Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d'une information (plus souvent appelée message) sur une voie de communication peu fiable.

La théorie des codes correcteurs ne se limite pas qu'aux communications classiques (radio, câble coaxial, fibre optique, etc.) mais également aux supports pour le stockage comme les disques compacts, la mémoire RAM et d'autres applications où l'intégrité des données est importante.

Problématique

---

Les codes correcteurs d'erreurs ont leur source dans un problème très concret lié à la transmission de données. Dans la grande majorité des cas, une transmission de données se fait en utilisant une voie de communication, le canal de communication, qui n'est pas entièrement fiable. Autrement dit, les données, lorsqu'elles circulent sur cette voie, sont susceptible d'être altérées.

Par exemple lors d'une communication radio, la présence de parasites sur la ligne va perturber le son de la voix. Il y a alors essentiellement deux approches possibles :

• augmenter la puissance de l'émission
• ajouter de la redondance à l'information

Si l'on reprend l'exemple de la communication radio, augmenter la puissance de l'émission signifie crier ou avoir un meilleur émetteur. Cette technique a bien évidemment ses limites, et aura du mal à être utilisée dans des sondes spatiales, sans même prendre en considération des contraintes sur les ressources en énergie.

L'autre solution va consister à ajouter des données, ce qui donne lieu au code des aviateurs qui diront «Alpha Tango Charlie» dans le seul but de transmettre correctemment «ATC» à travers leur radio. La séquence «Alpha Tango Charlie», même déformée par la friture, sera bien plus reconnaissable pour l'oreille humaine qu'un «ATC» déformé.

Formalisation du problème

---

