Multi-Trial Guruswami--Sudan Decoding for Generalised Reed--Solomon Codes

Abstract : An iterated refinement procedure for the Guruswami--Sudan list decoding algorithm for Generalised Reed--Solomon codes based on Alekhnovich's module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity. We provide a detailed description of the module minimisation, reanalysing the Mulders--Storjohann algorithm and drawing new connections to both Alekhnovich's algorithm and Lee--O'Sullivan's. Furthermore, we show how to incorporate the re-encoding technique of Kötter and Vardy into our iterative algorithm.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00975927
Contributeur : Alexander Zeh <>
Soumis le : mercredi 9 avril 2014 - 20:42:05
Dernière modification le : dimanche 31 décembre 2017 - 09:44:02
Document(s) archivé(s) le : mercredi 9 juillet 2014 - 12:11:52

Fichiers

hal-arxiv20140409.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Johan Sebastian Rosenkilde Nielsen, Alexander Zeh. Multi-Trial Guruswami--Sudan Decoding for Generalised Reed--Solomon Codes. Designs, Codes and Cryptography, Springer Verlag, 2014, pp.1-21. 〈10.1007/s10623-014-9951-7〉. 〈hal-00975927〉

Partager

Métriques

Consultations de la notice

441

Téléchargements de fichiers

103