Codes correcteurs d'erreurs

Un bit stocké sur un disque, transmis par une fibre ou gravé sur un disque optique se retourne parfois tout seul. Le chiffrement ne protège en rien contre cela : un seul bit retourné dans un message chiffré produit un déchiffrement faux, et rien ne le signale.

Ce chapitre traite ce second problème avec la même arithmétique que le précédent et une intention opposée. La cryptographie cache de l'information à un adversaire ; un code correcteur en ajoute, délibérément, pour que le message survive au bruit. Ajouter de la redondance est facile ; en ajouter juste assez, et savoir exactement ce qu'elle achète, ne l'est pas.

Le problème, et ce qui ne le résout pas

Une ligne de transmission retourne des bits. Le taux dépend du support, mais il n'est jamais nul : une liaison optique perd un bit sur mille milliards, une mémoire vive en perd bien davantage sous rayonnement, un disque optique rayé en perd par paquets.

Trois réponses viennent à l'esprit, et deux ne marchent pas.

Répéter le message trois fois et prendre la majorité fonctionne, et coûte deux tiers du débit. C'est le code le plus simple qui corrige, et sa faiblesse n'est pas la robustesse mais le prix.

Renvoyer le message quand il est faux suppose de savoir qu'il est faux, donc un code détecteur, et suppose surtout un canal de retour. Il n'y en a pas quand on lit un disque gravé il y a dix ans, ni quand on reçoit une sonde spatiale.

Chiffrer ne fait rien du tout contre le bruit. Pire : un bon chiffrement propage l'erreur, un bit retourné dans le chiffré corrompant un bloc entier une fois déchiffré.

Détecter et corriger sont deux services différents

Détecter répond à « ce message est-il intact ? » et coûte peu. Corriger répond à « quel était le message ? » et coûte beaucoup plus.
Le choix ne se fait pas sur la robustesse souhaitée, mais sur l'existence d'un canal de retour. Avec un retour, détecter suffit et l'on redemande. Sans retour, il faut corriger sur place, et la redondance doit être payée d'avance.

La distance de Hamming

Définition

La distance de Hamming entre deux mots de même longueur est le nombre de positions où ils diffèrent.

Entre 1011010 et 1001110, les positions 3 et 5 diffèrent : la distance vaut 2.

Cette distance est l'outil central du sujet, parce qu'une erreur de transmission déplace le mot reçu à une distance égale au nombre de bits retournés. Un bit faux donne un mot à distance 1 du mot émis, deux bits faux un mot à distance 2.

Distance minimale d'un code

La distance minimale $d$ d'un code est la plus petite distance entre deux mots de code distincts.

Tout découle de ce seul nombre.

Ce que la distance minimale achète

Un code de distance minimale

d

détecte jusqu'à

d - 1

erreurs, et corrige jusqu'à

\lfloor (d-1)/2 \rfloor

erreurs.
La raison est géométrique. Pour détecter, il suffit qu'un mot altéré ne tombe jamais sur un autre mot de code : il faut donc moins de

d

erreurs. Pour corriger, il faut en plus que le mot reçu reste plus proche du mot émis que de tout autre, ce qui divise la marge par deux.

Un code de distance 3 corrige donc une erreur et en détecte deux. Un code de distance 4 corrige toujours une seule erreur, mais en détecte trois : le bit supplémentaire n'a pas acheté de correction, il a acheté de la détection.

Le bit de parité, et ses limites

Le code le plus simple ajoute un bit valant la somme modulo 2 des bits de données, c'est-à-dire 1 si le nombre de 1 est impair.

Sa distance minimale vaut exactement 2 : deux mots de code diffèrent d'au moins deux positions, puisque changer un seul bit de données change aussi le bit de parité. Il détecte une erreur et n'en corrige aucune.

Un nombre pair d'erreurs passe inaperçu

Deux bits retournés laissent la parité inchangée, et le contrôle déclare le mot intact. Le bit de parité n'attrape donc que les erreurs en nombre impair, ce qui est exactement la moitié des cas quand les erreurs sont indépendantes.
Sur un canal où les erreurs arrivent par rafales, ce qui est le cas d'un support rayé ou d'une interférence, il est bien pire que cela : une rafale de deux bits est plus probable qu'un bit isolé, et elle est invisible.

Le code de Hamming à sept bits

Le premier code qui corrige sans tout répéter date de 1950, et il tient sur sept bits : quatre de données, trois de contrôle.

Le principe est de placer les bits de contrôle aux positions qui sont des puissances de deux, soit 1, 2 et 4, et de faire porter à chacun la parité d'un sous-ensemble précis de positions.

Bit de contrôle	Position	Surveille les positions
$c_1$	1	1, 3, 5, 7
$c_2$	2	2, 3, 6, 7
$c_4$	4	4, 5, 6, 7

Le choix n'a rien d'arbitraire : le bit de contrôle en position $2^k$ surveille toutes les positions dont l'écriture binaire porte un 1 au rang $k$ .

