Efficient list decoding of a class of algebraic-geometry codes (Q540394): Difference between revisions

The paper of \textit{M. Sudan} [J. Complexity 13, No. 1, 180--193 (1997; Zbl 0872.68026)] introduced a new paradigm in the decoding of error-correcting codes: the list decoding. First formulated for Reed-Solomon codes, the papers of \textit{M. A. Shokrollahi} and \textit{H. Wasserman} [IEEE Trans. Inf. Theory 45, No. 2, 432--437 (1999; Zbl 0947.94024)] and \textit{V. Guruswami} and \textit{M. Sudan} [IEEE Trans. Inf. Theory 45, No. 6, 1757--1767 (1999; Zbl 0958.94036)] extended the algorithm of Sudan to algebraic-geometry (AG) codes. The central and more costly step in the algorithm of Guruswami and Sudan is an interpolation step. The present paper proposes an efficient interpolation algorithm for a certain class of AG codes. Section 2 introduces the family of AG codes that are considered in the remainder of the paper, the family of one-point AG codes that includes Reed-Solomon codes, Hermitian codes and norm-trace codes. Section 3 reformulates the constrained interpolation problem in the algorithm of Guruswami and Sudan in terms of finitely generated modules over an univariate polynomial ring. In this formulation interpolation polynomials of low degree correspond to short vectors in the module. To find such short vectors, Section 4 generalizes an algorithm due to \textit{M. Alekhnovich} [``Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes'', IEEE Trans. Inf. Theory 51, No. 7, 2257--2265 (2005)] and Section 5 shows that this algorithm can compute the necessary interpolation polynomial. Finally, Section 6 examines several examples of codes in the family (projective line, elliptic codes, Hermitian codes), finding for each of them the complexity of the interpolation step, a complexity that it is lower than the complexity of previously known algorithms.