Gröbner basis approach to list decoding of algebraic geometry codes (Q2460910): Difference between revisions

\textit{M. Sudan} [J. Complexity 13, 180--193 (1977; Zbl 0872.68026)] gave a decoding method (originally for Reed Solomon codes but soon generalized to algebraic geometry (AG) codes), based on List Decoding, improving the performances of previous decoding methods (to the price of returning a list of codewords, sometimes with more than one element; then a choice can be made based on supplementary information). Sudan's algorithm has two stages: in the first the received word is used to find a set of points and a polynomial in two variables interpolating these points while the second stage determines the factors of the polynomial to yield the list of codewords. On the other hand the authors of the paper under review presented [Linear Algebra Appl. 351--352, 533--551 (2002; Zbl 1008.93036)] a general algorithm based on Gröbner bases to solve a system of polynomial congruences such as \[ H^k({\mathbf b})\equiv 0 \bmod M^k,\,\, k=1,\dots p \] with \({\mathbf b}=(b_1,\dots, b_L)\in A^L\),\, and \(M^k\) \(A\)-modules, where \(A\)\, is a polynomial ring \(A=F[x_1,\dots, x_s]\). That Gröbner basis algorithm was previously applied by the authors to the interpolation problem of list decoding of Reed Solomon codes. In the present paper they show how it can be applied to the list decoding of (one point) AG codes. Section 2 of the paper joins together the notation and the needed results about Gröbner basis. Section 3 gives a linear functional version of their algorithm, assuming the additional hypothesis that the set of solutions of the system is a submodule, while in Section 4 the authors derive a congruence based version of the algorithm. Section 5 is devoted to the application of the algorithm to the list decoding of AG codes. Firstly the authors summarize Sudan's algorithm and one point AG codes. Then they show how their module description leads to decoding algorithms for AG codes, both for hard decision list decoding (Algorithm 8) and soft decision. Algorithm 9 provides a common list decoding algorithm to solve both problems. Finally the paper discuss the complexity of the common and hard decision algorithms.