Les codes algébriques principaux et leur décodage

Daniel Augot 1
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
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.
Type de document :
Communication dans un congrès
Jean-Guillaume Dumas and Grégoire Lecerf and Delphine Boucher; and Thomas Cluzeau. Journées Nationales de Calcul Formel, May 2010, Luminy, France. CIRM, 1, pp.31-74, 2010, Les cours du CIRM. 〈http://ccirm.cedram.org/ccirm-bin/fitem?id=CCIRM_2010__1_2_31_0〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00543322
Contributeur : Daniel Augot <>
Soumis le : lundi 6 décembre 2010 - 13:27:02
Dernière modification le : jeudi 10 mai 2018 - 02:06:48
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:39:58

Fichiers

Identifiants

  • HAL Id : inria-00543322, version 1

Collections

Citation

Daniel Augot. Les codes algébriques principaux et leur décodage. Jean-Guillaume Dumas and Grégoire Lecerf and Delphine Boucher; and Thomas Cluzeau. Journées Nationales de Calcul Formel, May 2010, Luminy, France. CIRM, 1, pp.31-74, 2010, Les cours du CIRM. 〈http://ccirm.cedram.org/ccirm-bin/fitem?id=CCIRM_2010__1_2_31_0〉. 〈inria-00543322〉

Partager

Métriques

Consultations de la notice

505

Téléchargements de fichiers

4678