On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes
We derive the Wu list-decoding algorithm for generalized Reed-Solomon (GRS) codes by using Grobner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp-Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.
goppa code list decoding johnson radius list size rational interpolation reed-solomon code