Beelen, Peter1; Høholdt, Tom3; Nielsen, Johan Sebastian Rosenkilde1; Wu, Yingquan4
1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Mathematics, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 Discrete mathematics, Department of Mathematics, Technical University of Denmark4 Sandforce Inc.
We derive the Wu list-decoding algorithm for generalized Reed–Solomon (GRS) codes by using Gröbner 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.
I E E E Transactions on Information Theory, 2013, Vol 59, Issue 6, p. 3269-3281