Skip to main content

2009 | OriginalPaper | Buchkapitel

A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes

verfasst von : Daniel Augot, Michael Stepanov

Erschienen in: Gröbner Bases, Coding, and Cryptography

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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 (List decoding of

q

-ary Reed–Muller codes, Tech. report, from the authors,

2004a

; IEEE Trans. on Inf. Th. 50(4): 679–682,

2004b

), relying on the theory of Gröbner bases We give a stronger form of the well-known Schwartz–Zippel Lemma (Schwartz in J. Assoc. Comput. Mach. 27(4): 701–717,

1980

; Zippel in Proc. of EUROSAM 1979, LNCS, vol. 72, Springer, Berlin, pp. 216–226,

1979

), taking multiplicities into account. Using this Lemma, we get an improved decoding radius.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
verfasst von
Daniel Augot
Michael Stepanov
Copyright-Jahr
2009
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-93806-4_27