A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes

Alexander Zeh 1, 2 Christian Senger 2
1 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
2 INT - University of Ulm. - Institute of Communications Engineering [Ulm]
Abstract : The Welch-Berlekamp approach for Reed-Solomon (RS) codes forms a bridge between classical syndrome-based decoding algorithms and interpolation-based list-decoding procedures for list size ℓ = 1. It returns the univariate error-locator polynomial and the evaluation polynomial of the RS code as a y-root. In this paper, we show the connection between the Welch-Berlekamp approach for a specific Interleaved Reed-Solomon code scheme and the Guruswami-Sudan principle. It turns out that the decoding of Interleaved RS codes can be formulated as a modified Guruswami-Sudan problem with a specific multiplicity assignment. We show that our new approach results in the same solution space as the Welch-Berlekamp scheme. Furthermore, we prove some important properties.
Keywords : decoding irs list
Type de document :
Communication dans un congrès
M. Gastpar and R. Heath and K. Narayanan. IEEE International Symposium on Information Theory (ISIT), Jun 2010, Austin, United States. IEEE, pp.1198-1202, 2010, 〈10.1109/ISIT.2010.5513427〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00647609
Contributeur : Alexander Zeh <>
Soumis le : vendredi 2 décembre 2011 - 14:16:57
Dernière modification le : jeudi 10 mai 2018 - 02:06:56
Document(s) archivé(s) le : samedi 3 mars 2012 - 02:31:25

Fichier

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

Identifiants

Collections

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

Citation

Alexander Zeh, Christian Senger. A link between Guruswami-Sudan's list-decoding and decoding of interleaved Reed-Solomon codes. M. Gastpar and R. Heath and K. Narayanan. IEEE International Symposium on Information Theory (ISIT), Jun 2010, Austin, United States. IEEE, pp.1198-1202, 2010, 〈10.1109/ISIT.2010.5513427〉. 〈hal-00647609〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

330

Téléchargements de fichiers

119

Contact


archive-ouverte@inria.fr