Afin de préciser un peu les questions que se pose la théorie des codes, et les problèmes qu'elle rencontre, nous allons prendre l'exemple d'un canal discret. C'est-à-dire que nous allons supposer que l'information à transmettre peut être vue comme une suite $x$ de symboles (il s'agit le plus souvent de bits, donc de 0 et de 1). Ces symboles appartiennent à un ensemble $A$ (l'alphabet).

Avant sa transmission, le message est encodé, c'est-à-dire qu'il est transformé en une autre suite $y=E(x)$ de symboles, appartenant éventuellement à un autre ensemble $A\text{'}\backslash neq\; A$.

Ensuite, $y$ est transmis par un canal bruité qui va, éventuellement le modifier en $\backslash tilde\; y$. Pour terminer, un décodeur essaie de retrouver le message $x$ à partir de $\backslash tilde\; y$. Théoriquement, il est équivalent de rechercher $y=E(x)$, puisque l'encodage doit bien évidemment être une injection pour que le problème soit intéressant.

Lorsque $y\backslash neq\backslash tilde\; y$, on dit qu'une erreur est survenue, et si de plus on pose $y=(y\_0,...,y\_i,...)$ (resp. $\backslash tilde\; y=(\backslash tilde\; y\_0,...,\backslash tilde\; y\_i,...)$), alors $d(y,\backslash tilde\; y)=|\backslash \{i:\; y\_i\backslash neq\backslash tilde\; y\_i\backslash \}|$ est appelé le poids de l'erreur. De façon plus générale, $d(y,z)$ est appelée la distance de Hamming entre $y$ et $z$.

Codes en blocs et codes convolutifs

L'application d'encodage $E$ est définie sur une partie $M\backslash subset\; A^\backslash mathbb\{N\}$ et en fonction de cela on a essentiellement deux grandes classes de codes correcteurs :

• les codes en blocs
• les codes convolutifs.

La première classe, celle des codes en blocs, encode des messages de taille fixée $k$ (donc $M=A^k$, en identifiant cet ensemble à l'ensemble des suites nulles à partir du rang $k$) par des blocs de taille fixe $n$ (toujours en identifiant $A\text{'}^n$ à l'ensemble des suites nulles à partir du rang $n$). Formellement, $E:\; A^k\backslash to\; A\text{'}^n$.

La seconde classe, celle des codes convolutifs, ne nécessite pas le découpage en blocs de taille fixée, en fait, on a $E:\; A^\backslash mathbb\{N\}\backslash to\; A\text{'}^\backslash mathbb\{N\}$. Autrement dit, elle est définie sur des suites infinies de symboles, et prend donc des valeurs dans les suites d'éléments de $A\text{'}$.

Exemple de code en blocs

Considérons $A=A\text{'}=\backslash \{0,1\backslash \}$ et l'application $E$ :

• $E(0)\; =\; 000$ ;
• $E(1)\; =\; 111$.

Autrement dit, le message à transmettre est simplement répété trois fois et on a $k=1$ et $n=3$.

Définitions : Codes et encodages

Les éléments qui peuvent être atteints par l'application $E$ sont appelés les mots de code. Du point de vue de la correction d'erreurs ce qui importe, c'est la configuration « géometrique » de ces mots de code les uns par rapport aux autres et non pas l'association message/mot de code.

Pour cette raison, on appelle code l'ensemble des mots de code, donc l'image de l'application $E$. Cette dernière application est appelée l'encodage.

Dans le cas général, un même code $C$ admet clairement plusieurs encodages, il suffit par exemple de composer un encodage fixé avec une permutation de l'ensemble des messages.

Deux problèmes de la théorie des codes

---

Dans ses premiers travaux sur la théorie de l'information, Claude Shannon a prouvé l'existence d'une limite dans la quantité d'information pouvant être transmise de manière fiable en utilisant un canal bruité, limite appelée capacité du canal, et dépendant de la quantité de bruit -- il s'agit du second théorème de Shannon, encore appelé théorème du codage de canal. Il a également prouvé qu'il existait des codes correcteurs permettant d'atteindre cette limite. Malheureusement, ce dernier résultat n'est qu'un résultat d'existence, ce qui signifie que l'on ne connaît pas de moyens pratiques pour construire ces codes optimaux.

Un autre problème de toute première importance dans cette théorie est celui du décodage : ayant reçu $\backslash tilde\; y$, comment trouver le message $x$ émis à l'origine ? On ne sait pas résoudre ce problème efficacement pour tous les codes et on sait même que, dans toute sa généralité, ce problème ne peut être résolu.

Théorie algébrique des codes en blocs

---

Afin de pouvoir étudier les codes, plusieurs contraintes sont ajoutées au schéma extrêmement général que nous venons de décrire.

La contrainte la plus classique consiste à imposer aux alphabets $A$ et $A\text{'}$ d'avoir une structure algébrique de corps finis, autrement dit, de disposer des opérations $+,-,*$ et $/$, ainsi que d'un $0$ et d'un $1$.

Une première conséquence du fait que $A\text{'}$ soit un corps est que la distance de Hamming peut alors s'écrire en fonction d'une application $w$, sous la forme $d(y,z)=w(z-y)$, où $w(a)$ est le nombre de coordonnées non nulles de $a$. Cette application est appelée le poids de Hamming.

Capacité de correction et distance minimale

L'un des principaux objets de la théorie est de connaître la capacité de correction des codes. Cela signifie, dans ce contexte, connaître le poids maximal que peut avoir une erreur, sans que cela empêche de retrouver le mot de code émis.

Or, usuellement, on considère que le mot de code émis est celui se trouvant le plus près du mot reçu, ce qui revient à supposer que le moins possible de coordonnées ont été modifiées. Ce procédé conduit à une erreur de décodage à chaque fois que l'erreur $e$ est telle que $d(x\_0,x\_0+e)>d(x\_1,x\_0+e)$ où $x\_0$ et $x\_1$ sont des mots de code.

Cela ne peut pas se produire si le poids de $e$ est inférieur à $t=\backslash left\backslash lfloor\; \backslash frac\{\backslash min\_\{x\backslash neq\; x\text{'}\backslash in\; C\}\; d(x,x\text{'})\}\{2\}\backslash right\backslash rfloor$. Cette valeur est appelée la capacité de correction du code, tandis que $d=\backslash min\_\{x\backslash neq\; x\text{'}\backslash in\; C\}\; d(x,x\text{'})$ s'appelle la distance minimale.

La capacité de correction est donc le poids en dessous duquel toutes les erreurs peuvent être corrigées. Dans la pratique, on s'intéresse surtout à la distance minimale, ce qui est bien sûr équivalent.

Géométriquement, la capacité de correction est le rayon maximal que peuvent avoir des boules centrées sur les mots du code sans s'intersecter. Si on note $B\_r(x)=\backslash \{y\backslash in\backslash mathbb\{F\}^n\; :\; d(x,y)\backslash le\; r\backslash \}$ la boule fermée de rayon $r$ centrée en $x$, alors $t=\backslash max\; \backslash \{r\; :\; \backslash cap\_\{x\backslash in\; C\}\; B\_r(x)=\backslash emptyset\backslash \}$

Borne de Hamming et codes parfaits

L'une des premières questions soulevées par la capacité de correction est celle du nombre de messages que l'on peut envoyer en utilisant des blocs de taille $n$ tout en pouvant corriger $t$ erreurs.

L'interprétation géométrique de la capacité de correction donne une première borne supérieure : les boules fermées de rayon $t$ centrées sur les mots de code doivent être disjointes. Or le nombre d'éléments dans une boule est

$V\_t=\backslash sum\_\{i=0\}^\{t\}\; \{n\; \backslash choose\; i\}\; (q-1)^i$

où $\{n\; \backslash choose\; i\}$ est le $i$-ème coefficient binomial de rang $n$. En effet, pour un mot $x$ à distance $i$ du centre $c$, il y a $\{n\; \backslash choose\; i\}$ positions possibles pour les differences entre $x$ et $x\text{'}$. Et, pour chacune des $i$ positions, il a $(q-1)$ valeurs possibles, que l'on peut choisir indépendamment les unes des autres.

Les boules devant être disjointes, le cardinal de leur reunion est $M\backslash cdot\; V\_t$, en notant $M$ le cardinal du code. Or, cette reunion ne peut pas avoir un cardinal strictement superieure à celui de l'espace tout entier, $\backslash mathbb\{F\}^n$. Cela donne donc l'inégalité connue sous le nom de borne de Hamming :

$M\; \backslash leq\; \backslash frac\{q^n\}\{V\_t\}$

Les codes pour lesquels cette inégalité est en faite une égalité sont dit parfait. Autrement dit, un code de capacité de correction $t$ est parfait si les boules fermés de rayon $t$ centrés sur les mots de code sont disjointes et recouvre tout l'espace.

On connaît tous les codes parfaits, qui sont d'ailleurs très peu nombreux. Essentiellement, on a : les codes triviaux (un mot de code, ou tout l'espace), les codes de Hamming, les codes à répétition, et les codes de Golay binaire de longueur 23 et ternaire de longueur 11.

Paramètres et notation

Les trois paramètres les plus importants d'un code en blocs sont la longueur $n$ des blocs, le nombre $M$ de mots, c'est-à-dire le nombre de messages possibles, et enfin sa distance minimale $d$. Un code ayant ces paramètres est notée $\backslash \{n,M,d\backslash \}$.

Codes linéaires

L'alphabet $A\text{'}$ étant un corps, on peut imposer à un code $C$ d'avoir une structure d'espace vectoriel, on parle alors de code linéaire. On peut alors, sans restriction, prendre $A=A\text{'}$, ce que nous ferons dans la suite, et nous noterons $\backslash mathbb\{F\}$ le corps utilisé, suivant la tradition pour les corps finis.

Les paramètres d'un code linéaire sont notés de manière légèrement differente que ceux des codes quelconques. En effet, le cardinal d'un code linéaire est nécessairement une puissance du nombre $q$ d'éléments du corps $\backslash mathbb\{F\}$, à savoir $Card(C)=q^\{\backslash dim(C)\}$ où $\backslash dim(C)$ désigne la dimension de $C$ en tant que sous espace vectoriel (sur $\backslash mathbb\{F\}$) de $\backslash mathbb\{F\}^n$. On utilise donc la notation $*$ au lieu de $\backslash left\backslash \{n,q^k,d\backslash right\backslash \}$.

Matrice de parité

La linéarité d'un code implique de nombreuses propriétés très utiles, dont notamment un encodage et une détection d'erreurs très simples. Un espace vectoriel pouvant être vu comme l'ensemble des solutions d'un système d'équations linéaires homogènes, il existe un système

$\backslash begin\{matrix\}$

a_{0,0} y_0+...+a_{0,n-1} y_{n-1} =0\\ a_{1,0} y_0+...+a_{1,n-1} y_{n-1} = 0\\ ...\\ a_{r,0} y_0+...+a_{r,n-1} y_{n-1} = 0 \end{matrix} tel qu'il y a équivalence entre :

• $\backslash left(y\_0,...y\_\{n-1\}\backslash right)$ est solution du système si dessus ;
• $\backslash left(y\_0,...y\_\{n-1\}\backslash right)$ est un mot de code.

Il est habituel de mettre ce système sous forme matricielle

$y\backslash cdot\; H^t\; =\; 0$

où $H=\backslash left(a\_\{i,j\}\backslash right)$, $y=\backslash left(y\_0,...y\_\{n-1\}\backslash right)$ et la notation $\{\}^t$ désigne la transposition. La détection des erreurs est alors evidente : il suffit de verifier que le mot reçu est une solution ; le coût du calcul est donc un produit matriciel. C'est de là que la matrice $H$ tire son nom de matrice de contrôle --- on trouve également matrice de parité.

Matrice génératice

Considérons maintenant l'encodage. Un espace vectoriel admet une base, c'est-à-dire une famille de vecteurs $\{e\_i\}$ dont l'ensemble des combinaisons linéaires $\backslash left\backslash \{\backslash sum\_i\backslash lambda\_i\backslash cdot\; e\_i\; :\; \backslash lambda\_i\; \backslash in\; \backslash mathbb\{F\}\backslash right\backslash \}$ est l'espace tout entier avec une écriture unique d'un vecteur sous la forme d'une combinaison linéaire des $\{e\_i\}$ (une telle famille s'obtient par exemple en resolvant le système $y\backslash cdot\; H^t\; =\; 0$). Sous forme matricielle, cela signifie qu'il existe une matrice $G$ pour laquelle

$E\; :\; u\backslash in\; \backslash mathbb\{F\}^k\; \backslash mapsto\; u\backslash cdot\; G\backslash in\; \backslash mathbb\{F\}^n$

est un encodage et ses lignes forment une base du code. La matrice $G$ s'appelle la matrice génératice du code.

Code dual

La contrainte de linéarité sur le code donne naturellement naissance à la notion de code dual d'un code linéaire. Puisque $C$ est un espace vectoriel, on peut considerer l'ensemble des formes linéaires qui s'annulent sur $C$. Cet ensemble est un espace vectoriel que l'on appelle code dual de $C$. En fait, comme les formes linéaires sur l'espace de dimension fini $\backslash mathbb\{F\}^n$ s'identifie à $\backslash mathbb\{F\}^n$ lui-même --- à $f(y\_0,...,y\_\{n-1\})=c\_0y\_0+...+c\_\{n-1\}y\_\{n-1\}$ on associe $c=(c\_0,...,c\_\{n-1\})$ ---, le code dual est simplement identifié à l'ensemble des mots $y=(y\_0,...,y\_\{n-1\})$ de $\backslash mathbb\{F\}^n$ vérifiant

$y\_0c\_0+...+y\_\{n-1\}c\_\{n-1\}=0$

pour tout $c=(c\_0,...,c\_\{n-1\})\backslash in\; C$.

Par définition, le code dual, fréquement noté $C^\{\backslash bot\}$, est donc un code linéaire de la même longueur que $C$. Sa dimension est $n-k$ si $C$ est $*$. Il découle directement des définitions que si $H$ est une matrice de parité d'un code $C$, alors c'est une matrice génératrice du code dual $C^\{\backslash bot\}$. De même, une matrice génératrice de $C$ est une matrice de parité de $C^\{\backslash bot\}$.

Il est possible de calculer la distance minimale de $C^\{\backslash bot\}$ à partir de $C$, toutefois il n'est pas suffisant de connaitre celle de $C$ : il faut connaitre le polynôme énumerateur des poids de $C$. L'identité de MacWilliams donne alors celui de $C^\{\backslash bot\}$ d'où on extrait simplement la distance minimale de ce dernier.

Syndrome et décodage

Nous avons vu que la matrice de parité permet une détection très simple des erreurs. Elle peut également permettre une correction. L'application $S:y\backslash mapsto\; y\backslash cdot\; H^t$ est appelée le syndrome. Elle est linéaire et son noyau correspond au code.

Pour effectuer le décodage, on construit un tableau contenant toute les valeurs possibles de $S$, autrement dit si le code est $*$, tous les éléments de $\backslash mathbb\{F\}^\{n-k\}$ et à chaque élément $z$, on associe un mot $l\_z$ de poids minimal de l'ensemble $S^\{-1\}(\backslash \{z\backslash \})$.

Lorsque l'on veut décoder le mot $y$, on calcule son syndrome $z=S(y)$ et on prend $y-l\_z$. C'est un mot du code puisque $S(y-l\_\{z\})=S(y)-S(l\_z)=0$. De plus c'est l'un des mots les plus proches de $y$ : si $x\text{'}$ est dans les plus proches voisins de $y$, alors il minimise $d(x\text{'},y)=w(y-x\text{'})$. Or $y-x\text{'}$ a pour syndrome $z$ et a donc, par définition, un poids supérieur ou égal à celui de $l\_z$.

L'algorithme décrit ci-dessus permet de calculer l'un des plus proches voisins, mais il se peut très bien qu'il existe plusieurs voisins, autrement dit qu'il y ait plusieurs choix possibles de $l\_z$ pour certains $z$. Considérons un code $*$, avec $d=2t+1$, alors ce code peut corriger $t$ erreurs. Cela signifie --- voir l'interprétation géométrique de la capacité de correction --- que pour tout mot appartenant à une boule de rayon $t$ centré sur un mot de code, il n'y a qu'un seul plus proche voisin --- en fait, c'est une définition équivalente de la capacité de correction. Du point de vue de la table, pour chaque $z$ ayant un $l\_\{z\}$ de point inférieur à $t$, on peut être assuré de l'unicité du plus proche voisin.

Le problème soulevé par le décodage par syndrome est double :

• d'une part, il a $2^\{n-k\}$ syndromes possibles. Le tableau a donc très vite une taille telle qu'on ne peut plus le stocker. Par exemple, pour des blocs de 128 bits et une dimension de 80, le tableau a $2^\{48\}$ entrées. Même en étant très soucieux du stockage, cela représente un minimum de plusieurs dizaines de Tera-octets.
• outre le problème du stockage, il y également celui du calcul du tableau. Il n'y a pas véritablement mieux à faire que de calculer le syndrome de tous mots dont le poids est inférieur à $d-1$, soit $\{n\; \backslash choose\; d-1\}\; \backslash approx\; n^\{d-1\}$ calculs de syndrome.

Ce type de décodage est parfois appelé le décodage par tableau standard, en référence au tableau syndrome/mot de code qu'il nécessite.

Codes cycliques

Ces codes sont plus compliqués et reposent sur l'utilisation des propriétés des polynômes dans un corps fini. Le contrôle de redondance cyclique (CRC pour cyclic redundancy check) consiste à considérer un bloc de données comme la représentation des coefficients d'un polynôme que l'on divise ensuite par un polynôme fixe et prédéterminé. Les coefficients issus de cette division constituent le CRC et servent de code correcteur. La vérification des données se fait en multipliant le polynôme fixe par les coefficients du CRC et en comparant le résultat avec les données. On peut également calculer le CRC des données reçues et comparer avec le CRC reçu.

Autres codes

---

Les structures utilisées dans les codes correcteurs ont tout d'abord été très simples (par exemple celle d'espace vectoriel), puis ce sont complexifiés avec une meilleure compréhension des problèmes théoriques. La théorie des codes correcteurs en arrive même à utiliser la géométrie arithmétique pour construire des codes.

Quelques codes correcteurs

---

Voici différents types de codes correcteurs :

• Code de Hamming
• Code de Reed-Müller
• Code de Goppa
• Code de Xing
• Code de Elkies
• Code de Reed-Solomon

Quelques applications typiques

---

La transmissions d'informations peut-être sujet à des perturbations. Voici quelques applications touchés par ces perturbations :

• les téléphones cellulaires sont mobiles, relativement peu puissants, et souvent utilisés soit loin des antennes relais, soit dans un environnement urbain très bruyant du point de vue électromagnétique;
• les sondes spatiales n'ont pas à leur disposition d'énormes quantités d'énergie pour émettre des messages, se trouvent à des distances astronomiques, et leur antenne, même si elle est orientée le mieux possible, n'est pas parfaite;
• en cas de conflit armé, les communications adverses sont une des cibles privilégiées pour le brouillage et la guerre électronique
• les images disque contiennent pour certains formats (par exemple Mode 2 Form 1) des codes EDC et ECC pour contrôler les données gravées, et cela par secteur.

Différences entre un code correcteur et un code d'authentification

---

Le théorie des codes correcteurs s'intéresse à des perturbations aléatoires ou suivant une distribution particulière. Il n'y a pas d'"intelligence" dans ce bruit dans le sens où il ne s'agit pas d'une tentative frauduleuse de perturbation de ligne mais le résultat d'un phénomène physique inhérent au canal de transmission. Les codes d'authentification sont au contraire utilisés pour contrer un adversaire intelligent qui va tenter de modifier les données selon une procédure particulière qui s'éloigne du bruit sur la ligne. Les buts et les conditions de fonctionnement sont donc différents. Le premier concept est lié à la théorie de l'information alors que le deuxième est du ressort de la cryptologie et ne vise pas à rétablir l'information, tout au plus confirmer que l'information est valide.

Toutefois, dans le cas d'un brouillage volontaire (guerre électronique), les deux notions s'approchent puisque il faut éviter que l'attaquant réduise les capacités de transmission tout en assurant l'authenticité des informations.

Voir aussi

---

• Limite de Shannon
• Turbo code
• Méthode de décodage

Théorie des codes

Detecció d'errors | Fehlerkorrekturverfahren | Error correction and detection | Detección de errores | 誤り検出 | 오류정정부호 | Kanaalcodering | Коррекция ошибок