Journal article

A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation

Mortuza Ali, Margreta Kuijper

IEEE TRANSACTIONS ON INFORMATION THEORY | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | Published : 2011

Abstract

In this paper, we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Minimal list decoding for a code C refers to list decoding with radius L, where L is the minimum of the distances between the received word {\bf r} and any codeword in C. We consider the problem of determining the value of L as well as determining all the codewords at distance L. Our approach involves a parametrization of interpolating polynomials of a minimal Grbner basis G. We present two efficient ways to compute G. We also show that so-called re-encoding can be used to further reduce the complexity. We then demonstrate how our parametric approach can be solved by a computationally feasible rational c..

View full abstract