Codes correcteurs d'erreurs

Combien de bits ajouter à un relevé qu'on ne pourra jamais redemander ?

Une bouée de mesure ancrée au large envoie vers la côte, toutes les dix minutes, un relevé de quatre bits : la hauteur des vagues, codée de 0 à 15. Un bit sur mille arrive retourné, et la bouée n'écoute rien : impossible de lui redemander un relevé. Combien de bits ajouter à chaque relevé, et qu'achètent-ils exactement ? La réponse chiffrée vient à la fin du chapitre.

Le problème est général. Un bit stocké sur un disque, transmis par une fibre ou par radio se retourne parfois tout seul. Le chiffrement seul n'y peut rien : un bit retourné dans un message chiffré donne un déchiffrement faux. Une signature ou un code d'authentification le signalerait, sans pouvoir rendre le message.

Le chapitre sur la cryptographie protégeait un message contre un adversaire ; celui-ci le protège contre le bruit, avec la même arithmétique et une intention opposée. La cryptographie cache de l'information ; 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.

Travailler seul

Chaque cadre de calcul, chaque quiz et les questions à déplier sont précédés d'un rappel de cours : la notion, sa formule et un petit exemple résolu. Le lire avant de répondre. Tout se calcule à la main ; le seul programme Python du chapitre, replié et facultatif, vérifie ce qui a été fait à la main, et il n'y a rien à y écrire.

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, et une liaison radio que perturbe un moteur voisin en perd plusieurs d'un coup, par paquets.

Trois réponses viennent à l'esprit : la première marche mais coûte cher, la deuxième ne marche que dans certains cas, la troisième ne marche pas du tout.

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 relit un disque gravé il y a dix ans, ni quand la bouée de l'introduction émet sans rien écouter. Vers une sonde spatiale lointaine, le retour existe, mais une demande met des heures à lui parvenir.

Chiffrer ne fait rien du tout contre le bruit. Pire : selon la façon dont il est employé, un chiffrement peut propager l'erreur, un seul bit retourné dans le chiffré corrompant tout un bloc du message 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 premier critère n'est pas la robustesse souhaitée, mais l'existence d'un canal de retour. Avec un retour, détecter suffit le plus souvent, et l'on redemande. Sans retour, il faut corriger sur place, et la redondance doit être payée d'avance.

La distance de Hamming

Rappel de cours : la distance de Hamming

La distance de Hamming entre deux mots de même longueur est le nombre de positions où ils diffèrent. Chaque bit retourné en chemin éloigne le mot reçu de 1 du mot émis : $k$ bits retournés le placent à distance $k$ .

Exemple résolu, entre 1011010 et 1001110, comparés position par position :

Position	1	2	3	4	5	6	7
`1011010`	1	0	1	1	0	1	0
`1001110`	1	0	0	1	1	1	0

Seules les positions 3 et 5 diffèrent : la distance vaut 2.

Compter les positions qui diffèrent

1.
Quelle est la distance de Hamming entre 1100 et 1010 ?
2.
Quelle est la distance entre 0000 et 1111 ?
3.
Quelle est la distance entre 10110 et 10110 ?
4.
Un mot de huit bits est émis, trois bits se retournent en chemin. À quelle distance du mot émis se trouve le mot reçu ?

Cette distance est l'outil central du sujet, parce qu'une erreur de transmission déplace le mot reçu : il s'écarte du mot émis d'autant de positions que de bits retournés.

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, ou corrige jusqu'à $\lfloor (d-1)/2 \rfloor$ erreurs, c'est-à-dire la partie entière de $(d-1)/2$  : 1 pour $d = 3$ ou $d = 4$ , 2 pour $d = 5$ .
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, le décodeur remplace le mot reçu par le mot de code le plus proche. Il retrouve le bon à condition que le mot reçu reste plus proche du mot émis que de tout autre, ce qui divise la marge par deux.

Le code de répétition triple, qui envoie 000 pour 0 et 111 pour 1, a une distance minimale de 3 et montre les deux usages possibles. Reçu 010 : ce mot est à distance 1 de 000 et à distance 2 de 111. Un décodeur qui corrige choisit 000, et il a raison si un seul bit s'est retourné. Si deux bits se sont retournés à partir de 000, le mot reçu, par exemple 110, est à distance 1 de 111, et le décodeur corrige vers le mauvais mot sans rien signaler. Un décodeur qui se contente de détecter aurait signalé ces deux erreurs, puisque 110 n'est pas un mot de code. Un code de distance 3 corrige donc une erreur, ou en détecte deux, mais pas les deux à la fois. Une distance plus grande permet de les faire ensemble.

