Auteur : Gintaras Skersys
Date de soutenance : 21 octobre 1999
Titre : Calcul du groupe d'automorphismes des codes. Détermination de l'équivalence des codes.
Jury : G. Robin (Prés.), P. Charpin (Rap.), P. Fitzpatrick (Rap.), F. Laubie, F. Morain, T. Berger (Dir.), N. Sendrier (Codir.)
Document : Thèse (PDF)
Résumé : Nous présentons dans ce travail un algorithme pour calculer les groupes de permutations et d'automorphismes d'un code correcteur d'erreurs et pour déterminer l'équivalence et l'équivalence par permutation de deux codes. Il est basé sur la méthode des partitions de Jeffrey S. Leon et sur l'algorithme de séparation du support de Nicolas Sendrier.
La méthode des partitions de Leon nous semble très technique, nous avons donc essayé de la clarifier en la présentant d'une manière différente de celle de Leon.
Notre algorithme est limité par la dimension du hull (l'intersection du code avec son dual) des codes concernés qui doit être inférieure à une vingtaine. Si c'est le cas, notre algorithme fonctionne efficacement, par exemple, pour les codes linéaires binaires de longueur jusqu'à 10000.
De plus, nous avons étudié la dimension du hull des codes cycliques. Nous avons montré que la dimension moyenne du hull des codes cycliques de longueur n donnée sur un corps fini Fq donné est soit nulle, soit de l'ordre de n, et elle est nulle si et seulement si n est un diviseur d'un entier de la forme qm+1, m>=0. Nous avons étudié l'ensemble des diviseurs des entiers de cette forme.
Mots-clés : Codes correcteurs d'erreurs, groupe de permutations d'un code, groupe d'automorphismes d'un code, équivalence des codes, équivalence par permutation des codes, base et ensemble fort de générateurs (BSGS), recherche arrière ("backtrack search"), algorithme, méthode des partitions de J. Leon, raffinement, algorithme de séparation du support de N. Sendrier, signature, hull, dimension du hull des codes cycliques.