Sudan's List Decoding of Reed-Solomon Codes from a Groebner Basis Perspective

Authors:
  • KLKwankyu Lee
    Kwankyu Lee
  • MOMichael E. O'Sullivan
    Michael E. O'Sullivan

Abstract
Sudan's list decoding of Reed-Solomon codes is formulated as a 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 is shown to be equivalent with the Berlekamp-Massey algorithm for decoding Reed-Solomon codes.