Rappel de cours : corriger et signaler à la fois

Un décodeur peut faire les deux : corriger les mots reçus tout proches d'un mot de code, à distance au plus $t$ , et signaler tous les autres sans y toucher. Il corrige alors jusqu'à $t$ erreurs et en signale à coup sûr jusqu'à $s$ , avec $s \geq t$ , à condition que

t + s \leq d - 1

En effet, entre $t + 1$ et $s$ erreurs, le mot reçu est à plus de $t$ du mot émis, et à au moins $d - s \geq t + 1$ de tout autre mot de code : il n'est dans le rayon de correction d'aucun mot, et le décodeur le signale.

Exemple résolu. À $d = 3$ , corriger une erreur et en signaler deux demanderait $1 + 2 = 3$ , plus que $d - 1 = 2$  : le code de répétition corrige une erreur ou en signale deux. À $d = 4$ , $1 + 2 = 3 = d - 1$  : un code de distance 4 corrige une erreur et signale les mots à deux erreurs au lieu de les corriger de travers. Deux erreurs laissent en effet le mot reçu à distance 2 du mot émis, et à distance 2 au moins de tous les autres : il n'est à distance 1 d'aucun mot de code. C'est tout ce que la distance supplémentaire achète, car le code ne corrige toujours qu'une erreur.

Vérification rapideon peut se reprendre

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

Le bit de parité, et ses limites

Rappel de cours : le bit de parité

Un nombre modulo 2 est le reste de sa division par 2 : 0 s'il est pair, 1 s'il est impair. Le bit de parité d'un mot est la somme de ses bits modulo 2, c'est-à-dire 1 si le mot compte un nombre impair de 1, et 0 sinon :

p = (b_1 + b_2 + \dots + b_n) \bmod 2

Ajouté à la fin du mot, il rend pair le nombre total de 1. Le récepteur recompte les 1 du mot reçu entier, bit de parité compris : un nombre pair, il déclare le mot intact ; un nombre impair, il signale une erreur.

Exemple résolu. Les données 1011 comptent trois 1, puisque $1 + 0 + 1 + 1 = 3$ , un nombre impair, donc $p = 1$  : le mot émis est 10111, qui compte quatre 1.

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.

Le tableau suit le mot 10111 quand des bits se retournent en chemin, en partant de la gauche :

Bits retournés	Mot reçu	Nombre de 1	Verdict du contrôle
aucun	`10111`	4	intact, à raison
le premier	`00111`	3	erreur détectée
les deux premiers	`01111`	4	intact, à tort
les trois premiers	`01011`	3	erreur détectée

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. Quand les erreurs sont rares et indépendantes, c'est presque toujours le cas, car une erreur isolée est bien plus probable que deux : avec un bit faux sur mille, il signale plus de 99 % des mots de cinq bits altérés.
Sur un canal où les erreurs arrivent par rafales, ce qui est le cas d'un support rayé ou d'une interférence, la situation change : une rafale retourne plusieurs bits voisins d'un coup, leur nombre est pair à peu près une fois sur deux, et ces rafales-là passent inaperçues.

La somme de contrôle par OU exclusif du chapitre des bits aux caractères, dans le parcours Python, n'est pas autre chose : chacun de ses huit bits est le bit de parité d'une colonne, le même rang pris dans tous les caractères du message. Elle hérite donc de la même limite, colonne par colonne.

Vérification rapideon peut se reprendre

1.Que garantit exactement un bit de parité ?

2.Une rafale retourne quatre bits voisins d'un mot muni d'un bit de parité. Le contrôle…

Le code de Hamming à sept bits

Le premier code qui corrige sans tout répéter est conçu à la fin des années 1940 par Richard Hamming, 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. Il suit l'écriture binaire des positions.

Rappel de cours : lire un nombre binaire de trois chiffres

