Article ID Journal Published Year Pages File Type
401662 Journal of Symbolic Computation 2008 14 Pages PDF
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 Gröbner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp–Massey-like decoding algorithm.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence