Code correcteur

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

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.

[modifier] 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é.

[modifier] 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'\neq A$ .

Ensuite, $y$ est transmis par un canal bruité qui va, éventuellement le modifier en $\tilde y$ . Pour terminer, un décodeur essaie de retrouver le message $x$ à partir de $\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\neq\tilde y$ , on dit qu'une erreur est survenue, et si de plus on pose $y = (y 0,..., y i,...)$ (resp. $\tilde y=(\tilde y_0,...,\tilde y_i,...)$ ), alors $d(y,\tilde y)=|\{i: y_i\neq\tilde y_i\}|$ 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$ .

[modifier] Codes en blocs et codes convolutifs

L'application d'encodage $E$ est définie sur une partie $M\subset A^\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' n$ à l'ensemble des suites nulles à partir du rang $n$ ). Formellement, $E: A^k\to A'^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^\mathbb{N}\to A'^\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'$ .

[modifier] Exemple de code en blocs

Considérons $A = A' = {0,1}$ 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$ .

[modifier] 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.

[modifier] 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 $\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.

[modifier] 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'$ 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'$ 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.

[modifier] 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=\left\lfloor \frac{\min_{x\neq x'\in C} d(x,x')}{2}\right\rfloor$ . Cette valeur est appelée la capacité de correction du code, tandis que $d=\min_{x\neq x'\in C} d(x,x')$ 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)=\{y\in\mathbb{F}^n : d(x,y)\le r\}$ la boule fermée de rayon $r$ centrée en $x$ , alors $t=\max \{r : \cap_{x\in C} B_r(x)=\emptyset\}$

[modifier] 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=\sum_{i=0}^{t} {n \choose i} (q-1)^i$

où ${n \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 \choose i}$ positions possibles pour les différences entre $x$ et $x'$ . 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\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, $\mathbb{F}^n$ . Cela donne donc l'inégalité connue sous le nom de borne de Hamming :

$M \leq \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 recouvrent 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.

[modifier] 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 ${n, M, d}$ .

[modifier] Codes linéaires

Voir l’article Code linéaire.

L'alphabet $A'$ é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'$ , ce que nous ferons dans la suite, et nous noterons $\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 différente 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 $\mathbb{F}$ , à savoir $Card(C)=q^{\dim(C)}$ où $\dim(C)$ désigne la dimension de $C$ en tant que sous espace vectoriel (sur $\mathbb{F}$ ) de $\mathbb{F}^n$ . On utilise donc la notation $[n, k, d]$ au lieu de $\left\{n,q^k,d\right\}$ .

[modifier] 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

$\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 :

$\left(y_0,...y_{n-1}\right)$ est solution du système si dessus ;
$\left(y_0,...y_{n-1}\right)$ est un mot de code.

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

$y\cdot H^t = 0$

où $H=\left(a_{i,j}\right)$ , $y=\left(y_0,...y_{n-1}\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é.

[modifier] 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 $\left\{\sum_i\lambda_i\cdot e_i : \lambda_i \in \mathbb{F}\right\}$ 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\cdot H^t = 0$ ). Sous forme matricielle, cela signifie qu'il existe une matrice $G$ pour laquelle

$E : u\in \mathbb{F}^k \mapsto u\cdot G\in \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.

[modifier] 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 $\mathbb{F}^n$ s'identifie à $\mathbb{F}^n$ lui-même --- à $f (y 0,..., y n - 1) = c 0 y 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 $\mathbb{F}^n$ vérifiant

y 0 c 0 + ... + y n - 1 c n - 1 = 0

pour tout $c=(c_0,...,c_{n-1})\in C$ .

Par définition, le code dual, fréquemment noté $C^{\bot}$ , est donc un code linéaire de la même longueur que $C$ . Sa dimension est $n - k$ si $C$ est $[n, k]$ . 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^{\bot}$ . De même, une matrice génératrice de $C$ est une matrice de parité de $C^{\bot}$ .

Il est possible de calculer la distance minimale de $C^{\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^{\bot}$ d'où on extrait simplement la distance minimale de ce dernier.

[modifier] Syndrome et décodage

Voir l’article Décodage par syndrome.

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\mapsto y\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 $[n, k, d]$ , tous les éléments de $\mathbb{F}^{n-k}$ et à chaque élément $z$ , on associe un mot $l z$ de poids minimal de l'ensemble $S - 1 ({z})$ .

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'$ est dans les plus proches voisins de $y$ , alors il minimise $d (x', y) = w (y - x')$ . Or $y - x'$ 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 $[n, k, d]$ , avec $d = 2 t + 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 $248$ 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 \choose d-1} \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.

[modifier] 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.

[modifier] 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 se 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.

[modifier] 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

[modifier] 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.

[modifier] 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.

[modifier] Voir aussi

Récupérée de « http://fr.wikipedia.org../../../c/o/d/Code_correcteur.html »

Catégorie : Théorie des codes