En binaire, chaque chiffre vaut deux fois plus que son voisin de droite : sur trois chiffres, les poids sont 4, 2 et 1. Trois chiffres binaires $abc$ valent donc

abc_2 = 4a + 2b + c

Exemple résolu. $101_2 = 4 + 0 + 1 = 5$ et $110_2 = 4 + 2 + 0 = 6$ . Dans l'autre sens, 3 s'écrit $011_2$ , puisque $3 = 2 + 1$ . Le détail, sur huit chiffres, est dans le chapitre des bits aux caractères du parcours Python.

Les sept positions, écrites sur trois chiffres :

Position	1	2	3	4	5	6	7
En binaire	001	010	011	100	101	110	111

$c_1$ surveille les positions dont le chiffre de droite vaut 1, $c_2$ celles dont le chiffre du milieu vaut 1, $c_4$ celles dont le chiffre de gauche vaut 1. Autrement dit, le bit de contrôle en position $2^k$ surveille les positions dont l'écriture binaire porte un 1 au rang $k$ , les rangs se comptant à partir de 0 en partant de la droite.

Encoder un mot de données se fait en deux temps. Les quatre bits de données occupent les cases restantes, 3, 5, 6 et 7, dans cet ordre. Puis chaque bit de contrôle est choisi pour que son groupe, lui compris, compte un nombre pair de 1. Pour les données 1011, les cases 3, 5, 6 et 7 reçoivent 1, 0, 1 et 1 :

le groupe de $c_1$ (cases 3, 5, 7) compte déjà $1 + 0 + 1 = 2$ , nombre pair, donc $c_1 = 0$  ;
celui de $c_2$ (cases 3, 6, 7) compte $1 + 1 + 1 = 3$ , donc $c_2 = 1$ pour rendre le total pair ;
celui de $c_4$ (cases 5, 6, 7) compte $0 + 1 + 1 = 2$ , donc $c_4 = 0$ .

Lu de la case 1 à la case 7, le mot émis est 0110011.

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 son groupe compte un nombre pair de 1, et 1 sinon. Écrits dans l'ordre $c_4$ , $c_2$ , $c_1$ , de gauche à droite, les trois chiffres forment un nombre binaire : le syndrome.
Ce nombre vaut 0 si le mot est intact. Si un seul bit a été retourné, il vaut exactement la position de ce bit : les contrôles qui passent à 1 sont ceux qui surveillent cette position, donc les chiffres à 1 de son écriture binaire. Retourner la position 5, qui s'écrit 101, fait passer $c_4$ et $c_1$ à 1 et laisse $c_2$ à 0 : le syndrome vaut $101_2 = 5$ .
La position se lit, elle ne se cherche pas. Sans cette construction, retrouver le mot émis demanderait de comparer le mot reçu aux seize mots de code, et leur nombre double à chaque bit de données ajouté ; ici, trois parités suffisent.

La figure ci-dessous porte le mot de données 1011, encodé en 0110011. Chaque case se retourne d'un clic, et les trois contrôles se recalculent dessous.

1c1contrôle

2c2contrôle

3c2 c1donnée

4c4contrôle

5c4 c1donnée

6c4 c2donnée

7c4 c2 c1donnée

c1	1 + 3 + 5 + 7	2 pair
c2	2 + 3 + 6 + 7	4 pair
c4	4 + 5 + 6 + 7	2 pair

syndrome = 000₂ = 0

Les trois contrôles passent : le mot est intact, et le syndrome vaut 0.

données émises 1011 → données décodées 1011 (retrouvées)

Le mot 1011 encodé sur sept bits. Sous chaque case, les contrôles qui la surveillent, dans l'ordre du syndrome : la position 5 s'écrit 101 en binaire, elle est donc surveillée par c4 et c1, et par eux seuls.

À manipuler