Le syndrome donne la position de l'erreur, pas seulement son existence

À la réception, les trois parités sont recalculées. Chacune vaut 0 si elle est respectée, 1 sinon, et les trois chiffres lus ensemble forment un nombre binaire : le syndrome.
Ce nombre vaut 0 si le mot est intact, et sinon il vaut exactement la position du bit fautif. C'est toute l'élégance de la construction : la position se lit, elle ne se cherche pas.

Ce code a une distance minimale de 3. Il corrige donc une erreur et en détecte deux, et son rendement vaut $4/7$ , soit environ 57 % du débit consacré aux données.

Le rendement, et ce qu'il faut en faire

Rendement d'un code

Le rendement est le rapport du nombre de bits de données au nombre de bits transmis. Un rendement de 1 signifie aucune redondance, donc aucune protection.

Corriger une seule erreur ne demande pas le même prix selon la longueur du mot. Le nombre de bits de contrôle croît comme le logarithme de la longueur, alors que le nombre de bits de données croît comme la longueur.

Longueur	Bits de contrôle	Bits de données	Rendement
7	3	4	0,571
15	4	11	0,733
31	5	26	0,839
63	6	57	0,905

Un meilleur rendement n'est pas une meilleure protection

Les quatre codes du tableau corrigent tous une seule erreur. Le code long a un meilleur rendement, et il est plus fragile : une erreur sur soixante-trois bits est bien plus probable qu'une erreur sur sept, et la deuxième erreur n'est pas corrigée.
Le choix se fait donc sur le taux d'erreur du canal, jamais sur le rendement seul. Un canal propre autorise des mots longs ; un canal bruité impose des mots courts, et l'on paie la redondance.

Le CRC : détecter beaucoup, ne corriger rien

Les protocoles réseau n'emploient presque jamais de code correcteur : ils ont un canal de retour, et il leur suffit de détecter pour redemander. Ils emploient un contrôle de redondance cyclique.

Le principe est une division polynomiale. Le message est vu comme un polynôme à coefficients dans $\{0, 1\}$ , on le divise par un polynôme générateur fixé, et le reste de cette division devient le champ de contrôle. C'est exactement la division euclidienne du chapitre sur l'arithmétique, transportée sur les polynômes.

Ce qu'un CRC de 32 bits garantit

Il détecte toutes les rafales d'erreurs de longueur inférieure ou égale à 32 bits, ce qui couvre la quasi-totalité des dégradations réelles d'une ligne. Ce n'est pas une probabilité, c'est une certitude.
Au-delà, il laisse passer une erreur avec une probabilité de

2^{-32}

, soit environ deux chances sur dix milliards. Et il ne corrige rien du tout : il dit que le paquet est abîmé, pas ce qu'il contenait.

Un CRC n'est pas une signature

Il détecte les erreurs accidentelles, pas les modifications délibérées. Fabriquer un message différent ayant le même CRC est un exercice de quelques lignes, puisque l'opération est publique et sans clé.
C'est exactement la distinction du chapitre précédent entre intégrité contre le bruit et intégrité contre un adversaire. La première appelle un CRC, la seconde un code d'authentification à clé. Les confondre produit un système qui ne protège pas de ce qu'on croyait.

À calculer soi-même

Un code se juge par trois nombres : sa distance minimale, ce qu'elle permet, et ce qu'elle coûte.

Distance, correction et rendement

1.
Quelle est la distance de Hamming entre 1011010 et 1001110 ?
2.
Un code a une distance minimale de 3. Combien d'erreurs corrige-t-il ?
3.
Combien d'erreurs ce même code détecte-t-il ?
4.
Combien d'erreurs un code de distance minimale 7 corrige-t-il ?
5.
Le code de Hamming à sept bits porte quatre bits de données. Quel est son rendement ?
6.
Un code de longueur 31 corrigeant une erreur demande cinq bits de contrôle. Quel est son rendement ?
7.
Combien de mots de code le code de Hamming à sept bits possède-t-il, parmi les 128 mots de sept bits ?
8.
Quelle proportion des mots de sept bits sont des mots de code, en pour cent ?

La dernière réponse explique tout le reste. Seuls 12,5 % des mots de sept bits sont valides, et les sept huitièmes restants sont autant de mots que le décodeur reconnaîtra comme fautifs. La redondance n'est rien d'autre que cela : rendre la plupart des messages possibles illégaux, pour qu'une altération se voie.

Où la démarche dérape

Un raisonnement sur la robustesse d'un code, mené sur le bon nombre et la mauvaise formule.

Une distance qu'on croit entièrement convertie en correction

Une seule étape est fausse. Désigner laquelle.

Un code a une distance minimale $x$ . On cherche le nombre d'erreurs qu'il peut corriger.

Vérification

Vérification rapideon peut se reprendre

1.Que garantit exactement un bit de parité ?

2.Que vaut le syndrome dans le code de Hamming à sept bits ?

