Skip to Main content Skip to Navigation
Conference papers

Les codes algébriques principaux et leur décodage

Daniel Augot 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Résumé : Le premier exposé reprend les algorithmes classiques de décodage des codes géométriques, basés sur l'algorithme de Berlekamp-Massey et ses généralisations multivariées (Berlekamp-Massey-Sakata). Toutefois, avant de présenter ces algorithmes, je rappelerai les bases de la théorie des codes : codes linéaires, borne de Singleton, codes de Reed-Solomon, borne de Hamming. Ensuite, j'introduirai de manière motivée la famille des codes géométriques, comme généralisation des codes géométriques, après un bref rappel de la théorie des courbes algébriques sur les corps finis. La cadre sera alors en place pour introduire le décodage par syndrômes, qui est le décodage classique des codes géométriques. Le deuxième exposé est consacré aux progrès récents dans le domaine du codage algébrique, qui reposent sur le décodage par interpolation. Ces progrès sont dus à Guruswami-Sudan, et reposent sur une vision duale des codes de Reed-Solomon et des codes géométriques. Je présenterai dans l'ordre les algorithmes de Berlekamp-Welsh, Sudan et Guruswami-Sudan, dans le contexte des codes de Reed-Solomon et dans le contexte des codes géométriques. On verra finalement comment l'algorithme de Berlekamp-Massey-Sakata peut être recyclé dans ce contexte.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00543322
Contributor : Daniel Augot <>
Submitted on : Monday, December 6, 2010 - 1:27:02 PM
Last modification on : Thursday, March 5, 2020 - 6:24:56 PM
Long-term archiving on: : Thursday, June 30, 2011 - 1:39:58 PM

Files

Identifiers

  • HAL Id : inria-00543322, version 1

Collections

Citation

Daniel Augot. Les codes algébriques principaux et leur décodage. Journées Nationales de Calcul Formel, Jean-Guillaume Dumas, Grégoire Lecerf, Delphine Boucher et Thomas Cluzeau, May 2010, Luminy, France. pp.31-74. ⟨inria-00543322⟩

Share

Metrics

Record views

609

Files downloads

8078