ADS - Codes de contrôle (détecteurs et correcteurs d'erreurs)

Il existe trois grands types de codes :

• la compression : diminuer le coût de stockage et de transmission de l'information (diminuer taille et redondance)
• la cryptographie : assurer la confidentialité de l'information
• les codes de contrôle (détecteurs et correcteurs d'erreurs) : assurer la fiabilité du stockage et de la transmission de l'information (augmentation de la redondance)

Leur étude a été initiée par Shannon il y a une cinquantaine d'années avec la théorie de l'information. Les théorèmes de Shannon ont montré l'existence de codes optimaux (correcteurs d'erreurs et compression), et Varshamov et Gilbert ont montré à la même époque l'existence de codes ayant un taux de transmission optimal par rapport à la fiabilité.

Nous allons tout d'abord définir les outils utilisés puis étudier quelques exemples de codes de contrôle.

Qu'est-ce qu'un code correcteur ?

Lors de la transmission ou stockage de l'information codée, sous forme de mots, il peut y avoir des imperfections, du bruit qui causent un risque d'omission ou de modification d'un symbole.

Code

Commençons par définir mathématiquement quelques termes :

• alphabet.........ensemble fini F (de symboles)
• mot...............k-uplet   , k étant fixe
• vocabulaire.....ensemble A de mots,
• code..............application injective :   (A, B vocabulaires)

Exemples de codes :

• code génétique : {nucléotides A, C, G, U}³ -> {acides aminés}
• langues et traduction
  Ces deux exemples de codes ne sont pas des applications injectives.
• conversion de bases : binaire <-> hexadécimal, {0,1}⁴ <-> {0,...,9,A,...,F}  (applications bijectives)

Alphabets utilisés

Un code efficace nécessite des relations entre les symboles, donc des alphabets numériques qui permettent d'effectuer des opérations mathématiques sur les symboles.

Les opérations les plus simples, l'addition et la multiplication, sont définies dans un corps. Un corps est un ensemble muni de deux opérations, qui doivent vérifier quelques propriétés, notamment la stabilité (toute combinaison d'éléments du corps avec ses opérations doit donner un résultat qui appartient au corps) et la symétrisation des éléments (chaque élément doit avoir un inverse et un opposé dans le corps).

Par ailleurs un alphabet fini implique un corps fini, que l'on munit des addition et multiplication modulo p (on ne garde que le reste de la division euclidienne du résultat par le cardinal p du corps).

De plus, si F est un corps, l'ensemble des mots de k symboles F^k est un espace-vectoriel. Les mots sont alors des vecteurs, ce qui permet d'utiliser toutes les ressources de l'algèbre linéaire.
De nombreux codes sont linéaires, ce sont donc des applications linéaires qui ont une matrice associée, utile pour les calculs.

On utilisera désormais l'alphabet binaire {0,1} muni des addition et multiplication modulo 2 (ainsi 1+1 = 0).

Code de contrôle

On caractérise un code par trois nombres : code [n,k,d]

• n = dimension du vocabulaire but (nombre de symboles des mots)
• k = dimension du vocabulaire source
• d = distance minimale (nombre minimal de symboles différents) entre deux mots du vocabulaire but

k/n représente alors le taux de transmission (vitesse) et d/n la fiabilité de transmission.

On peut séparer les codes de contrôle en deux catégories :

• Les codes détecteurs d'erreur (ex : bit de parité)
• Les codes correcteurs d'erreur : permettent de détecter et corriger les erreurs.
  On utilise le principe de décodage par vraisemblance maximale : si le mot reçu n'appartient pas au vocabulaire, le mot envoyé est le mot du vocabulaire le plus proche (au sens de distance de Hamming : nombre de coordonnées différentes = d). On suppose donc que le minimum d'erreur a été commis.
  Pour pouvoir corriger une erreur il faut que d soit supérieur ou égal à trois.
  Ces codes se basent sur la redondance (répétition) de l'information.

Exemples de codes de contrôle

Codes détecteurs d'erreurs et bit de parité

Les codes détecteurs d'erreur consistent à créer la signature d'un mot. On peut protéger autant de symboles que l'on veut avec un symbole (seuls problèmes : localisation de l'erreur et risque d'erreurs multiples se compensant).
Ces codes sont très simples et économes donc très utilisés (calcul de CRC dans les fichiers informatiques, numéro RIB, numéro SECU, transmission modems).

