On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes

Peter Beelen, Tom Høholdt, Johan Sebastian Rosenkilde Nielsen, Yingquan Wu

Research output: Contribution to journalJournal articleResearchpeer-review

404 Downloads (Pure)


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.
Original languageEnglish
JournalI E E E Transactions on Information Theory
Issue number6
Pages (from-to)3269-3281
Publication statusPublished - 2013

Bibliographical note

Copyright 2015 IEEE. IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.


Dive into the research topics of 'On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes'. Together they form a unique fingerprint.

Cite this