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

Des courbes pour le codage et la cryptographie

Dans cet exposé élémentaire et introductif au Colloquium Junior de l’INRIA, nous présentons la problématique usuelle de la théorie des codes correcteurs d’erreurs et de la cryptographie. Nous montrons comment l’utilisation de la géométrie algébrique effective des courbes sur les corps finis peut être utilisée pour résoudre certaines des questions se posant dans ces disciplines.

Construction des codes géométriques avec Magma

Dans cet exposé donné au 3e Congrès Européen de Mathématiques (3ECM, Barcelone, Espagne, juillet 2000), nous illustrons un certain nombre de qualités du système de calcul formel Magma et la manière dont il peut servir à l’implantation d’algorithmes sophistiqués faisant intervenir de nombreuses primitives dans différentes branches des mathématiques effectives comme les corps finis, la géométrie algébrique ou la théorie des codes correcteurs d’erreurs en donnant pour exemple la construction des codes de Goppa géométriques au sein de ce système.

Ce travail a été réalisé en collaboration avec Pawel WOCJAN.

Un relèvement de Hensel pour le décodage en liste

Cet article propose une amélioration algorithmique de l’algorithme de Sudan pour les codes de Reed-Solomon et sa généralisation aux codes géométriques par Shokrollahi et Wasserman. Au lieu de factoriser complètement le polynôme d’interpolation sur le corps de fonctions de la courbe, nous calculons rapidement suffisamment de termes du développement p-adique des fonctions correspondant aux mots de code cherchés grâce à la méthode de Newton.

Ce travail a été réalisé en collaboration avec Daniel Augot, publié dans IEEE Transactions on Information Theory, vol. 46, n°7, pp. 2605-2614, 2000. Une version préliminaire a été proposée dans le Rapport de Recherche INRIA, n° 3532, novembre 1998.cience/codec/RR-3532.pdf »>INRIA Research Report, n° 3532, November 1998.

Rapport eurocitoyen sur la sécurité et la défense

En 2007, les menaces ne se situent plus exclusivement dans des pays lointains, le terrorisme frappe au cœur de l’Europe, les criminels ont des moyens croissants, le rôle des média est fondamental, l’armée s’est professionnalisée, l’informatique a pris une importance majeure dans les entreprises et chez les particuliers, l’Europe de la défense se construit…

Ce projet avait pour objectif de permettre à des citoyens de discuter ensemble et avec des experts, et de se forger une opinion sur les questions de sécurité et la défense en France et en Europe, en complément du débat officiel dans un contexte de réformes nationales¹ et internationales² majeures. La première version de ce document peut être trouvé ici.

¹Livre blanc sur la défense et la sécurité nationale en cours de rédaction par la Commission Mallet, mission Bauer sur la recherche stratégique, création de la Direction Centrale du Renseignement Intérieur (DCRI), réunissant la Direction Centrale des Renseignement Généraux (DCRG) et la Direction de la Surveillance du Territoire (DST), Commission Balladur sur la modernisation des institutions de la Ve République, Révision Générale des Politiques Publiques (RGPP), réforme de la carte judiciaire, etc.

² Signature du Traité de Lisbonne et Présidence française du Conseil de l’Union Européenne en 2008.

Programmation fonctionnelle

Polycopié de programmation fonctionnelle en Licence

Cours de programmation fonctionnelle en Licence, Université Paris XII (2001-2003)

Découvrez Objective Caml

Publié dans GNU/Linux & Hurd Magazine France n° 43 (oct. 2002)

Objective Caml (Ocaml pour les intimes) est un langage de programmation magnifique: flexible, sûr, d’exécution rapide, doté de nombreuses bibliothèques (graphiques, réseau, …). Il est souvent, à tort, considéré comme une curiosité qui n’intéresserait que quelques informaticiens théoriciens. Dans cet article, nous parcourrons rapidement l’arbre généalogique de ce langage pour en comprendre les principes fondateurs et familiariser le lecteur avec la programmation fonctionnelle; nous présenterons ensuite les différents modes de travail d’Ocaml et quelques aspects originaux de ce langage. Nous terminerons par un petit exemple d’utilisation des bibliothèques graphique et Unix et l’évocation des autres outils de développement disponibles pour Ocaml.

Ressources autour de la validité et la sûreté/sécurité des logiciels

History’s Worst Software Bugs, by Simson Garfinkel, 2005.