Les codes correcteurs d'erreurs expliqués

Aucun canal n'est parfait. Les rayons cosmiques inversent des bits en mémoire, les rayures effacent des parties d'un disque et les signaux radio s'affaiblissent. Au lieu d'espérer que tout ira bien, les systèmes numériques ajoutent de la redondance de manière astucieuse, afin que le destinataire puisse déduire ce qui a été envoyé même quand une partie arrive erronée. Les mathématiques de ces codes, nées à la fin des années 1940, protègent discrètement presque chaque bit que nous stockons ou envoyons.

Trois cercles qui se chevauchent contenant les sept bits d'un mot de code de Hamming, un cercle mis en évidence là où un contrôle de parité échoue
Trois cercles qui se chevauchent contenant les sept bits d'un mot de code de Hamming, un cercle mis en évidence là où un contrôle de parité échoue

Détecter les erreurs grâce à la parité

La protection la plus simple est un unique bit de parité : on ajoute un 1 ou un 0 pour que le nombre total de 1 soit pair. Si un bit s'inverse en chemin, le compte devient impair et le destinataire sait que quelque chose s'est mal passé. La parité ne peut pas dire quel bit est erroné, et deux inversions s'annulent sans être remarquées, mais elle est bon marché et a été utilisée pendant des décennies dans les mémoires et les liaisons série. Détecter une erreur n'est toutefois que la moitié du travail : il faut ensuite renvoyer les données.

Corriger par la répétition

Pour corriger une erreur sans redemander, le destinataire a besoin d'assez de redondance pour la mettre en minorité. Envoyer chaque bit trois fois, 000 ou 111, lui permet de suivre la majorité : une inversion dans un triplet est corrigée. Le prix est élevé : trois bits pour chaque bit de données, et deux inversions dans le même triplet l'emportent quand même. La question qui a lancé la théorie des codes était de savoir si l'on pouvait faire mieux.

Le code de Hamming

En 1947, Richard Hamming travaillait aux Bell Labs sur un calculateur à relais qui lisait ses programmes sur des cartes perforées. Lorsque la machine trouvait une erreur pendant le week-end, elle s'arrêtait tout simplement, et Hamming ne retrouvait le lundi que des calculs perdus. Si une machine peut détecter une erreur, se demanda-t-il, pourquoi ne pourrait-elle pas la localiser et la corriger ? Sa réponse, publiée en 1950, envoie 4 bits de données sous forme de 7. Trois bits de parité, aux positions 1, 2 et 4, contrôlent chacun un groupe différent de positions qui se chevauchent, choisi de sorte que chaque erreur unique fasse échouer une combinaison unique de contrôles.

Le syndrome

Le destinataire recalcule les trois contrôles. S'ils réussissent tous, le mot est accepté. Si certains échouent, écrire les contrôles en échec sous forme de chiffres binaires, avec le contrôle 4 comme chiffre de poids fort, donne un nombre de 1 à 7 : le syndrome, qui est exactement la position du bit inversé. Le rétablir restaure le mot de code. L'astuce fonctionne parce que les positions sont numérotées de sorte que l'écriture binaire de chacune énumère les contrôles auxquels elle appartient, ce qui explique pourquoi le code paraît si ordonné lorsqu'on le dessine sous forme de trois cercles qui se chevauchent.

La distance de Hamming

La distance de Hamming entre deux mots est le nombre de positions où ils diffèrent. Dans le code (7,4), deux mots de code sont toujours à une distance d'au moins 3. Un mot comportant une erreur reste à distance 1 du mot de code envoyé et à au moins 2 de tous les autres, si bien que le décodage vers le mot de code le plus proche le corrige. En général, un code dont les mots de code sont éloignés d'au moins d détecte d − 1 erreurs et en corrige (d − 1)/2, arrondi à l'entier inférieur. Ajouter un bit de parité global porte la distance à 4, ce qui donne le code étendu qui corrige une erreur et en détecte deux.

La limite de Shannon

En 1948, deux ans avant l'article de Hamming, Claude Shannon démontra un théorème saisissant. Tout canal bruité possède une capacité, et l'on peut transmettre des données à n'importe quel débit inférieur avec aussi peu d'erreurs qu'on le souhaite, en utilisant des codes suffisamment longs ; au-delà, les erreurs sont inévitables. Shannon montra que de tels codes existent, mais pas comment les construire. Trouver des codes pratiques proches de sa limite a pris un demi-siècle, des codes de Reed-Solomon en 1960 aux turbocodes en 1993 et à la redécouverte des codes LDPC (low-density parity-check, à matrice de parité creuse).

Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.
Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.

Des codes tout autour de nous

Les codes de Reed-Solomon permettent aux CD de se lire malgré les rayures et aux codes QR d'être scannés avec jusqu'à 30 % du symbole endommagé. La mémoire des serveurs utilise des codes de Hamming étendus pour corriger les bits isolés inversés par les rayons cosmiques. Les images des planètes extérieures prises par Voyager étaient protégées par des codes de Golay, puis de Reed-Solomon, et les codes LDPC et polaires de la 5G et du Wi-Fi exploitent presque chaque bit que le canal permet. Même le code-barres d'un livre et le dernier chiffre d'un numéro de compte bancaire sont de simples codes détecteurs d'erreurs.

À vous d'explorer

Ouvrez le simulateur de code correcteur d'erreurs pour coder quatre bits de données de votre choix avec le code de Hamming (7,4), inverser des bits en cliquant dessus dans les cercles ou dans la rangée, et voir les cercles en échec et le syndrome désigner l'erreur avant que le décodeur ne la répare. Activez le bit de parité supplémentaire pour voir les erreurs doubles détectées, et envoyez un message à travers un canal bruité pour comparer ce qui arrive avec et sans le code.

Questions fréquemment posées

Quelle est la différence entre détection et correction d'erreurs ?

La détection indique seulement au destinataire que quelque chose ne va pas : il doit alors redemander les données ; un bit de parité ou une somme de contrôle fait cela. La correction permet au destinataire de reconstituer l'original sans redemander, ce qui exige davantage de redondance. Les systèmes qui ne peuvent pas redemander, comme une sonde spatiale à des millions de kilomètres ou un DVD, comptent sur la correction.

Pourquoi ne pas simplement tout envoyer deux fois ?

Deux copies montrent qu'une erreur s'est produite, mais pas laquelle est la bonne, et elles doublent le coût. Trois copies permettent un vote à la majorité mais le triplent. Le code de Hamming corrige une erreur unique par bloc de sept avec moins du double de bits, et les codes plus longs font bien mieux.

Qui était Richard Hamming ?

Un mathématicien américain, 1915-1998, qui a travaillé sur le projet Manhattan puis pendant trente ans aux Bell Labs. Outre ses codes, il est connu pour la fenêtre de Hamming en traitement du signal, pour la distance de Hamming et pour sa conférence « You and Your Research ». Il a reçu le prix Turing en 1968.

Un code peut-il corriger n'importe quel nombre d'erreurs ?

Seulement avec assez de redondance. Un code peut corriger jusqu'à (d − 1)/2 erreurs par bloc, où d est la distance minimale entre mots de code, et des codes plus longs avec davantage de bits de contrôle atteignent un d plus grand. Le théorème de Shannon fixe la limite ultime : aucun code ne peut dépasser la capacité du canal.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le simulateur de code correcteur d'erreurs