Arithmétique modulaire - Définition

Code correcteur

Les CD utilisent comme code cyclique une variante du code de Reed-Solomon appelée code C.I.R.C.

Un code correcteur n'a pas la vocation d'assurer la sécurité, mais la fiabilité de la transmission d'un message. Il permet de restituer le texte original même si une perturbation aléatoire et modérée se produit durant la transmission. Le message encodé est transmis sous une forme appelée mot du code. Il contient non seulement les informations du message initial mais aussi les redondances permettant la validation d'une bonne communication et parfois la correction automatique d'éventuelles erreurs.

Un mot du code est composée d'une famille de n lettres choisies dans un alphabet, en général binaire. Le cas industriel le plus fréquent est celui du code linéaire, la valeur n est constante pour chaque mot du code et est appelée dimension du code. L'ensemble des mots du code est muni d'une structure d'espace vectoriel de dimension n.

Les codes linéaires utilisent essentiellement l'arithmétique modulaire comme base mathématique. Beaucoup enrichissent la structure d'espace vectoriel par celle d'un anneau de polynômes sur un corps fini. Ce corps est parfois le corps binaire, souvent un corps de cardinal une puissance de deux. On parle alors de code cyclique.

Les codes linéaires sont largement présent dans l'industrie. La télécommunication les utilise pour le téléphone portable ou internet, l'informatique pour notamment la communication entre la mémoire et de processeur, l'audio-visuel pour les disques compacts ou d'autres formats de même nature comme les DVD.

Somme de contrôle

Code de longueur deux avec une somme de contrôle

Une somme de contrôle est un code linéaire particulièrement utilisé. Il correspond à un code correcteur dont seule la détection est automatisable, la correction est obtenue par une demande de répétition du message.

Au message initial est ajoutée une information codée sur une lettre. La lettre est choisie de telle manière à ce que la congruence de la somme des lettres du mot du code soit égale à une valeur donnée, souvent zéro. Dans l'exemple illustré sur la figure de droite, le message initial est composé de deux lettres, un mot du code en contient trois, si le message initial est 00, le mot du code transmis est 000, si le message est 01, le mot du code devient 011. Les quatre mots possibles du code sont illustrés par les points verts de la figure.

Si une unique erreur se produit, sur n'importe laquelle des trois lettres du mot du code, le message reçu correspond à un point noir. Le récepteur sait qu'il doit demander le renouvellement de la transmission. Cette configuration est analogue quelle que soit la longueur du mot du code. Une longueur égale à huit est souvent choisie, elle permet la transmission d'un message de sept lettres. Le résultat est identique, chaque mot licite du code ne possède pour voisin que des mots hors du code, une unique erreur durant la transmission est ainsi détectée. En revanche une double anomalie est systématiquement passée sous silence.

Code cyclique

Illustration d'un code parfait

Il existe certaines situations où la demande de répétition n'est pas possible, par exemple pour un DVD, lorsqu'une poussière masque une information. Il est nécessaire d'imaginer des codes correcteurs qui, non seulement détectent, mais corrigent automatiquement les erreurs.

La méthode utilisée consiste à éloigner les mots du code à une distance suffisante pour repérer le bon message d'origine. La distance entre deux points correspond au nombre de lettres à modifier pour passer de l'un à l'autre. Le graphique de gauche illustre cette situation. Les points verts correspondent aux mots du code, par définition sans erreur. Les bleus sont ceux obtenus lorsqu'une unique lettre est altérée dans la transmission et les rouges quand deux lettres sont modifiées. Dans le schéma, on remarque que chaque point bleu contient un unique point vert à une distance de un et à chaque point rouge correspond un unique point vert situé à une distance de deux. Si une ou deux erreurs se sont produites, l'unique point vert le plus proche correspond nécessairement au message initial. Un tel code est capable de protéger jusqu'à deux erreurs.

L'arithmétique modulaire fournit des solutions optimales pour construire la géométrie d'un code linéaire correcteur. Comme un espace vectoriel ne constitue pas une structure suffisante pour définir des moduli, il est enrichi d'une structure d'anneau de polynômes quotienté par Xⁿ - 1, où n désigne la dimension de l'espace vectoriel. Dans cet espace de modulo, le monôme Xⁿ est identifié au polynôme constant un. Si la chaîne (a₀, a₁, …, a_n) est un mot du code, alors il en est de même de la suivante : (a_n, a₀, a₁, …, a_n-1). On parle pour cette raison de code cyclique. La logique est la même que celle d'un code correcteur, à la différence près que la congruence est définie non pas sur un entier mais sur un polynôme cyclotomique à coefficients dans un corps fini.

L'exemple le plus simple correspond au code de Hamming dont les messages à transmettre comportent quatre lettres et trois lettres supplémentaires décrivent les redondances.

Identité de Mac Williams

Le contexte d'un code linéaire est analogue à celui de la cryptographie, on y trouve aussi des espaces vectoriels de dimension n sur un corps fini et un système de modulo de polynômes, le polynôme choisi étant souvent : Xⁿ + 1. Les caractères du groupe sont utilisés, ainsi que l'analyse harmonique associée.

L'identité de Mac Williams est un exemple archétypal. Elle permet la détermination du polynôme énumérateur des poids du code dual ou encore l'étude des caractéristiques du code de Hamming. Elle est obtenue grâce à l'analyse harmonique, à l'aide d'un produit de convolution.