Code correcteur - Définition

Exemples de code en blocs

Code de répétition

Un exemple simple est celui du code de répétition. La cas étudié ici est celui d'un code binaire, c’est-à-dire que les deux alphabets A et A' sont confondus et égaux à {0,1}. La longueur du code est égale à un et la dimension à trois.

L'application φ est définie sur les deux valeurs: 0 et 1, par une triple définition du message. De manière formelle, on obtient :

Si une unique altération se produit, alors un système de vote permet de retrouver le message d'origine. Ce code correcteur possède l'avantage de non seulement détecter une erreur, mais aussi de permettre une correction automatique. En revanche, il est cher, c’est-à-dire que sa dimension est élevée par rapport à la longueur des mots transmis.

Somme de contrôle

Code de longueur deux avec un bit de parité

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 paire et un sinon. 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ée 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.

En revanche, un point noir est toujours à proximité de trois points verts, le récepteur ne dispose donc d'aucun moyen pour une correction automatique.

Cette technique est généralisable à d'autres alphabets et pour des codes de longueurs quelconques. Elle est économique, c'est la raison pour laquelle elle est largement utilisée. En revanche, et à la différence de l'exemple précédent, la correction impose une nouvelle transmission.

Formalisation du problème

Alphabet

Afin de préciser les questions que se pose la théorie des codes, et les problèmes qu'elle rencontre, l'article considère le cas d'un canal discret. L'information à transmettre peut être vue comme une suite x de symboles pris dans un ensemble fini (il s'agit le plus souvent de bits, donc de 0 et de 1).

• Un alphabet est un ensemble fini non vide, ses éléments sont appelés lettres ou symboles.
• Un message ou un mot est une suite à valeur dans un alphabet, il correspond à une suite de lettres.

L'objectif d'un code correcteur est la transmission fiable d'un message. Dans cet article les alphabets sont notés A ou A', le cardinal d'un alphabet est noté q, et un message m.

Code en bloc

Dans le cas général, les messages à transmettre n'ont pas de longueur fixe. Cette situation existe, par exemple, pour une communication téléphonique. En revanche, il est plus simple de développer un code correcteur pour des messages d'une longueur fixe.

La solution utilisée consiste à segmenter la difficulté. Dans un premier temps, est traité le cas d'un message de longueur fixe. Pour le cas général, une solution simple consiste à concaténer une suite de blocs. La méthode la plus répandue, car la plus efficace est celle du code convolutif.

• La longueur d'un message désigne le nombre de lettres qu'il contient.
• Un code en bloc est un code correcteur traitant des messages de longueur fixe.

Dans la suite de l'article, la longueur d'un message est noté k. L'ensemble des messages est noté E et son cardinal M. M est un entier inférieur ou égal à q^k.

Encodage

Comme le montre le paragraphe redondance et fiabilité, il n'est pas toujours judicieux de transmettre le message m. L'ajout d'une redondance peut être pertinente. Pour répondre à cet objectif, il existe une fonction φ injective de E dans un ensemble F, la transmission a lieu sur φ(m) et non sur m. L'injectivité est nécessaire, car sinon deux messages distincts ne seraient plus distinguables par le récepteur. F est l'ensemble des suites finies de longueur n un entier strictement positif à valeur dans A' un alphabet. Dans le cas général l'alphabet de F diffère de celui de E.

Avant sa transmission, le message est encodé, c'est-à-dire qu'il est transformé en une autre suite y=φ(x) de symboles. Ensuite, y est transmis par un canal bruité qui va, éventuellement le modifier en y'. Pour terminer, un décodeur essaie de retrouver le message x à partir de y'. Il est théoriquement équivalent de rechercher y, puisque l'encodage est une injection. Lorsque y diffère de y', on parle d'erreur(s) ou d'altération(s).

• L'application φ de E dans F est appelée encodage.
• La longueur n des suites de F est appelée dimension du code ou simplement dimension.
• L'image φ(E), sous-ensemble de F est appelée code.
• Un mot du code est un élément du code.