Thèse de doctorat (PhD thesis)

Décodage en liste des codes géométriques
(List decoding of Algebraic-Geometric Codes)

Thèse de doctorat de l'Université Pierre et Marie Curie, Paris 6, réalisée au Projet Codes de l'Unité de Recherche de Rocquencourt de l'INRIA, sous la direction de Pascale Charpin et la co-direction de Daniel Augot.

PhD thesis of Pierre et Marie Curie, Paris 6 University, done at Projet Codes, Rocquencourt Research Unit of INRIA, under the direction of Pascale Charpin and the co-direction of Daniel Augot.

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é:

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.

Keywords:

List decoding; maximum-likelihood soft-decision decoding; algebraic-geometric codes; Reed-Solomon codes; subfield subcodes; Guruswami-Sudan's algorithm; effective algebraic geometry; algorithmic number theory; roots of polynomials on function fields of curves over a finite field; computer algebra; Magma implementation.

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.

Abstract:

Algebraic-geometric codes were introduced by Goppa in 1981 and are built using algebraic curves over finite fields. In 1982, Tsfasman, Vladuts and Zink showed that one could build a family of such codes that beats the Gilbert-Varshamov bound. In 1996, Sudan proposed a list decoding algorithm for Reed-Solomon codes. This algorithm was adapted in 1997 to one-point strongly algebraic-geometric codes by Shokrollahi and Wasserman, then improved by Guruswami and 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. [suite]

In this thesis, we extend these methods to all algebraic-geometric codes and their subfield subcodes, and to a generalized Hamming distance that allows to reformulate algebraically the soft decision decoding problem and to propose a maximum likelihood list decoding algorithm over any discrete memoryless channel. We illustrate these new results with an implementation in the computer algebra system Magma. [more]

Contexte

Context

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.

Coding Theory's main goal is to improve mathematically the reliability of telecommunications. Its foundations were built in the middle of the 20th century with the work of Claude Shannon, Richard Hamming, and others.

Claude Shannon
(1916-2001)

Richard Hamming
(1915-1998)

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.

Huge progress has been made since then and the connexions between Coding Theory and others areas of Mathematics and Computer Science, like Combinatorics, Cryptography, Number Theory, Algebraic Geometry or Complexity Theory are innumerable.

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.

The introduction of algebraic-geometric tools by Goppa allowed him to build in 1981 some codes, naturally called "algebraic-geometric", from curves over finite fields. These codes beneficiate from the powerful Riemann-Roch Theory that allows, in particular, to estimate the fundamental parameters of such codes that are their minimum distance and their dimension.

Les points rationnels d'une courbe

Bernhardt Riemann
(1826-1866)

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.

In 1982, Michael Tsfasman, Serge Vladuts and Thomas Zink could exhibit a family of explicit algebraic-geometric codes that were better than all known codes at that time and whose performance was beating the Gilbert-Varshamov bound that was (wrongly) conjectured to be optimal.

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.

In 1996, Madhu Sudan proposed a method for the list decoding of Reed-Solomon codes, that was adapted in 1997 by Amin Shokrollahi and Hal Wasserman to one-point strongly algebraic-geometric codes, and improved again by Venkatesan Guruswami and Sudan.

Contributions de cette thèse

Contributions of this thesis

La généralisation de l'algorithme de Guruswami-Sudan à tous les codes géométriques.

The generalization of Guruswami-Sudan's algorithm to all algebraic-geometric codes.

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.

The description of a list decoding algorithm for a distance that generalizes the Hamming distance and that allows an algebraic soft decision decoding that maximizes the likelihood on any discrete memoryless channel.

Fig. 1. Décodage en liste par rapport à la distance de Hamming (Fig. 1) et par rapport à la distance généralisée (Fig. 2) permettant le décodage souple.

Fig. 2. List decoding with respect to Hamming distance (Fig. 1) and with respect to the generalized distance (Fig. 2) that allows soft decision decoding.

Des raffinements des conditions d'existence des polynômes auxilliaires utilisés dans les algorithme de décodage en liste.

Some refinements of existence conditions for auxilliary polynomials that are used in list decoding algorithms.

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.

