Skip to Main content Skip to Navigation
Book sections

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

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.
Complete list of metadata

https://hal.inria.fr/inria-00564022
Contributor : Daniel Augot <>
Submitted on : Monday, February 7, 2011 - 6:11:26 PM
Last modification on : Thursday, March 5, 2020 - 6:27:00 PM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

424