Generic interpolation polynomial for list decoding (Q661987): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q5563439 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4693774 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient list decoding of a class of algebraic-geometry codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3413659 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decoding affine variety codes using Gröbner bases / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3613964 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the structure of order domains / rank
 
Normal rank
Property / cites work
 
Property / cites work: FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved decoding of Reed-Solomon and algebraic-geometry codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: List decoding of Reed-Solomon codes from a Gröbner basis perspective / rank
 
Normal rank
Property / cites work
 
Property / cites work: List decoding of Hermitian codes using Gröbner bases / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decoding Cyclic Codes: the Cooper Philosophy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Gröbner basis approach to list decoding of algebraic geometry codes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructions in Algebra / rank
 
Normal rank

Revision as of 21:31, 4 July 2024

scientific article
Language Label Description Also known as
English
Generic interpolation polynomial for list decoding
scientific article

    Statements

    Generic interpolation polynomial for list decoding (English)
    0 references
    11 February 2012
    0 references
    In this article list decoding of one-point algebraic geometry codes is studied, given a nonsingular, absolutely irreducible projective curve defined over a finite field. A one-point algebraic geometry code is obtained by assigning to the functions of a Riemann-Roch space of the form \(L(rP)\), with \(P\) a rational point on the curve, codewords of the form \((f(P_1),\dots,f(P_n))\), with \(P_1,\dots,P_n\) other rational points on the curve. The list decoding of such codes can be done using the Guruswami-Sudan list decoding algorithm. In this algorithm an interpolation polynomial needs to be found. The interpolation polynomial \(Q\) depends on the received word \((r_1,\dots,r_n)\), since it is required to satisfy that it has \((P_i,r_i)\) as a zero, possibly with a certain multiplicity. All interpolation polynomials lie in a certain ideal and the interpolation polynomial needed in the list-decoding algorithm can be found using Gröbner basis techniques. In this paper results of Lee and O'Sullivan are extended to show how to find the interpolation polynomial needed for the list decoding of one-point algebraic geometry codes. Then a generic point of view is taken: since the interpolation polynomial depends on the received word \((r_1,\dots,r_n)\), one can try to find a generic interpolation polynomial by regarding \(r_1,\dots,r_n\) as variables. Specializing these variables in the generic interpolation polynomial to the actually received values, one can obtain the interpolation polynomial needed for the decoding. This approach is certainly of theoretical interest, though it is difficult to find an explicit generic interpolation polynomial if one wants to correct many errors. In the example given in the paper, the authors consider a \([q-1,q-3,3]\) Reed-Solomon code (meaning the underlying algebraic curve is the projective line). A generic interpolation polynomial is given assuming at most one error has occurred.
    0 references
    list decoding
    0 references
    generic interpolation polynomial
    0 references
    one-point algebraic geometry code
    0 references
    Gröbner basis
    0 references
    affine variety code
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references