Retourner une case, n'importe laquelle, et lire le syndrome : il vaut le numéro de cette case. Cliquer de nouveau sur la même case la remet en place, ce que fait aussi le bouton « remettre le mot émis ». Recommencer ainsi sur les sept positions, une seule à la fois, y compris sur un bit de contrôle : le mécanisme ne fait aucune différence entre les deux sortes de bits, ce qui n'a rien d'évident et découle de la construction.
Regarder ensuite quels contrôles passent à 1, mis en couleur dans le tableau, et les comparer à la ligne écrite sous la case. En retournant la position 5, ce sont c4 et c1, et 5 s'écrit 101 : les contrôles violés sont l'écriture binaire de la position. Le syndrome n'a rien à chercher, ses trois parités écrivent la position.
Retourner enfin deux cases à la fois, par exemple 3 et 5. Le syndrome vaut 6 et désigne une position que personne n'a touchée. Le décodeur ne signale aucun doute : il corrige un bit innocent, et les données décodées sont fausses. Un décodeur qui corrige ne détecte donc pas deux erreurs, il les prend pour une seule ; pour les signaler, il faudrait renoncer à corriger et traiter tout syndrome non nul comme une alarme.

Pour aller plus loin (facultatif) : les sept syndromes vérifiés en Python

Ce programme ne fait rien de plus que la figure, et il n'y a rien à y écrire : il refait l'encodage de 1011 mené à la main plus haut, retourne chaque bit à tour de rôle et affiche le syndrome obtenu. Il sert à vérifier un calcul fait à la main. Le mot s'affiche comme une liste de sept chiffres, [0, 1, 1, 0, 0, 1, 1] pour 0110011. Remplacer "1011" par d'autres données vérifie un autre encodage, celui de la section « À calculer soi-même » par exemple.

main.py

Sortie

>_ Prêt à exécuter…

Les sept syndromes affichés valent 1, 2, …, 7, chacun égal à la position retournée : c'est ce qui permet de corriger sans rien demander à l'émetteur.

Ce code a une distance minimale de 3. Un bit retourné donne un syndrome égal à sa position, donc jamais nul. Deux bits retournés non plus : leurs positions diffèrent par au moins un chiffre binaire, et le contrôle de ce rang voit changer un seul de ses bits. Un ou deux bits retournés ne mènent donc jamais à un autre mot de code. Trois le peuvent : en retournant les cases 1, 2 et 3, $c_1$ voit changer deux bits (cases 1 et 3), $c_2$ aussi (cases 2 et 3), $c_4$ aucun, et les trois parités restent paires.

Ce code corrige donc une erreur. Son rendement, la part des bits transmis qui portent des données, vaut $4/7$ , soit environ 57 %.

Rappel de cours : décoder un mot reçu

Recalculer les trois parités du mot reçu, chacune sur son groupe de quatre cases : 0 si le groupe compte un nombre pair de 1, 1 sinon.
Les écrire dans l'ordre $c_4$ , $c_2$ , $c_1$ et lire ce nombre binaire : c'est le syndrome.
Un syndrome nul, le mot est accepté. Sinon, retourner la case qu'il désigne. Les données se lisent ensuite dans les cases 3, 5, 6 et 7.

Exemple résolu. Le mot émis 0110011 arrive sous la forme 0110111.

Groupe de $c_1$ , cases 1, 3, 5, 7 : $0 + 1 + 1 + 1 = 3$ , impair, donc 1.
Groupe de $c_2$ , cases 2, 3, 6, 7 : $1 + 1 + 1 + 1 = 4$ , pair, donc 0.
Groupe de $c_4$ , cases 4, 5, 6, 7 : $0 + 1 + 1 + 1 = 3$ , impair, donc 1.

Le syndrome s'écrit $101_2 = 5$ . Retourner la case 5 redonne 0110011, et les cases 3, 5, 6 et 7 portent les données 1011.

Vérification rapideon peut se reprendre

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

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. La construction de Hamming s'étend telle quelle : avec $r$ bits de contrôle placés aux positions 1, 2, 4, …, $2^{r-1}$ , le syndrome s'écrit sur $r$ chiffres et peut désigner $2^r - 1$ positions, d'où des mots de 7, 15, 31 ou 63 bits pour 3, 4, 5 ou 6 bits de contrôle. Le nombre de bits de contrôle croît donc 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 mot plus long se paie ailleurs : il offre plus de place à une deuxième erreur, que le code ne corrige pas.

Rappel de cours : la probabilité de deux erreurs dans un mot

Si chaque bit se retourne avec la probabilité $p$ , indépendamment des autres, le nombre d'erreurs dans un mot de $n$ bits suit une loi binomiale. Le mot arrive intact avec la probabilité $(1-p)^n$ , avec exactement une erreur avec la probabilité $np(1-p)^{n-1}$ , et subit donc au moins deux erreurs avec la probabilité

