A note on the generalisation of the Guruswami-Sudan list decoding algorithm to Reed-Muller codes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Chapitre D'ouvrage Année : 2009

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

Résumé

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.

Dates et versions

inria-00564022 , version 1 (07-02-2011)

Identifiants

Citer

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⟩
176 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More