Efficient List-Decoding of Reed-Solomon Codes with the Fundamental Iterative Algorithm

Alexander Zeh 1, 2 Christian Gentner 3 Martin Bossert 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
Abstract : In this paper we propose a new algorithm that solves the Guruswami-Sudan interpolation step for Reed-Solomon codes efficiently. It is a generalization of the Feng-Tzeng approach, the so-called fundamental iterative algorithm. From the interpolation constraints of the Guruswami-Sudan principle it is well known that an improvement of the decoding radius can only be achieved, if the multiplicity parameter s is smaller than the list size l. The code length is n and our proposed algorithm has a complexity (without asymptotic assumptions) of O(ls4 n2).}, keywords={Feng-Tzeng approach;Guruswami-Sudan interpolation;Reed-Solomon codes;communication complexity;efficient list-decoding;fundamental iterative algorithm;Reed-Solomon codes;communication complexity;decoding;iterative methods;
Type de document :
Communication dans un congrès
Daniel Costello and Alex Grant. IEEE Information Theory Workshop (ITW), Sep 2010, Taorminia, Italy. IEEE, pp.130-134, 2009, 〈10.1109/ITW.2009.5351241〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00647592
Contributeur : Alexander Zeh <>
Soumis le : vendredi 2 décembre 2011 - 14:03:47
Dernière modification le : jeudi 12 avril 2018 - 01:47:26
Document(s) archivé(s) le : samedi 3 mars 2012 - 02:31:01

Fichier

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

Identifiants

Collections

Citation

Alexander Zeh, Christian Gentner, Martin Bossert. Efficient List-Decoding of Reed-Solomon Codes with the Fundamental Iterative Algorithm. Daniel Costello and Alex Grant. IEEE Information Theory Workshop (ITW), Sep 2010, Taorminia, Italy. IEEE, pp.130-134, 2009, 〈10.1109/ITW.2009.5351241〉. 〈hal-00647592〉

Partager

Métriques

Consultations de la notice

427

Téléchargements de fichiers

145