P_{\geq 2} = 1 - (1-p)^n - np(1-p)^{n-1} \approx \frac{n(n-1)}{2}\,p^2 \quad \text{quand } np \text{ est petit.}

Le facteur $\frac{n(n-1)}{2}$ compte les paires de positions où deux erreurs peuvent tomber : la probabilité croît à peu près comme le carré de la longueur.

Exemple résolu, pour un mot de 15 bits et un bit faux sur mille : $1 - 0{,}999^{15} - 15 \times 0{,}001 \times 0{,}999^{14} \approx 0{,}000\,104$ , soit 104 millionièmes, un mot sur 9 600 environ. L'approximation donne $\frac{15 \times 14}{2} \times 0{,}001^2 = 0{,}000\,105$ , soit 105 millionièmes.

Un meilleur rendement n'est pas une meilleure protection

Les quatre codes du tableau corrigent tous une seule erreur par mot. Le code long a un meilleur rendement, et il est plus fragile : deux erreurs dans un même mot sont bien plus probables sur soixante-trois bits que sur sept, et la deuxième 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

Au niveau des trames et des paquets, les protocoles réseau se contentent le plus souvent de détecter : ils ont un canal de retour, et il leur suffit de redemander un paquet abîmé. Ils emploient pour cela un contrôle de redondance cyclique, ou CRC ; chaque trame Ethernet se termine ainsi par un CRC de 32 bits. Les liaisons radio très bruitées, le Wi-Fi ou la téléphonie mobile, corrigent en plus sur place, parce qu'y redemander serait trop fréquent.

Rappel de cours : le CRC, une division modulo 2

Le principe est une division de polynômes. Le message est lu comme un polynôme dont les coefficients sont ses bits : 1101 devient $x^3 + x^2 + 1$ . Le générateur, fixé à l'avance, est de degré $r$ . L'émetteur écrit d'abord $r$ zéros à la suite du message, ce qui revient à le multiplier par $x^r$ , puis divise ce message allongé par le générateur en calculant modulo 2 : $1 + 1 = 0$ , il n'y a jamais de retenue, et soustraire revient à faire un OU exclusif bit à bit, noté $\oplus$ , qui vaut 1 quand les deux bits diffèrent et 0 sinon :

0 \oplus 0 = 1 \oplus 1 = 0, \qquad 0 \oplus 1 = 1 \oplus 0 = 1

Les $r$ bits du reste prennent la place des zéros, et la trame ainsi formée est divisible par le générateur. Le récepteur divise la trame reçue entière : un reste nul, il l'accepte ; un reste non nul, elle est abîmée. C'est la division euclidienne du chapitre sur l'arithmétique modulaire, posée comme celle des polynômes, mais modulo 2.

Exemple résolu. Le message 1101 et le générateur 1011, soit $x^3 + x + 1$ , de degré 3. Le message allongé s'écrit 1101000. Sous chaque 1 de tête, un OU exclusif avec 1011 donne successivement 0110000, 0011100, 0001010, puis 0000001. Le reste est 001, et la trame émise 1101001. Reçue avec son troisième bit retourné, 1111001, elle laisse le reste 110, non nul : l'erreur est vue.

Le générateur le plus simple, $x + 1$ , montre que ce n'est pas étranger à ce qui précède : le reste de la division par $x + 1$ vaut la somme des bits modulo 2, c'est-à-dire le bit de parité. Un CRC de 32 bits fait la même opération avec un générateur de degré 32, choisi avec soin, et obtient un reste de 32 bits.

Ce qu'un CRC garantit. Un CRC de $r$ bits, dont le générateur se termine par un 1 comme tous ceux qu'on emploie, détecte toutes les rafales d'erreurs de longueur inférieure ou égale à $r$ , une rafale de longueur $r$ étant une zone de $r$ bits consécutifs au plus, du premier bit faux au dernier, quels que soient les bits retournés entre les deux. Ce n'est pas une probabilité, c'est une certitude, et pour le CRC de 32 bits d'Ethernet elle couvre la quasi-totalité des dégradations réelles d'une ligne.
Au-delà, une altération aléatoire passe avec une probabilité d'environ $2^{-r}$  : pour 32 bits, environ une sur quatre milliards. Et il ne corrige rien du tout : il dit que la trame est abîmée, pas ce qu'elle 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 la distinction que le chapitre précédent fait entre l'intégrité accidentelle, contre le bruit, et l'intégrité contre un adversaire. La première se contente d'un CRC. Pour la seconde, l'empreinte de référence doit être hors de portée de l'adversaire : signée par l'expéditeur, ou calculée avec une clé secrète partagée, c'est-à-dire un code d'authentification. Les confondre produit un système qui ne protège pas de ce qu'on croyait.

