Décodage en liste des codes géométriques

Travaux de doctorat de l’Université Paris VI
(désormais UPMC Sorbonne Universités)

Recherche menée, entre 1997 et 2001, au projet CODES (désormais SECRET) de l’INRIA, sous la direction de Pascale Charpin, Directrice de recherche INRIA, Directrice du projet CODES, et de Daniel Augot, Chargé de recherche INRIA.

Pour une introduction grand public à la théorie des codes, voir mon article L’algèbre qui corrige les erreurs. Une description de mes travaux destinée aux scientifiques non spécialistes de ce sujet est fournie plus bas.

Résumé : Les codes géométriques ont été introduits par Goppa en 1981 et sont construits à partir de courbes algébriques sur les corps finis. En 1982, Tsfasman, Vladuts et Zink ont montré qu’on pouvait construire de tels codes dépassant la borne de Gilbert-Varshamov. En 1996, Sudan a proposé un algorithme de décodage en liste des codes de Reed-Solomon. Cet algorithme fut adapté, en 1997, aux codes fortement géométriques à un point par Shokrollahi et Wasserman, puis amélioré par Guruswami et Sudan.

Dans cette thèse, nous étendons ces méthodes à tous les codes géométriques, à leurs sous-codes dans un sous-corps, et à une distance de Hamming généralisée qui nous permet de reformuler algébriquement le problème du décodage souple et de proposer un algorithme de décodage en liste à maximum de vraisemblance sur tout canal discret sans mémoire. Nous illustrons ces nouveaux résultats par une implantation dans le système de calcul formel Magma.

NB: il demeure quelques erreurs que je n’ai jamais eu le courage de corriger.

2000 Mathematics Subject Classification: 11T71 Algebraic coding theory; cryptography; 94B35 Decoding; 94B27 Geometric methods (including applications of algebraic geometry) [See also 11T71, 14G50]; 11Yxx Computational number theory [See also 11-04]; 14Qxx Computational aspects in algebraic geometry [See also 12Y05, 13Pxx, 68W30]; 68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 17-08, 33F10].

Mots clés : Décodage en liste; décodage souple à maximum de vraisemblance; codes géométriques; codes de Reed-Solomon; sous-codes dans un sous-corps; algorithme de Guruswami-Sudan; géométrie algébrique effective; théorie algorithmique des nombres; racines de polynômes sur un corps de fonctions de courbe sur un corps fini; calcul formel; implantation en Magma.

Soutenance: Cette thèse a obtenu la mention Très Honorable à l’issue d’une soutenance s’étant déroulée le mardi 18 décembre 2001 à 14h00, Campus de Jussieu (Batiment 41, Salle 203-205), 4, place Jussieu, 75005 Paris, France, devant un jury constitué de:

  • Daniel Lazard: Professeur (Paris VI), Président du Jury
  • Pascale Charpin: Directrice de recherche (INRIA), Directrice de thèse
  • Daniel Augot: Chargé de recherche (INRIA), Co-directeur de thèse
  • Claude Carlet: Professeur (Caen), Rapporteur
  • Tom Høholdt: Professor (DTU, Danemark), Rapporteur
  • François Morain: Professeur (Polytechnique), Examinateur

Description « non technique » à destination des scientifiques non-spécialistes du sujet

Contexte

La Théorie des codes a pour objectif principal de fiabiliser les télécommunications de manière mathématique. Elle a été fondée vers le milieu de 20e siecle par les travaux de Claude Shannon et Richard Hamming, entre autres.

De gigantesques progrès ont été faits depuis et les connexions de la Théorie des codes avec d’autres branches des mathématiques et de l’informatique comme la Combinatoire, la Cryptographie, la Théorie des nombres ou la géométrie algébrique ou encore la Théorie de la complexité sont innombrables.

L’introduction d’outils de géométrie algébrique par Goppa lui permit, en 1981, de fabriquer des codes qualifiés naturellement de « géométriques » à partir de courbes sur les corps finis. Ces codes bénéficient de la puissante Théorie de Riemann-Roch qui permet en particulier d’estimer les paramètres fondamentaux des codes que sont leur distance minimale et leur dimension.

En 1982, Michael Tsfasman, Serge Vladuts et Thomas Zink réussirent à montrer une famille explicite de codes géométriques meilleurs que tous les codes connus dont les performances dépassaient même la borne de Gilbert-Varshamov qu’on conjecturait – à tort – être optimale.

En 1996, Madhu Sudan proposa une méthode de décodage en liste des codes de Reed-Solomon, qui fut adaptée en 1997 par Amin Shokrollahi et Hal Wasserman aux codes fortement géométriques à un point, puis améliorée par Venkatesan Guruswami et Sudan.

Contributions de cette thèse

  1. La généralisation de l’algorithme de Guruswami-Sudan à tous les codes géométriques
  2. La description d’un algorithme de décodage en liste pour une distance généralisant la distance de Hamming et permettant un décodage souple algébrique maximisant la vraisemblance sur tout canal discret sans mémoire
  3. Des raffinements des conditions d’existence des polynômes auxiliaires utilisés dans les algorithme de décodage en liste
  4. Une prise en compte des structures de données et des primitives algorithmiques requises pour exploiter la structure géométrique des codes (courbe, normalisée, genre, diviseurs, espaces de Riemann-Roch) pour leur décodage en liste
  5. Une implantation en Magma d’un algorithme de désingularisation d’un modèle plan d’une courbe et d’une amélioration de l’algorithme de Brill-Noether permettant, entre-autres, le calcul de séries p-adiques de fonctions en tout point fermé p de la courbe considérée et son genre (collaboration avec Pawel Wocjan)
  6. L’implantation en Magma d’une bibliothèque de manipulation de canaux de communications permettant de tester notre algorithme de décodage souple
  7. L’adaptation de l’algorithme de Newton-Puiseux à la recherche de racines de polynômes à coefficients dans un corps de fonctions, qui nous permet de fournir l’une des primitives exploitées dans l’algorithme de décodage en liste
  8. La démonstration d’une propriété combinatoire sur les codes de faible taux de transmission permettant d’utiliser dans ce cas l’algorithme de Newton-Hensel, ce qui réduit la complexité de leur décodage en liste à un temps essentiellement quadratique (collaboration avec Daniel Augot)
  9. La preuve qu’on peut précalculer suffisamment d’information pour ne pas avoir à recourir à la Théorie de Riemann-Roch effective pendant le décodage en liste
  10. Une implantation complète, en Magma, des méthodes ci-dessus, en particulier de notre algorithme de décodage en liste généralisé et de sa version souple