Les codes algébriques principaux et leur décodage

Daniel Augot (1)

1 TANC - Algorithmic number theory for cryptology

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.

Domaines: Théorie de l'information [cs.IT]; Théorie de l'information et codage [math.IT]

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⟩