Code parfait et code MDS

Les codes parfaits et les codes MDS, pour maximum distance séparable) sont des types de codes correcteurs d'erreur.

Un code correcteur est un code permettant au récepteur de détecter ou de corriger des altérations à la suite de la transmission ou du stockage. Elle est rendue possible grâce à une redondance de l'information. Un code est dit parfait s'il ne contient aucune redondance inutile. Le concept correspond à un critère d'optimalité. Un code est dit MDS s'il vérifie un autre critère d'optimalité s'exprimant dans le contexte des codes linéaires.

Il existe de nombreux codes correcteurs. Les sommes de contrôles sont les exemples les plus simples, on peut citer néanmoins aussi des codes cycliques comme des BCH ou ceux de Reed-Solomon. Les codes parfaits sont plus rares, on peut citer par exemple les codes de Hamming ou les codes de Golay binaires de longueur 23 et ternaire de longueur 11.

Contexte

Code correcteur

Les codes correcteurs ont leur source dans un problème très concret lié à la transmission de données. Dans certains cas, une transmission de données se fait en utilisant une voie de communication qui n'est pas entièrement fiable. Les données, lorsqu'elles circulent sur cette voie, sont susceptibles d'être altérées. L'objectif d'un code correcteur est l'apport d'une redondance de l'information de manière que l'erreur puisse être détectée ou corrigée.

Rappelons brièvement la formalisation d'un code. Un message est un mot formé de k lettres prises dans un alphabet A, notons E l'ensemble des messages. Ce message est encodé par une application φ injective en un mot contenant n lettres dans un alphabet A' non nécessairement égal à A. Notons q le cardinal de A' et F l'ensemble d'arrivée de φ. F est l'ensemble des mots formé de n lettres pris dans un alphabet à q éléments, F est donc de cardinal qⁿ. L'ensemble φ(E) est inclus dans F et est appelé code et un élément de cet ensemble un mot du code. La longueur du code correspond à k, le nombre de lettres constituant le message. Ces notations sont utilisés dans tout l'article.

Distance de Hamming

Hyper-cube binaire de dimension quatre.

Un concept essentiel dans la théorie des codes correcteurs est celui de la distance de Hamming. À deux mots du code, elle associe le nombre de lettres qui diffèrent.

• La distance de Hamming entre ramer et cases est 3.

La figure de droite illustre un cas largement répandu dans l'industrie, celui où les lettres de l'alphabet sont binaires. Dans l'exemple choisi, les mots sont composés de quatre lettres. La distance entre 0110 et 1110 est égale à un car il est nécessaire de parcourir un segment du graphique pour joindre les deux mots. On peut aussi remarquer que les deux mots diffèrent seulement par leur première lettre. La même approche montre que la distance entre 0100 et 1001 est égale à trois.

Dans l'exemple de la figure, l'alphabet est un corps fini, il est en effet muni de deux lois : une additive et l'autre multiplicative. Cela confère à l'ensemble une structure d'espace vectoriel. Dans ce cas là, la distance dérive d'une pseudo-norme appelée poids de Hamming et qui associe à un vecteur le nombre de coordonnées non nulles. La distance de Hamming entre deux mots est alors égale au poids de leur différence.

Définition et exemple

Définition

Illustration d'un code parfait.

L'objectif d'un code correcteur est la capacité de détection ou de correction d'erreurs, le moyen utilisé est la redondance (cf code correcteur). Usuellement, on considère un entier t correspondant au nombre d'erreurs maximal que peut entraîner la transmission. Si les boules fermées de centre les mots du code et de rayon t ne s'intersectent pas, alors t erreurs sont corrigibles. Les points en dehors de ces boules entraînent un grossissement inutile de l'espace F. L'idéal est alors que les boules forment une partition de F.

