Generic interpolation polynomial for list decoding (Q661987)

From MaRDI portal
Revision as of 06:38, 9 December 2024 by Import241208021249 (talk | contribs) (Normalize DOI.)
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