Title :
A fast interpolation method for list decoding of RS and algebraic-geometric codes
Author :
Sakata, Shojiro ; Numakami, Yukio ; Fujisawa, Masaya
Author_Institution :
Dept. of Inf. & Commun. Eng., Univ. of Electro-Commun., Tokyo, Japan
Abstract :
In this paper, we present an efficient algorithm to find a Grobner basis of the ideal set of polynomials I(V) based on the Berlekamp-Massey-Sakata (BMS) algorithm, which gives another efficient method of giving the solution at the first stage of the Sudan algorithm (1997). We also show that the interpolation problem can be generalized to find a Grobner basis of the ideal I(V;M) which consists of polynomials having zeros (αi,βi)∈V with some multiplicity condition specified by a set M (∈Z0 2) of integer vectors. This Hermitian type of interpolation problem takes a role in the improved version of the Sudan algorithm. A modification of BMS the algorithm can be applied to solve this problem. On the other hand, for list decoding of one-point AG codes our method can be adapted to find a Grobner basis of a relevant ideal
Keywords :
Reed-Solomon codes; algebraic geometric codes; decoding; interpolation; polynomials; Berlekamp-Massey-Sakata algorithm; Grobner basis; Hermitian problem; RS codes; Reed-Solomon codes; Sudan algorithm; algebraic-geometric codes; fast interpolation method; ideal set of polynomials; integer vectors; list decoding; multiplicity condition; Algorithm design and analysis; Computational complexity; Decoding; Ear; Equations; Error correction codes; Galois fields; Interpolation; Polynomials;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866777
