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

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

doi:10.1109/TIT.2013.2243800

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 journal › Journal article › Research › peer-review

319 Downloads (Pure)

Abstract

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 language	English
Journal	I E E E Transactions on Information Theory
Volume	59
Issue number	6
Pages (from-to)	3269-3281
ISSN	0018-9448
DOIs	https://doi.org/10.1109/TIT.2013.2243800
Publication status	Published - 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.

Access to Document

10.1109/TIT.2013.2243800

Goppa v3Accepted author manuscript, 318 KB

Cite this

@article{4695793dccfb4ab2b83a0fe897505246,

title = "On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes",

abstract = "We derive the Wu list-decoding algorithm for generalized Reed–Solomon (GRS) codes by using Gr{\"o}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.",

author = "Peter Beelen and Tom H{\o}holdt and Nielsen, {Johan Sebastian Rosenkilde} and Yingquan Wu",

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.",

year = "2013",

doi = "10.1109/TIT.2013.2243800",

language = "English",

volume = "59",

pages = "3269--3281",

journal = "I E E E Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers",

number = "6",

}

TY - JOUR

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

AU - Beelen, Peter

AU - Høholdt, Tom

AU - Nielsen, Johan Sebastian Rosenkilde

AU - Wu, Yingquan

N1 - 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.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1109/TIT.2013.2243800

DO - 10.1109/TIT.2013.2243800

M3 - Journal article

VL - 59

SP - 3269

EP - 3281

JO - I E E E Transactions on Information Theory

JF - I E E E Transactions on Information Theory

SN - 0018-9448

IS - 6

ER -

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

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this