A note on the generalisation of the Guruswami-Sudan list decoding algorithm to Reed-Muller codes

Daniel Augot 1 Michael Stepanov 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 : We revisit the generalisation of the Guruswami-Sudan list decoding algorithm to Reed-Muller codes. Although the generalisation is straightforward, the analysis is more difficult than in the Reed-Solomon case. A previous analysis has been done by Pellikaan and Wu, relying on the theory of Groebner bases [2, 3]. We give a stronger form of the well-known Schwartz-Zippel Lemma [5, 4], taking multiplicities into account. Using this Lemma, we get an improved decoding radius.
Type de document :
Chapitre d'ouvrage
Massimiliano Sala and Teo Mora and Ludovic Perret and Shojiro Sakata and Carlo Traverso. Gröbner Bases, Coding, and Cryptography, 2, Springer, pp.395-398, 2009, 〈10.1007/978-3-540-93806-4_27〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00564022
Contributeur : Daniel Augot <>
Soumis le : lundi 7 février 2011 - 18:11:26
Dernière modification le : jeudi 10 mai 2018 - 02:06:23

Lien texte intégral

Identifiants

Collections

Citation

Daniel Augot, Michael Stepanov. A note on the generalisation of the Guruswami-Sudan list decoding algorithm to Reed-Muller codes. Massimiliano Sala and Teo Mora and Ludovic Perret and Shojiro Sakata and Carlo Traverso. Gröbner Bases, Coding, and Cryptography, 2, Springer, pp.395-398, 2009, 〈10.1007/978-3-540-93806-4_27〉. 〈inria-00564022〉

Partager

Métriques

Consultations de la notice

148