Vérification rapideon peut se reprendre

1.Avant de diviser par un générateur de degré 3, l'émetteur d'un CRC…

2.Pourquoi Ethernet emploie-t-il un CRC plutôt qu'un code correcteur ?

Ce que la bouée achète

La question d'ouverture a maintenant sa réponse, chiffrée. La bouée émet 144 relevés par jour, 52 560 par an, sur un canal où un bit sur mille se retourne.

Protection	Bits par relevé	Relevés signalés, donc perdus	Relevés faux, sans alerte
Aucune	4	aucun	1 sur 250, soit 210 par an
Bit de parité	5	1 sur 200, soit 260 par an	1 sur 100 000, un tous les deux ans
Hamming à sept bits	7	aucun	1 sur 48 000, environ un par an
Répétition triple	12	aucun	1 sur 83 000, moins d'un par an

Les nombres viennent des rappels du chapitre. Sans protection, le relevé est faux dès qu'un de ses quatre bits l'est : $1 - 0{,}999^4 \approx 0{,}004$ . Le bit de parité signale tout nombre impair d'erreurs sur ses cinq bits, presque toujours une seule : $5 \times 0{,}001 \times 0{,}999^4 \approx 0{,}005$  ; il laisse passer les mots à deux erreurs, dix paires de positions possibles, soit environ $10 \times 0{,}001^2 = 10^{-5}$ . Le code de Hamming corrige toute erreur isolée et ne signale jamais rien : un relevé n'est faux qu'avec au moins deux erreurs dans le même mot, 21 millionièmes d'après la formule du rappel. La répétition triple perd un bit de données quand deux au moins de ses trois copies se retournent, environ $3 \times 0{,}001^2$ , et le relevé compte quatre bits.

Trois bits suffisent, ceux du code de Hamming : ils font passer de 210 relevés faux par an à un seul, sans en perdre aucun. La répétition triple fait un peu mieux, pour huit bits ajoutés au lieu de trois. Le bit de parité, si bon marché soit-il, n'est pas une réponse ici : il voit l'erreur mais ne la répare pas, et sans voie de retour un relevé signalé est un relevé perdu, plus nombreux même que les relevés faux qu'il évite. C'est la règle du début du chapitre, chiffrée : sans canal de retour, il faut corriger sur place, et payer la redondance d'avance.

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 formules : détection jusqu'à $d - 1$ , correction jusqu'à $\lfloor (d-1)/2 \rfloor$ , et les deux à la fois, $t$ erreurs corrigées et $s$ signalées, tant que $t + s \leq d - 1$ . Ne jamais additionner les deux maximums.
Calculer le rendement, et la probabilité qu'un mot subisse plus d'erreurs que le code n'en corrige, 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, dans l'ordre $c_4$ , $c_2$ , $c_1$  : il donne la position quand un seul bit est faux, et zéro signifie intact.
Pour un CRC, écrire à la suite du message autant de zéros que le degré du générateur, diviser en OU exclusif, et garder le reste ; le récepteur divise la trame entière et attend un reste nul.
Distinguer le bruit de l'adversaire. Un CRC répond au premier et à rien d'autre.

Mettre en pratique

Un compteur d'eau télérelevé envoie chaque nuit à la passerelle radio du quartier un code d'état de quatre bits, 1001 ce soir, protégé par le code de Hamming à sept bits.

Rappel de cours : les gestes du chapitre

