List Decoding of Reed-Solomon Codes from a Groebner Basis Perspective
Preprint
Abstract
The interpolation step of Guruswami and Sudan's list decoding of Reed-Solomon codes poses the problem of finding the minimal polynomial of an ideal with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Groebner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp-Massey-like decoding algorithm.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon CodesIEEE Transactions on Information Theory, 2005
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- On the key equationIEEE Transactions on Information Theory, 1995
- Gr bner bases of ideals defined by functionals with an application to ideals of projective pointsApplicable Algebra in Engineering, Communication and Computing, 1993