La figure de droite correspond à une telle configuration. Les points du code en vert, sont espacés d'une distance de cinq entre eux. Si la transmission ne produit jamais plus de deux altérations, alors les erreurs sont toutes corrigibles. De plus, il n'existe pas de points en dehors des boules fermées de centre les points du code et de rayon deux, c’est-à-dire de redondance inutile. Les points à une distance de un du code sont en bleu et ceux à une distance de deux en rouge.

En résumé, l'espace est intégralement rempli par les boules fermées de rayon deux et de centre les points du code, de plus elles ont une intersection vide entre elles. Ce concept conduit à la définition suivante :

• Un code linéaire est dit parfait si et seulement s'il existe une valeur t tel que les boules fermées de centre les mots de code et de rayon t forment une partition de l'espace.

Exemples

Cas triviaux

Si la longueur du code est un, c’est-à-dire si l'espace E ne contient qu'une lettre le code dans un alphabet d'une lettre est trivialement parfait. Cependant le seul message pouvant être transmis est toujours la même lettre, ce qui rend le code peu intéressant.

Dans le cas où l'application d'encodage φ est l'identité, alors le code est encore parfait car les boules fermées de centre les points du code et de rayon zéro forment une partition de F, ici égal à E. Le code est encore peu intéressant car seulement zéro erreur peuvent être corrigée. On parle alors encore de code trivial.

Code de répétition

Soit A l'alphabet binaire, constitué des lettres 0 et 1 et considérons le code de répétition de dimension un et de longueur trois. Les messages sont constitués d'une lettre, par exemple 0, les codes d'une triple répétition de la lettre soit 000 dans l'exemple. Comme l'alphabet ne contient que deux lettres, deux au moins sur trois des lettres d'un élément de F sont semblables, en conclusion tout mot de F est à distance de un d'un mot du code. De plus, un mot de F n'est à une distance d'au plus un d'un unique mot du code, ce qui démontre que ce code est parfait. Cependant cette propriété tombe si le code contient plus de deux lettres, en effet il existe des éléments de F constitués de trois lettres différentes et donc à distance de deux de trois mots différents du code et à distance de un d'aucun mot du code.

Code de Hamming

Description du code de Hamming binaire de paramètre [7,4,3]

Les codes correcteurs réellement utilisés dans l'industrie sont plus complexes que les précédents. Les plus simples sont les codes de Hamming et plus particulièrement le code binaire de Hamming de paramètres [7,4,3].

C'est un code de longueur sept, c’est-à-dire que le récepteur reçoit sept bits, de dimension quatre c’est-à-dire qu'une fois décodé, le message contient quatre lettres et la distance minimale entre chaque mot de code est trois.

La figure de droite est une représentation graphique de ce code. Le message est le mot d₁d₂d₃d₄. Le mot du code est constitué de trois sommes de contrôles p₁p₂p₃, puis des quatre lettres du mot du message. La valeur de p_i est égal à zéro si la somme des trois lettres du message incluses dans son cercle sur la figure est paire et un sinon.

On remarque que la somme des éléments de chaque cercle est paire si et seulement si l'élément est un mot du code. De plus, chaque élément de F est à une distance de un d'un mot du code. En conséquence, ce code est parfait et possède une capacité maximale de correction d'une erreur.

Somme de contrôle

Code de longueur deux avec un bit de parité.

Messages = E	Codes = φ(E)
00	000
01	101
10	110
11	011

Un autre exemple plus ambigu est fourni par la somme de contrôle. L'objectif n'est plus ici la correction automatique mais la détection d'une unique erreur. Les deux alphabets sont binaires, les messages sont de longueur deux et le code de dimension trois.

L'encodage consiste à ajouter un bit de parité, qui vaut zéro si la somme des lettres est paires et un dans le cas contraire. La table de correspondance de l'encodage est donnée à droite.