3.Un code de distance minimale 4 corrige combien d'erreurs ?

4.Pourquoi les protocoles réseau emploient-ils un CRC plutôt qu'un code correcteur ?

Exercices type

Pourquoi la correction divise-t-elle la marge par deux, alors que la détection ne le fait pas ?

Détecter demande seulement que le mot reçu ne soit aucun mot de code. Il suffit donc que le déplacement reste strictement inférieur à la distance minimale.

Corriger demande en plus de savoir lequel des mots de code était le bon, donc que le mot reçu reste plus proche du mot émis que de tout autre. Entre deux mots de code séparés de $d$ , le point d'équidistance est au milieu : la marge utilisable n'est que la moitié, d'où la partie entière de $(d-1)/2$ .

Trois répétitions et vote majoritaire : quelle est la distance minimale, et quel est le rendement ?

Deux mots de code distincts diffèrent sur les trois copies de chaque bit changé, donc la distance minimale vaut 3. Le code corrige une erreur, ce que le vote majoritaire réalise directement.

Son rendement vaut 1/3, contre 4/7 pour le code de Hamming à sept bits qui corrige exactement autant d'erreurs. C'est la mesure de ce que la construction de Hamming fait gagner : la même protection pour presque deux fois moins de redondance.

Un canal retourne un bit sur mille. Vaut-il mieux des mots de 7 bits ou de 63 bits ?

Les deux codes corrigent une seule erreur. Ce qui les sépare est la probabilité d'en subir deux dans le même mot.

Sur sept bits, subir deux erreurs est très improbable. Sur soixante-trois bits, c'est neuf fois plus long, donc bien plus fréquent, et une deuxième erreur n'est pas corrigée : elle est en outre mal corrigée, puisque le décodeur choisit le mot de code le plus proche et se trompe.

Le mot long a un meilleur rendement et une protection réelle inférieure. Le choix se fait sur le taux d'erreur du canal.

Un CRC peut-il remplacer une signature ?

Non, et la confusion est fréquente. Un CRC est une opération publique et sans clé : n'importe qui peut recalculer le CRC d'un message modifié, ou fabriquer un message ayant un CRC donné.

Il protège contre le bruit, qui ne choisit pas ses altérations. Il ne protège en rien contre un adversaire, qui les choisit précisément. Contre lui, il faut un code d'authentification à clé, ce que le chapitre sur la cryptographie appelle l'intégrité contre un adversaire.

Pourquoi les bits de contrôle sont-ils placés aux positions 1, 2 et 4 ?

Parce que ce sont les puissances de deux, et que chaque position binaire correspond à exactement un bit de contrôle. La position 5 s'écrit 101, donc elle est surveillée par les bits de contrôle 1 et 4 et par aucun autre.

C'est ce qui fait fonctionner le syndrome : chaque position a une combinaison de surveillants unique, et cette combinaison est précisément son écriture binaire. Placer les bits de contrôle ailleurs briserait la correspondance et obligerait à chercher la position dans une table.

La méthode

Déterminer s'il existe un canal de retour avant tout choix. Avec retour, détecter suffit ; sans retour, il faut corriger et payer la redondance.
Calculer la distance minimale du code, puisque tout en découle.
Appliquer les deux formules : détection jusqu'à $d - 1$ , correction jusqu'à $\lfloor (d-1)/2 \rfloor$ . Ne jamais les confondre.
Calculer le rendement, et le confronter au taux d'erreur du canal. Un rendement élevé sur un canal bruité est une protection illusoire.
Pour Hamming, lire le syndrome comme un nombre binaire : il donne la position, et zéro signifie intact.
Distinguer le bruit de l'adversaire. Un CRC répond au premier et à rien d'autre.

Synthèse

Détecter et corriger sont deux services de coûts très différents. Le canal de retour décide lequel est nécessaire.
La distance de Hamming compte les positions où deux mots diffèrent. Une erreur déplace le mot d'une position par bit retourné.
Un code de distance minimale $d$ détecte $d - 1$ erreurs et en corrige $\lfloor (d-1)/2 \rfloor$ .
Le bit de parité a une distance de 2 : il détecte une erreur, n'en corrige aucune, et laisse passer tout nombre pair d'erreurs.
Le code de Hamming à sept bits a une distance de 3, corrige une erreur, et son syndrome donne directement la position fautive.
Le rendement croît avec la longueur du mot, et la protection réelle décroît : le choix se fait sur le taux d'erreur du canal.
Un CRC détecte toutes les rafales jusqu'à sa longueur, ne corrige rien, et ne protège pas contre un adversaire.
La redondance consiste à rendre la plupart des messages possibles illégaux, pour qu'une altération se voie.

Et ensuite

Détecter une erreur, la localiser, et décider que faire du message : ces opérations se décrivent comme un parcours de structure. Graphes et coloration referme le parcours sur les structures discrètes, et sur le fait que la difficulté d'un problème n'est jamais dans le problème seul, mais dans le couple problème-structure.