On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm

Daniel Augot; Alexander Zeh

doi:10.1109/ISIT.2008.4595466

On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm

Daniel Augot
, Alexander Zeh

INRIA Rocquencourt
University of Suttgart
Team SECRET
Institute of Communication Networks and Computer Engineering

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

15 Citations (Scopus)

Résumé

In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the Sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the Guruswami-Sudan (GS) algorithm, which is able to list decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative Algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.

langue originale	Anglais
titre	Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Editeur	Institute of Electrical and Electronics Engineers Inc.
Pages	2620-2624
Nombre de pages	5
ISBN (imprimé)	9781424422579
Les DOIs	https://doi.org/10.1109/ISIT.2008.4595466
état	Publié - 1 janv. 2008
Modification externe	Oui
Evénement	2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada Durée: 6 juil. 2008 → 11 juil. 2008

Série de publications

Nom	IEEE International Symposium on Information Theory - Proceedings
ISSN (imprimé)	2157-8095
ISSN (Electronique)	2157-8117

Une conférence

Une conférence	2008 IEEE International Symposium on Information Theory, ISIT 2008
Pays/Territoire	Canada
La ville	Toronto, ON
période	6/07/08 → 11/07/08

Accès au document

10.1109/ISIT.2008.4595466

Contient cette citation

Augot, D., & Zeh, A. (2008). On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm. Dans Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008 (p. 2620-2624). Article 4595466 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2008.4595466

@inproceedings{ee00570b88a2462a9a0035129a50f84c,

title = "On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm",

abstract = "In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the Sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the Guruswami-Sudan (GS) algorithm, which is able to list decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative Algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.",

keywords = "(Extended) Key Equation, Guruswami-Sudan algorithm, List decoding, Polynomial interpolation, Reed-Solomon codes",

author = "Daniel Augot and Alexander Zeh",

year = "2008",

month = jan,

day = "1",

doi = "10.1109/ISIT.2008.4595466",

language = "English",

isbn = "9781424422579",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2620--2624",

booktitle = "Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008",

note = "2008 IEEE International Symposium on Information Theory, ISIT 2008 ; Conference date: 06-07-2008 Through 11-07-2008",

}

Augot, D & Zeh, A 2008, On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm. Dans Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008., 4595466, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., p. 2620-2624, 2008 IEEE International Symposium on Information Theory, ISIT 2008, Toronto, ON, Canada, 6/07/08. https://doi.org/10.1109/ISIT.2008.4595466

On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm. / Augot, Daniel; Zeh, Alexander.
Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008. Institute of Electrical and Electronics Engineers Inc., 2008. p. 2620-2624 4595466 (IEEE International Symposium on Information Theory - Proceedings).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm

AU - Augot, Daniel

AU - Zeh, Alexander

PY - 2008/1/1

Y1 - 2008/1/1

N2 - In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the Sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the Guruswami-Sudan (GS) algorithm, which is able to list decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative Algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.

AB - In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the Sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the Guruswami-Sudan (GS) algorithm, which is able to list decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative Algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.

KW - (Extended) Key Equation

KW - Guruswami-Sudan algorithm

KW - List decoding

KW - Polynomial interpolation

KW - Reed-Solomon codes

U2 - 10.1109/ISIT.2008.4595466

DO - 10.1109/ISIT.2008.4595466

M3 - Conference contribution

AN - SCOPUS:52349089005

SN - 9781424422579

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2620

EP - 2624

BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008

Y2 - 6 July 2008 through 11 July 2008

ER -

On the Roth and Ruckenstein equations for the Guruswami-Sudan algorithm

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation