Minimal list decoding of Reed-Solomon codes using a parameterization of Gröbner bases
Mortuza Ali, Margreta Kuijper · 2011
Minimal list decoding for a code C refers to list decoding with radius L(y), where L(y) is the minimum of the distances between the received word y and any codeword in C. In this paper we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Our approach involves a parametrization of the interpolating polynomials of a minimal Gröbner basis G. We then demonstrate that our parametric approach can be solved by a computationally efficient rational curve fitting solution from a recent paper by Wu. Besides, we present an algorithm to compute the minimum multiplicity as well as the associated optimal values of the parameters. Use of these optimal parameters in the rational interpolation step results in computational as well as memory efficiency.