Code parfait et code MDS - Définition

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 :

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 :

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 :

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:

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 :

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é :

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

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 7 et de longueur 4.