Generic interpolation polynomial for list decoding
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.
- List decoding of Reed-Solomon codes from a Gröbner basis perspective
- Efficient list decoding of a class of algebraic-geometry codes
- scientific article; zbMATH DE number 2081134
- Gröbner basis approach to list decoding of algebraic geometry codes
- List decoding codes on Garcia-Stichtenoth tower using Gröbner basis
- Constructions in Algebra
- Decoding affine variety codes using Gröbner bases
- Decoding cyclic codes: the Cooper philosophy
- Efficient list decoding of a class of algebraic-geometry codes
- Evaluation codes from an affine variety code perspective
- FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments
- Gröbner basis approach to list decoding of algebraic geometry codes
- scientific article; zbMATH DE number 217454 (Why is no real title available?)
- scientific article; zbMATH DE number 3279238 (Why is no real title available?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- List decoding of Hermitian codes using Gröbner bases
- List decoding of Reed-Solomon codes from a Gröbner basis perspective
- On the structure of order domains
- Generalization of the Lee-O'Sullivan list decoding for one-point AG codes
- On the small-weight codewords of some Hermitian codes
- List decoding algorithm based on voting in Gröbner bases for general one-point AG codes
- Efficient list decoding of a class of algebraic-geometry codes
- Improved decoding of affine-variety codes
- List decoding codes on Garcia-Stichtenoth tower using Gröbner basis
- Interpolation in list decoding of Reed-Solomon codes
This page was built for publication: Generic interpolation polynomial for list decoding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q661987)