An evaluation that takes into account the data structures and algorithmic primitives that are required to use the geometric structure of codes (curve, normalized curve, genus, divisors, Riemann-Roch spaces) for their list decoding.

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).

An implementation in Magma of a desingularization algorithm of a plane model of a curve and of an improved version of the Brill-Noether algorithm. This allows in particular, the computation of p-adic series of fonctions in any closed point p of the curve and its genus (joint work with Pawel Wocjan).

Alexander von Brill
(1842-1935)

Max Noether
(1844-1921)

L'implantation en Magma d'une bibilothèque de manipulation de canaux de communications permettant de tester notre algorithme de décodage souple.

The implementation in Magma of a communication channels library that allows to test our soft decision algorithm.

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.

The adaptation of Newton-Puiseux's algorithm for finding roots of polynomials over function fields, that provides one of the primitives used in the list decoding algorithm.

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, publié dans IEEE Transactions on Information Theory).

The proof of a combinatoric property of low-rate codes that allows to use, in that case, Newton-Hensel's algorithm, which dramatically reduces the complexity of their list decoding to essentially quadratic time (joint work with Daniel Augot, published in IEEE Transactions on Information Theory).

Kurt Hensel
(1861-1941)

Victor Puiseux
(1820-1883)

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.

The proof that one can precompute sufficient information for not having to use effective Riemann-Roch Theory during list decoding.

Une implantation en Magma, complète des méthodes ci-dessus, en particulier de notre algorithme de décodage en liste généralisé et de sa version souple.

A complete implementation in Magma, of the above methods, in particular of our generalized list decoding algorithm and its soft decision version..

Isaac Newton
(1643-1727)
Kneller. Huile sur toile, 1702
National Portrait Gallery, London UK.

Soutenance

Defence

Je vous invite à la soutenance de ma thèse de doctorat de l'Université Pierre et Marie Curie, Paris 6, intitulée Décodage en liste des codes géométriques ainsi qu'au pot qui se tiendra juste après. Merci de m'écrire si vous avez l'intention de venir.

I invite you for the defence of my PhD at Université Pierre et Marie Curie, Paris 6, entitled List Decoding of Algebraic-Geometric Codes and to the party that will take place just afterwards. Thanks for writing to me if you plan to come.

La soutenance aura lieu le:
Mardi 18 décembre 2001
à 14h00
Batiment 41, Salle 203-205
Campus de Jussieu
4, place Jussieu
75005 Paris, France.

The defence will take place on:
Tuesday, december 18th 2001
at 2:00pm
Building 41, Room 203-205
Campus of Jussieu
4, place Jussieu
75005 Paris, France.

Vous pouvez venir au campus de Jussieu en transports en commun, en utilisant les lignes de métro 7 ou 10, ou en empruntant l'un des bus suivants: 24, 63, 67, 86, 87, 89. Il est recommandé de ne pas venir en voiture, car il est tres difficile de se garer dans le quartier.

You can come to the Jussieu campus using public transport, by taking the subway lines 7 or 10, or take one of the following buses: 24, 63, 67, 86, 87, 89. It is recommanded not to come by car, since it is extremely difficult to park in the Jussieu area.

Jussieu.

Sur le plan du campus qui suit, l'itinéraire rouge est celui à prendre quand on utilise l'entrée principale, place Jussieu (par exemple quand on vient en métro, station Jussieu). On peut rejoindre le bâtiment 41 par une passerelle dans le prolongement du bâtiment 42 ou descendre du parvis au niveau inférieur dans la tour 42, puis continuer jusqu'au bâtiment 41, marqué d'une croix violette. Quand on vient du 9, quai St-Bernard (par exemple quand on a pris les bus 24, 63 ou 89), il faut suivre l'itinéraire jaune. La salle 203-205 est au deuxième étage.

On the map of the campus that follows, the red itinerary is the one to take when you come from the main entrance, place Jussieu (for instance when you come from the Jussieu subway station). You can reach building 41 by taking the bridge from building 42 or go downstairs in tower 42, then continue to building 41, marked with a purple cross. The yellow itinerary is to be used when you come from the entrance 9, quai St-Bernard (for instance if you have taken the bus 24, 63 or 89). The room 203-205 is located at the third floor (floor 0 = street level in France).

Comment rejoindre le bâtiment 41

How to reach buiding 41