Bit de parité
Le bit de parité est un code [k+1,k,1], dont le principe est d'ajouter un bit au mot de sortes que le nombre de bits à 1 du mot soit pair. Il suffit alors de calculer ce bit à la réception et de le comparer avec celui envoyé pour savoir si une erreur de transmission a été commise. Il est particulièrement utilisé dans les modems, puisque chaque octet en contient un ce qui permet au modem de redemander un octet erronné, avec une perte de temps minimale.

Mais lorsque la source n'est pas disponible comme pour un modem, comme pour le stockage sur disquette par exemples, il peut ne pas être suffisant de savoir qu'une donnée est erronnée mais pouvoir la corriger.

Le codage à triple répétition

C'est un code [3,1,3], très simple, qui consiste à répéter trois fois chaque mot. Il permet évidemment de corriger une erreur dans chaque symbole de donnée, mais est très coûteux, puisqu'il multiplie par 3 la taille des données (k/n = 1/3).

Le code de Hamming

Le code de Hamming est une code [7,4,3]. Il prend donc en entrée des mots de 4 bits de données, et ajoute 3 bits de contrôle pour donner des mots de 7 bits.
Plus précisément : (u₁ ,u ₂,u₃ ,u₄ ) -> (u₁ ,u₂ ,u₃ ,u₄,u ₅ ,u₆,u₇ ) où :

• u₅ = u₁ + u ₂ + u₃
• u₆ = u₂ + u ₃ + u₄
• u₇ = u₁ + u ₂ + u₄

Les bits de donnée 1, 3 et 4 apparaissent dans deux équations, le bit de donnée 2 dans trois, et les bits de contrôle 5, 6 et 7 dans une seule.
On peut alors vérifier que l'on a bien d = 3 : en modifiant un bit de donnée, intervenant dans deux ou trois équations, il faut modifier deux ou trois bits de contrôle pour que les équations soient vérifiées, ce qui signifie que le nombre minimal de bits différents entre deux mots est 3. Il permet donc bien de corriger une erreur dans le mot.

Pour le décodage on est confronté à plusieurs cas :

• Aucune équation fausse : pas d'erreur (ou plusieurs qui se compensent)
• Une équation fausse : seuls les bits de contrôles n'interviennent que dans une équation, c'est donc le bit de contrôle en cause qui est erroné.
• Deux équations fausses : seuls les bits de donnée 1, 3 et 4 interviennent seulement dans deux équations, c'est donc le bit de donnée commun aux deux équations fausses qui est erroné.
• Trois équations fausses : seul le bit de donnée 2 intervient dans les trois équations, c'est lui qui est erroné.

Le codage de Hamming reste cependant médiocre par rapport aux critères de Varshamov et Gilbert, c'est pourquoi de nouveaux codes ont été recherchés et sont en train de voir effectivement le jour.

Les codes de Goppa (géométrico-algébriques)

Il s'agit d'une généralisation des codes de Reed-Solomon (utilisés par exemple dans les CD audios).
Ces codes utilisent les courbes sur un corps fini, d'équation P(x;y) = 0 (où P est un polynôme de degré m). En notant (P_j(x_j;y_j))_1<=j<=n les solutions de l'équation (points de la courbe), et en choisissant une base (G_i)_1<=i<=k des polynômes à deux inconnues de degré inférieur à m, on construit la matrice G de dimension k,n tel que ses éléments soient g_ij = G_i(P_j), qui définit un code [n,k,d] pour lequel on peut montrer que d >= n - d°(P).

Ces codes ont une grande distance minimale, ce qui les rend avantageux pour les transmissions très perturbées (satellite ...).

Exemple : avec la courbe de Klein x³y + y³ + y = 0 qui a 24 solutions dans le corps à 8 éléments, on peut construire un code [24,3,21] qui permet de corriger jusqu'à 10 erreurs dans un mot.

On a montré qu'il existe des codes de Goppa sur des corps de cardinal supérieur à 49 qui font mieux que l'optimum défini par Varshamov et Gilbert.

Conclusion

Les codes correcteurs d'erreurs sont donc encore un sujet de recherche active, visant principalement une mise en oeuvre efficace. Ils sont peu connus mais très utilisé, car la fiabilité des transmissions et du stockage est une nécessité.