Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm

Alexander Zeh 1, 2 Wenhui Li 1
1 INT - University of Ulm. - Institute of Communications Engineering [Ulm]
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We modify the Euclidean algorithm of Feng and Tzeng to decode Reed-Solomon (RS) codes up to the Sudan radius. The basic steps are the virtual extension to an Interleaved RS code and the reformulation of the multi-sequence shift-register problem of varying length to a multi-sequence problem of equal length. We prove the reformulation and analyze the complexity of our new decoding approach. Furthermore, the extended key equation, that describes the multi-sequence problem, is derived in an alternative polynomial way.
Keywords : Euclidean algorithm Reed-Solomon code Sudan radius multisequence problem multisequence shift register problem Reed-Solomon codes binary sequences decoding
Type de document :
Communication dans un congrès
Mao-Chao Lin and Hideki Ochiai and Tetsushi Ikegami. IEEE International Symposium on Information Theory and its Applications (ISITA), Oct 2010, Taichung, Taiwan. IEEE, pp.986-990, 2010, 〈10.1109/ISITA.2010.5649520〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00647597
Contributeur : Alexander Zeh <>
Soumis le : vendredi 2 décembre 2011 - 13:13:57
Dernière modification le : mercredi 10 octobre 2018 - 20:30:03
Document(s) archivé(s) le : samedi 3 mars 2012 - 02:31:06

Fichier

isita2010.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | LIX | INSMI | X-LIX | X | PARISTECH | X-DEP-INFO

Citation

Alexander Zeh, Wenhui Li. Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm. Mao-Chao Lin and Hideki Ochiai and Tetsushi Ikegami. IEEE International Symposium on Information Theory and its Applications (ISITA), Oct 2010, Taichung, Taiwan. IEEE, pp.986-990, 2010, 〈10.1109/ISITA.2010.5649520〉. 〈hal-00647597〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

193

Contact


archive-ouverte@inria.fr