La figure de gauche est une illustration géométrique du code. Elle représente l'ensemble d'arrivé F. Les mots du code sont en vert. Une unique erreur correspond à un déplacement sur le cube le long d'une arête. Dans ce cas, le récepteur reçoit un point noir dont la somme de toutes les lettres est un entier impair. Il est donc possible de déterminer l'existence d'une erreur.

Au sens général de la définition ci-dessus, un code de contrôle n'est pas parfait, les boules de rayon zéro ne contiennent aucun point noir et chaque point noir est dans trois boules de rayon un distincts. En revanche, au sens de la borne de Singleton décrite ci-dessous, pour les codes linéaires, il est MDS.

Cas général

Capacité de correction et distance minimale

Une première question apparaissant pour l'analyse d'un code est la valeur et la signification du paramètre t utilisé dans la définition du code parfait. La valeur t correspond au plus grand entier tel que les boules fermées de rayon t et de centre les mots du code ne s'intersectent pas deux à deux:

$t=\max \left\{r\in \mathbb {N} \;:\;\forall x,x'\in \varphi (E)\quad x\neq x'\Rightarrow B_{r}(x)\bigcap B_{r}(x')=\varnothing \right\}\quad avec\quad B_{r}(x)=\{y\in F:d(x,y)\leq r\}$

Si δ est la distance minimale entre deux mots du code, l'inégalité triangulaire montre que si t est strictement inférieur à δ/2, alors l'intersection des boules fermées de centres les mots du codes et de rayon t ont une intersection vide. En effet, si m un mot de F était élément de deux boules fermées de centre c et c' et de rayon t alors :

$d(c,c')\leq d(c,m)+d(m,c')\leq t+t<\delta \;$

Ce qui implique que c et c' sont égaux par définition de la distance minimale δ.

Réciproquement, montrons que si t est supérieur ou égal à δ/2 alors il existe au moins deux boules fermées de rayon t et de centre deux points du code distincts d'intersection non vide. La fonction distance de Hamming, prend ses valeurs dans un ensemble fini donc le minimum est atteint. Soit c et c' deux mots du code tel que d(c, c') soit égal à δ, où δ désigne la distance minimale. Les deux mots c et c' diffèrent par δ coordonnées. Soit m le mot ayant les mêmes coordonnées que c sauf pour les t premières des δ coordonnées qui diffèrent entre c et c' où m possède les coordonnées de c', m est à une distance de t de c et à une distance inférieure ou égale à t de c', ce qui permet que conclure que:

• La plus grande valeur t tel que les boules fermées de centre les mots du code et de rayon t aient une intersection vide est le plus grand entier strictement inférieur à δ/2.

On remarque de plus, que le plus grand nombre d'erreurs corrigibles de manière certaine est égal à la valeur t. En effet, une erreur n'est corrigible de manière certaine seulement s'il existe un unique mot du code proche du message transmis, ce qui correspond à la définition du paramètre t.

Borne de Hamming

Une approche pour déterminer le nombre de redondances nécessaires à la correction de t erreurs est le dénombrement. Il est possible de calculer le cardinal de l'espace F, celui d'une boule fermée de rayon t pour la distance de Hamming et donc le nombre maximal de messages transmissibles par le code avec une capacité de correction de t erreurs.

L'espace F est formé par des mots de n lettres pris dans un alphabet contenant d lettres. Il contient donc d ⁿ éléments.

Calculons le nombre de points à une distance de Hamming i d'un point c donnée. L'ensemble des points à une distance de i de c est celui contenant les mots ayant i coordonnées différentes de c. À chaque point de l'ensemble correspond un sous-ensemble de i éléments choisi parmi n. Le nombre d'ensembles de cette nature correspond au i-ème coefficient binomial de rang n. Pour chaque élément de l'ensemble il existe d - 1 lettres possibles. On en déduit, si V_t désigne le cardinal d'une boule fermée de rayon t :

$V_{t}=\sum _{i=0}^{t}{n \choose i}(d-1)^{i}$

Pour que le code puisse corriger t erreurs, ces boules doivent être disjointes. Le cardinal de leur réunion est égal à M.V_t, où M désigne le cardinal du code. Or, cette réunion ne peut pas avoir un cardinal strictement supérieur à celui de l'espace F, ce qui donne lieu à la définition et à la proposition suivante :

• Si M désigne le cardinal du code, alors la majoration suivante est vérifiée, elle porte le nom de borne de Hamming.

$M\leq {\frac {d^{n}}{V_{t}}}\quad avec\quad V_{t}=\sum _{i=0}^{t}{n \choose i}(d-1)^{i}$

Un code est dit parfait si et seulement si les boules fermées de centres les mots du code et de rayon t forment une partition de F, ce qui donne lieu à la proposition suivante :

• Un code est parfait si et seulement si la borne de Hamming est atteinte.

Cas linéaire

Code linéaire

Un code linéaire dispose d'une structure algébrique plus riche que celle du cadre général des codes correcteurs. Les alphabets A et A' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps F₂ ou l'une de ses extensions finies. Ce corps correspond à l'alphabet binaire dont les tables d'addition et de multiplication sont données ci-dessous:

+   0   1   0   0  1  1   1  0

.   0   1   0   0  0  1   0  1

Les ensembles E et F sont naturellement munis d'une structure d'espace vectoriel de dimension respectives k et n. Si F_d désigne le corps fini (cf l'article corps fini) de cardinal d où d est une puissance d'un nombre premier p, alors l'espace vectoriel F est généralement identifié à F_dⁿ.

La distance entre deux points de F correspond au nombre de coordonnées non nulles de la différence entre les deux points, dans la base canonique, elle dérive donc d'une pseudo-norme. Un code se décrit par trois paramètres, noté [n, k, δ], n est la dimension du code, k la longueur du code et δ la distance minimale entre deux mots du code. Ces notations sont utilisées dans le reste de l'article.

Enfin, l'application d'encodage φ est choisie linéaire, le code est donc un sous-espace vectoriel.

Matrice de contrôle

Il existe une application linéaire ayant pour noyau le code. Sa matrice est appelée H, ici elle est identifiée avec son application linéaire. Dans le cas des codes parfaits, elle possède une propriété forte :

• Si le code est parfait, la restriction de H à la boule fermée de centre un mot du code et de rayon t est bijective.

Les images de H que l'on appelle syndromes sont en bijection avec les erreurs possibles du code. Cette propriété offre une technique de décodage simple, appelée décodage par syndrome. De plus, elle offre une condition nécessaire et suffisante pour caractériser un code parfait :

• La majoration suivante est toujours vérifiée, elle est une égalité si et seulement si le code est parfait :

$V_{t}=\sum _{i=0}^{t}{n \choose i}(d-1)^{i}\leq d^{n-k}$

Cette propriété est restrictive, elle permet de trouver une condition nécessaire pour les paramètres des codes.

Code de Hamming

Recherchons tous les codes parfaits de distance minimale δ égale à trois. La valeur de t est alors un et l'égalité de la majoration précédente prend la forme si m désigne la valeur n - k :

$1+n.(d-1)=d^{m}\quad donc\quad n={\frac {d^{m}-1}{d-1}}\quad et\;k={\frac {d^{m}-1}{d-1}}-m\quad car\;k=n-m$

De fait, il est possible de construire tous ces codes, ils portent le nom de code de Hamming.

• Les seuls codes de distance minimale égale à trois sont les codes de Hamming. Ils sont décrits par les paramètres suivants, si m est un entier strictement positif et d est le cardinal du corps fini alphabet :

$\left[{\frac {d^{m}-1}{d-1}},{\frac {d^{m}-1}{d-1}}-m,3\right]$

Si m est égal à deux et d à deux on retrouve le code de répétition de paramètres [3,1,3]. Si m est égal à trois et d à deux, on retrouve les paramètres [7,4,3] de l'exemple précédent.

Codes de Golay

Pour t = 2, l'équation devient:

$1+n\cdot (d-1)+{\frac {n\cdot (n-1)}{2}}\cdot (d-1)^{2}=d^{m}$

L'unique solution est obtenue pour d = 3, n = 11 et m = 5, alors k est égal à 6, on obtient un code appelé le code de Golay ternaire de paramètre [11, 6, 5]. La boule unité, ainsi que l'espace des syndromes contient 243 éléments.

Pour t = 3 l'équation se complique, elle devient :

$1+n\cdot (d-1)+{\frac {n\cdot (n-1)}{2}}\cdot (d-1)^{2}+{\frac {n\cdot (n-1)\cdot (n-2)}{6}}\cdot (d-1)^{3}=d^{m}$

La solution est encore unique, elle est obtenue pour d = 2, n = 23 et m = 11, alors k est égal à 12, on obtient un code appelé le code de Golay binaire de paramètre [23, 12, 7]. La boule unité, ainsi que l'espace des syndromes contient 2048 éléments.

Il n'existe pas d'autre code linéaire parfait.

Borne de Singleton

Les codes parfaits linéaires sont trop peu nombreux pour satisfaire les besoins de l'industrie, une autre majoration, moins contraignante est souvent considérée :

• La majoration suivante est vérifiée pour tous les codes linéaires. Elle se nomme borne de Singleton :

$n-k\geq \delta -1$

En effet, Soit p la projection de F sur l'espace vectoriel engendré par les k - 1 premiers vecteurs de la base canonique, parallèlement à l'espace vectoriel engendré par les vecteurs restants. L'application poφ est nécessairement non injective car son image est un espace vectoriel de dimension strictement inférieure à celle de E. Il existe donc au moins deux mots du code distincts ayant les mêmes k - 1 premières coordonnées. Ces deux mots du code diffèrent par au plus n - k + 1 coordonnées, ce qui démontre la proposition.

Une définition est associée au cas où la borne est atteinte :

• Le code est MDS pour maximum distance séparable si et seulement si la borne de Singleton est atteinte.

Cette borne correspond à un code linéaire optimal pour les paramètres n et k choisis, c’est-à-dire qu'un code de dimension n et de longueur k est MDS s'il n'existe pas d'autres codes de même longueur et de même dimension ayant une distance minimale plus grande. Les codes de Reed-Solomon atteignent cette borne. Il en est de même pour les codes construits à l'aide d'une somme de contrôle, en revanche, ils ne sont pas parfaits car la distance minimale est égale à deux et un code parfait possède toujours une distance minimale impaire. Le code de Hamming binaire de paramètres [7, 4, 3] n'atteint pas la borne de Singleton et n'est donc pas MDS, mais il est parfait, la borne de Singleton n'est donc pas atteignable pour un code de dimension 4 et de longueur 7.

Voir aussi

Article connexe

• Matrice MDS

Liens externes

• Code correcteur C.I.R.C par J.P. Zanotti, université de Toulon
• Code Linéaire par G. Zemor, université Bordeaux I
• Cours de code par Christine Bachoc, université Bordeaux I
• (en) Jacksum (un programme Java open source permettant de calculer de nombreux contrôles par redondance)

Bibliographie

• (en) Jessie MacWilliams et Neil Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 (ISBN 978-0-44485009-6)
• A. Spătaru, Fondements de la théorie de la transmission de l'information, PPUR, 1987 (ISBN 978-2-88074133-4)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions], chapitres 6 à 13 (éd. Cassini, 2008)
• B. Martin, Codage, cryptologie et applications, PPUR, 2004 (ISBN 978-2-88074569-1)
• J.-G. Dumas, J.-L. Roch, E. Tannier et S. Varrette, Théorie des codes (Compression, cryptage, correction), Dunod, 2007 (ISBN 978-2-10050692-7) [présentation en ligne]