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

Alexander Zeh 1, 2 Wenhui Li 1
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, 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.
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 : jeudi 11 janvier 2018 - 06:22:14
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

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〉

Partager

Métriques

Consultations de la notice

284

Téléchargements de fichiers

177