Distance : compter les positions où deux mots diffèrent.
Capacités d'un code de distance minimale $d$  : détecter $d - 1$ erreurs, ou en corriger $\lfloor (d-1)/2 \rfloor$ , ou en corriger $t$ et en signaler $s$ à la fois tant que $t + s \leq d - 1$ .
Encoder en Hamming : les données dans les cases 3, 5, 6 et 7 ; chaque contrôle rend pair son groupe, $c_1$ avec les cases 3, 5, 7, $c_2$ avec 3, 6, 7, $c_4$ avec 5, 6, 7.
Syndrome : les trois parités recalculées du mot reçu, lues dans l'ordre $c_4$ , $c_2$ , $c_1$ comme un nombre binaire.
Deux erreurs dans un mot : $1 - (1-p)^n - np(1-p)^{n-1}$ .
Mots de code : un code qui porte $k$ bits de données a $2^k$ mots de code, parmi les $2^n$ mots possibles de $n$ bits.

Exemple résolu de ce dernier geste, sur un bit de parité ajouté à quatre bits de données : $2^4 = 16$ mots de code parmi les $2^5 = 32$ mots de cinq bits, soit la moitié. Les seize autres sont reconnus comme fautifs dès leur arrivée.

Un compteur d'eau, un code d'état sur sept bits

1.
Quelle est la distance de Hamming entre 1011010 et 0011101 ?
2.
Combien d'erreurs un code de distance minimale 7 corrige-t-il ?
3.
Un code de distance minimale 5 est réglé pour corriger une erreur. Combien d'erreurs signale-t-il à coup sûr en même temps ?
4.
Le compteur envoie le code d'état 1001. Que vaut son bit de contrôle $c_1$  ?
5.
Que vaut $c_2$  ?
6.
Que vaut $c_4$  ?
7.
La passerelle reçoit 0011101. Que vaut le syndrome, en décimal ?
8.
Combien de mots de code le code de Hamming à sept bits possède-t-il, parmi les 128 mots de sept bits ?
9.
Quelle proportion des mots de sept bits sont des mots de code, en pour cent ?
10.
Un bit sur mille se retourne. Quelle est la probabilité qu'un mot de sept bits subisse au moins deux erreurs, en millionièmes ?

Le syndrome 5 désigne la case 5 : la retourner redonne 0011001, et le code d'état 1001. La proportion de mots de code 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.

Rappel de cours : combien de bits de contrôle

Avec $r$ bits de contrôle, le syndrome s'écrit sur $r$ chiffres et désigne au plus $2^r - 1$ positions, la valeur 0 étant réservée au mot intact. Pour corriger une erreur dans un mot qui porte $k$ bits de données, il faut donc le plus petit $r$ tel que

k + r \leq 2^r - 1

Exemple résolu, pour $k = 11$ bits de données. Avec $r = 3$ , $11 + 3 = 14$ dépasse $2^3 - 1 = 7$  ; avec $r = 4$ , $11 + 4 = 15$ tient dans $2^4 - 1 = 15$ . Il faut quatre bits de contrôle : c'est le code de quinze bits du tableau du rendement.

Les autres questions reprennent les rappels précédents : la distance minimale et la règle $t + s \leq d - 1$ , la probabilité de deux erreurs dans un mot, et ce que fait un chiffrement d'un bit retourné, décrit au début du chapitre : selon la façon dont il est employé, il peut l'étaler sur tout un bloc du message déchiffré.

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 a la même distance minimale. C'est la mesure de ce que la construction de Hamming fait gagner : la répétition consacre deux bits sur trois à la redondance, Hamming trois sur sept, soit une fois et demie moins. La protection n'est d'ailleurs pas tout à fait la même : la répétition corrige une erreur tous les trois bits, Hamming une tous les sept, et les questions suivantes montrent ce que coûte un mot plus long.

Combien de bits de contrôle faut-il pour corriger une erreur dans un mot portant 1 000 bits de données, et est-ce une bonne idée ?

Il faut le plus petit $r$ tel que $1\,000 + r \leq 2^r - 1$ . Avec $r = 9$ , $1\,009$ dépasse $2^9 - 1 = 511$  ; avec $r = 10$ , $1\,010$ tient dans $2^{10} - 1 = 1\,023$ . Dix bits de contrôle suffisent, pour un rendement de $1\,000 / 1\,010 \approx 0{,}99$  : la croissance logarithmique du nombre de bits de contrôle, vue sur un grand mot.

