Code parfait et code MDS - Définition

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 dimension sept, c’est-à-dire que le récepteur reçoit sept bits, de longueur 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é

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.