Ce n'est une bonne idée que sur un canal très propre. Le mot de 1 010 bits ne corrige toujours qu'une erreur, et avec un bit faux sur mille il en subit au moins deux avec la probabilité $1 - 0{,}999^{1\,010} - 1\,010 \times 0{,}001 \times 0{,}999^{1\,009} \approx 0{,}27$  : plus d'un mot sur quatre arrive faux. Un rendement de 0,99 qui laisse passer un mot faux sur quatre est précisément la protection illusoire dont parle la méthode.

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 par mot. Ce qui les sépare est la probabilité d'en subir deux dans le même mot, car le décodeur prend alors le mot pour un mot à une erreur et le corrige de travers.

Avec un bit faux sur mille, la formule du rappel donne, pour un mot de 7 bits, au moins deux erreurs avec une probabilité d'environ $2{,}1 \times 10^{-5}$ , soit un mot sur 48 000. Pour un mot de 63 bits, environ $1{,}9 \times 10^{-3}$ , soit un mot sur 530 : neuf fois plus long, mais quatre-vingt-dix fois plus exposé, parce que la probabilité de deux erreurs croît à peu près comme le carré de la longueur.

La comparaison honnête porte sur la même quantité de données. Les 57 bits de données d'un mot long demandent un peu plus de quatorze mots courts, qui en perdent un avec une probabilité d'environ $3 \times 10^{-4}$ , six fois moins que le mot long. Le mot long transmet ces données avec 1,6 fois moins de bits. Sur ce canal, le mot de 7 bits protège nettement mieux ; le mot de 63 bits ne se justifie que si la perte d'un mot de temps en temps est acceptable, ou si le canal est plus propre.

Les ordres d'un poste d'aiguillage voyagent dans un code de distance minimale 5, et le poste peut redemander un ordre. Vaut-il mieux corriger jusqu'à deux erreurs, ou en corriger une seule et signaler les autres ?

Les deux réglages respectent $t + s \leq d - 1 = 4$  : corriger jusqu'à deux erreurs, ou en corriger une et signaler à coup sûr les mots qui en portent deux ou trois. Ils diffèrent par ce qui trompe le décodeur.

En corrigeant jusqu'à deux erreurs, trois erreurs placent le mot reçu à distance 3 du mot émis, et parfois à distance $5 - 3 = 2$ seulement d'un autre mot de code : le décodeur le corrige vers ce dernier, et l'aiguille reçoit un ordre faux sans aucune alerte. En corrigeant une seule erreur, ce même mot, à distance 2 au moins de tout mot de code, est signalé, et il faut quatre erreurs pour tromper le décodeur.

Le poste a une voie de retour : un ordre signalé se redemande, au prix d'un court délai. Une erreur isolée, de loin la plus fréquente, reste corrigée sur place ; les mots à deux ou trois erreurs, rares, coûtent une retransmission au lieu d'un ordre faux. Pour un ordre de sécurité, corriger une erreur et signaler les autres est le bon réglage : corriger deux erreurs n'épargne que quelques retransmissions, et réduit la marge de sécurité d'une erreur.

Un relevé doit être chiffré et protégé par un code correcteur. Dans quel ordre l'émetteur doit-il faire les deux ?

Chiffrer d'abord, protéger ensuite : le code correcteur est la dernière opération de l'émetteur, donc la première du récepteur. Le récepteur corrige le chiffré tel qu'il l'a reçu, puis déchiffre un chiffré redevenu intact.

Dans l'autre ordre, le récepteur doit déchiffrer avant de corriger, et le bit retourné traverse le déchiffrement. Selon la façon dont le chiffrement est employé, il en ressort étalé sur tout un bloc, des dizaines de bits faux, bien plus que l'erreur par mot que corrige le code de Hamming. Et si le message porte une signature ou un code d'authentification, comme le recommande le chapitre sur la cryptographie, la vérification échoue sur ce seul bit, et le message est refusé : la correction n'a jamais l'occasion de servir.

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

La distance de Hamming

Le bit de parité, et ses limites

Le code de Hamming à sept bits

Le rendement, et ce qu'il faut en faire

Le CRC : détecter beaucoup, ne corriger rien

Ce que la bouée achète

La méthode

Mettre en pratique

Dans la bibliothèque d'exercices

Le CRC : détecter beaucoup, ne corriger rien