Détection et correction d'erreurs

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• expliquer pourquoi un canal réel commet des erreurs et distinguer les deux tâches, détecter et corriger, en justifiant pourquoi la seconde est strictement plus difficile que la première;
• construire un bit de parité, énoncer exactement ce qu'il détecte et ce qu'il laisse passer, et calculer la probabilité d'une erreur non détectée;
• manipuler la distance de Hamming, démontrer qu'elle est une distance, et déduire de la distance minimale d'un code le nombre d'erreurs qu'il détecte et celui qu'il corrige;
• encoder et décoder avec le code de Hamming (7,4), calculer un syndrome, corriger une erreur simple et reconnaître l'échec sur une erreur double;
• énoncer et démontrer la borne de Hamming, dire ce qu'est un code parfait et vérifier que le code (7,4) l'est;
• diviser un message par un polynôme générateur sur $\mathrm{GF}(2)$ pour obtenir un CRC, et dire ce qu'un CRC garantit;
• énoncer le théorème du codage de canal, calculer la capacité $C=1-H(p)$ d'un canal binaire symétrique et expliquer pourquoi ce théorème ne donne aucun code.

Ajouter de la redondance, après l'avoir enlevée

Le chapitre 6 a mesuré la quantité d'information d'une source par son entropie $H$, et le chapitre 7 a construit des codes — Huffman, Lempel-Ziv — dont le seul but était de supprimer la redondance: un fichier compressé est un fichier dont on a retiré tout ce qui était prévisible. Un texte français comprimé optimalement ressemble à une suite de bits tirés à pile ou face; c'est précisément le signe que la compression a fonctionné.

Ce chapitre fait le mouvement inverse, et il faut voir dès maintenant que ce n'est pas une contradiction. La redondance que le chapitre 7 élimine est subie: elle vient de la structure de la langue, de la corrélation entre pixels voisins, des répétitions d'un journal de serveur. Elle est abondante, mal placée, et elle protège mal. La redondance que ce chapitre ajoute est choisie: on sait exactement combien de bits on dépense, où ils sont, et ce qu'ils garantissent. Sept bits bien choisis protègent quatre bits de données contre n'importe quelle erreur simple; les milliers de bits de redondance d'un texte français non compressé ne garantissent rien du tout.

L'ordre des deux opérations n'est d'ailleurs pas arbitraire. Dans une chaîne de transmission réelle, on comprime d'abord (codage de source), on protège ensuite (codage de canal). Shannon a montré que cette séparation ne coûte rien asymptotiquement — c'est le théorème de séparation source-canal, que nous n'aborderons pas — et elle a l'avantage considérable de découpler deux problèmes indépendants: combien vaut ce message, et à quel point ce fil est-il mauvais.

Pourquoi un bit se trompe

Un bit n'est jamais un bit. C'est une tension sur une piste de cuivre, une charge dans une cellule de mémoire, un creux dans une couche d'aluminium, une modulation de phase d'une onde radio. Toutes ces grandeurs sont continues, et la lecture consiste à décider d'un seuil. Trois familles de causes font basculer la décision:

• le bruit thermique et électromagnétique sur un canal de transmission: l'agitation des porteurs de charge, les interférences d'un moteur voisin, l'atténuation sur un long câble. Le récepteur lit une tension proche du seuil et tranche du mauvais côté;
• le défaut physique du support: une rayure sur un disque optique, un grain de poussière sur une bande, une cellule de mémoire flash usée par des dizaines de milliers de cycles d'écriture. Ici les erreurs ne sont pas isolées: elles arrivent en rafales (bursts), une rayure effaçant des milliers de bits consécutifs;
• la perturbation ponctuelle d'une mémoire: un rayon cosmique secondaire ou une particule alpha issue de la radioactivité naturelle du boîtier dépose assez de charge dans une cellule DRAM pour en inverser le contenu. C'est ce qu'on appelle une erreur soft: la cellule n'est pas cassée, seul son contenu est faux. C'est la raison pour laquelle les serveurs utilisent de la mémoire dite ECC, qui embarque exactement le genre de code que ce chapitre décrit.

Nous ne quantifierons pas ces taux: ils dépendent entièrement de la technologie, de l'altitude, de la température et de l'âge du matériel, et toute valeur citée sans sa source serait une invention. Ce que nous allons faire, c'est un modèle: fixer une probabilité d'erreur $p$ par bit et en tirer toutes les conséquences.

Ce modèle est une idéalisation, et il faut le dire: il ne décrit pas une rayure, qui produit une rafale et non des erreurs indépendantes. Les codes réellement utilisés sur un disque ou une bande combattent les rafales par un entrelacement (interleaving): on étale les bits d'un même mot de code sur des positions physiques éloignées, de sorte qu'une rafale de mille bits consécutifs ne touche qu'un bit dans chacun de mille mots différents — et redevient, du point de vue du décodeur, une suite d'erreurs isolées. Le modèle indépendant est donc à la fois faux et opérationnel, ce qui est la définition d'un bon modèle.

Détecter n'est pas corriger

Deux objectifs distincts, dont le second est strictement plus coûteux.

Détecter, c'est décider si le bloc reçu est intact ou abîmé. Un détecteur n'a besoin de rendre qu'un bit de réponse — «bon» ou «mauvais» — et l'usage qu'on en fait est un renvoi: le récepteur demande la retransmission du bloc. C'est le mécanisme des protocoles dits ARQ (Automatic Repeat reQuest), celui de TCP (chapitre 10).

Corriger, c'est nommer les positions fautives et rétablir le message sans rien redemander. Il faut donc, pour chaque bloc reçu abîmé, désigner un mot de code parmi tous ceux qui pourraient l'avoir engendré. Le canal de retour a disparu: c'est la seule option quand il n'existe pas (un disque enregistré il y a dix ans, une sonde spatiale à quarante minutes-lumière), ou quand il coûte trop cher (une diffusion vers un million de récepteurs, un flux temps réel).

L'asymétrie de coût se voit déjà sur un exemple minuscule. Pour détecter une erreur simple sur $k$ bits de données, un seul bit supplémentaire suffit, comme nous allons le voir. Pour en corriger une, il faut au minimum de quoi nommer la position fautive parmi $n$ possibilités, plus le cas «aucune erreur»: il faut donc au moins ${\log }_2(n+1)$ bits de redondance. Détecter coûte un bit; corriger coûte un logarithme — et surtout, comme nous allons le démontrer, corriger $t$ erreurs exige une distance minimale deux fois plus grande que d'en détecter $t$.

Le bit de parité

Le mécanisme le plus simple qui soit, et il est partout: dans les lignes série, dans certains bus, dans les cartes à puce.

Le rendement du code est $R=k/(k+1)$: pour $k=7$, on transmet 8 bits pour 7 bits utiles, soit un surcoût de $1/7\approx 14,3\%$. Le récepteur calcule le OU exclusif des huit bits reçus. S'il trouve 0, la parité est respectée; s'il trouve 1, le mot est certainement abîmé.

Démonstration. Notons $x\in \{0,1{\}}^n$ le mot émis et $e\in \{0,1{\}}^n$ le motif d'erreur, de sorte que le mot reçu est $y=x\oplus e$ (le bit $i$ est inversé si et seulement si ). Le contrôle du récepteur calcule

par commutativité et associativité du OU exclusif. Or $\sigma (x)=0$ puisque $x$ est un mot de code, donc $\sigma (y)=\sigma (e)$, qui vaut 1 si et seulement si $e$ contient un nombre impair de 1. Le contrôle signale une erreur exactement dans ce cas: toute erreur de poids impair est détectée, toute erreur de poids pair — en particulier toute erreur double — passe inaperçue. $\square$

La démonstration montre au passage un fait général et très utile: pour un code linéaire, c'est-à-dire un code stable par OU exclusif, le résultat du contrôle ne dépend que du motif d'erreur, jamais du mot émis. Nous nous en servirons constamment.

Distance de Hamming

Pour aller plus loin, il faut une géométrie. L'idée de Richard Hamming, aux Bell Labs à la fin des années 1940, est de munir l'ensemble $\{0,1{\}}^n$ des mots de $n$ bits d'une notion de distance, et de regarder un code comme un ensemble de points écartés les uns des autres.

Par exemple $d(1011010,1001011)=3$: les mots diffèrent aux positions 3, 4 et 7. La distance compte les bits à retourner pour passer de l'un à l'autre — c'est donc exactement le nombre d'erreurs que le canal doit commettre pour transformer $x$ en $y$.

Démonstration. Les points 1 et 2 sont immédiats: un cardinal est positif, il est nul si et seulement si l'ensemble compté est vide, c'est-à-dire si $x$ et $y$ coïncident partout; et la condition $x_i\ne y_i$ est symétrique en $x$ et $y$.

Pour le point 3, posons

de sorte que $d(x,z)=|A|$, $d(x,y)=|B|$ et $d(y,z)=|C|$. Montrons $A\subseteq B\cup C$. Soit , c'est-à-dire . Si l'on avait à la fois et , alors et , donc par transitivité de l'égalité — contradiction. Donc ou , et l'inclusion est établie. Il vient

$\square$

L'inégalité triangulaire n'est pas un ornement: c'est l'outil de la démonstration du théorème de correction, et c'est la raison pour laquelle l'image des «sphères» a un sens.

Les deux théorèmes fondamentaux

Démonstration. Soit $c$ le mot émis et $e$ un motif d'erreur de poids $w$ avec $1\le w\le d_{\min }-1$. Le mot reçu $y=c\oplus e$ vérifie . Si était un mot de code, on aurait deux mots de code distincts ( car ) à distance , ce qui contredit la définition de . Donc n'est pas un mot de code, et le récepteur — qui sait reconnaître les mots de code — signale l'anomalie.

Réciproquement, soient $c$ et $c^{\prime }$ deux mots de code à distance exactement $d_{\min }$. Le motif $e=c\oplus c^{\prime }$ est de poids $d_{\min }$, et si est émis avec cette erreur, le récepteur reçoit , qui est un mot de code parfaitement légitime: il ne détecte rien.

Démonstration. Le décodage au plus proche voisin consiste à rendre le mot de code $\hat{c}$ minimisant $d(\hat{c},y)$, où $y$ est le mot reçu. Supposons $y=c\oplus e$ avec $w(e)\le t$, donc . Soit un autre mot de code. L'inégalité triangulaire donne

Or (8.4) signifie $d_{\min }\ge 2t+1$, donc $d_{\min }-t\ge t+1>t\ge d(c,y)$. Tout autre mot de code est donc strictement plus loin de que : le plus proche voisin est , unique, et le décodage rend le mot émis.

Pour la seconde partie, prenons $c$ et $c^{\prime }$ à distance $d_{\min }$ et considérons un mot $y$ obtenu à partir de $c$ en inversant $t+1$ des $d_{\min }$ positions où et diffèrent. Alors et . Si , cela fait : le décodeur choisit et se trompe. Si , on obtient : le décodeur est devant une égalité, il ne peut pas trancher, et s'il tranche il a une chance sur deux de se tromper.

L'image de l'empilement de sphères

Voici la façon géométrique de lire les deux théorèmes, et il vaut la peine de la rendre complètement explicite parce qu'elle pilote toute la suite du chapitre.

Appelons boule de rayon $t$ centrée en $x$ l'ensemble $B(x,t)=\{y:d(x,y)\le t\}$ des mots à au plus $t$ inversions de $x$. Son cardinal ne dépend pas de $x$: choisir un élément de $B(x,t)$, c'est choisir les positions à inverser, soit

Un code est alors un ensemble de centres. Le canal déplace le point émis d'au plus $t$ pas, et le décodeur au plus proche voisin ramène le point reçu au centre le plus proche. Cette opération est correcte si et seulement si les boules de rayon $t$ centrées sur les mots de code sont deux à deux disjointes — c'est exactement ce que dit $d_{\min }\ge 2t+1$, puisque deux boules de rayon $t$ centrées à distance $d$ se rencontrent si et seulement si $d\le 2t$.

Détecter, c'est beaucoup moins demander: il suffit qu'aucun mot de code n'en touche un autre, c'est-à-dire $d_{\min }\ge w+1$ pour détecter $w$ erreurs. D'où le facteur deux entre les deux théorèmes: détecter $t$ erreurs demande $d_{\min }\ge t+1$, en corriger demande . Dans un cas, il faut que le point déplacé ne retombe sur aucun centre; dans l'autre, il faut qu'il reste dans le bon domaine.

Un code peut d'ailleurs choisir son régime. Avec $d_{\min }=3$ on peut, au choix, corriger une erreur (et n'en détecter aucune de plus), ou renoncer à corriger et détecter deux erreurs. Les deux usages ne se cumulent pas: dès qu'on décide de corriger, on décide d'interpréter, et une erreur double est interprétée à tort. C'est la convention que l'on résume en écrivant qu'un code de distance 3 «corrige une erreur ou en détecte deux».

Le code de répétition

Le correcteur le plus simple qu'on puisse imaginer: on répète chaque bit $m$ fois et l'on décide à la majorité.

Pour $m=3$, les mots de code sont 000 et 111, la distance minimale vaut 3 et le code corrige une erreur: les mots 001, 010, 100 sont décodés en 0, les mots 011, 101, 110 en 1. Le décodage au plus proche voisin est ici littéralement le vote majoritaire.

Le décodeur se trompe exactement lorsque la majorité des copies est fausse, c'est-à-dire lorsqu'au moins $t+1=(m+1)/2$ des $m$ bits sont inversés. Comme les erreurs sont indépendantes:

Le code de répétition est donc un correcteur honnête et un très mauvais code. Il montre en revanche un point de principe: on sait obtenir une fiabilité arbitrairement bonne, à condition d'accepter un rendement qui tend vers zéro. Toute la théorie du codage consiste à ne pas payer ce prix-là. Regardez la dernière ligne du tableau: le code de Hamming (7,4) offre un rendement de $0,5714$, presque le double de la répétition 3, pour une erreur résiduelle du même ordre de grandeur. C'est lui que nous construisons maintenant.

Le code de Hamming (7,4)

Hamming raconte l'avoir inventé par exaspération: la machine à cartes des Bell Labs signalait une erreur le week-end, s'arrêtait, et il retrouvait le lundi un calcul non fait. «Si la machine sait qu'il y a une erreur, pourquoi ne sait-elle pas où?» Le code publié en 1950 répond exactement à cette question.

La convention, fixée une fois pour toutes

Les trois équations de parité sont

Ces trois listes de positions ne sont pas arbitraires, et c'est le cœur du mécanisme: le contrôle $p_k$ porte sur les positions dont le numéro, écrit en binaire sur trois bits, a un 1 au poids $k$. Les positions 1, 3, 5, 7 sont celles de numéro impair ($001$, $011$, $101$, $111$); les positions 2, 3, 6, 7 celles dont le bit de poids 2 vaut 1 ($010$, $011$, $110$, $111$); les positions 4, 5, 6, 7 celles dont le bit de poids 4 vaut 1. Chaque position de parité (, , ) n'apparaît que dans un seul contrôle, ce qui permet de la calculer directement par (8.7).

Le diagramme de la figure 8.2 rend cette correspondance visible. Chaque cercle est une équation de parité; encoder consiste à choisir la valeur des trois bits de parité pour que chacun des trois cercles contienne un nombre pair de 1.

La matrice génératrice

Les relations (8.7) sont linéaires sur $\mathrm{GF}(2)$, le corps à deux éléments $\{0,1\}$ muni de l'addition modulo 2 et de la multiplication ordinaire. L'encodage est donc un produit matriciel: si $\mathbf{d}=(d_1,d_2,d_3,d_4)$ est le vecteur des données, le mot de code est avec

toutes les opérations étant faites modulo 2. La ligne $i$ de $G$ est le mot de code associé à la donnée $d_i=1$, les autres étant nulles; la colonne $j$ indique quels bits de données entrent dans $b_j$. Deux conséquences immédiates et importantes:

• le code est linéaire: $(\mathbf{d}\oplus {\mathbf{d}}^{\prime })G=\mathbf{d}G\oplus {\mathbf{d}}^{\prime }G$, donc le OU exclusif de deux mots de code est un mot de code, et l'ensemble des 16 mots est un sous-espace vectoriel de dimension 4 de $\mathrm{GF}(2{)}^7$;
• par le raccourci du paragraphe précédent, $d_{\min }$ est le plus petit poids d'un mot de code non nul.

Énumérons les seize mots (calcul fait en Python, poids indiqués):

La distribution des poids est donc: un mot de poids 0, sept de poids 3, sept de poids 4, un de poids 7. Le plus petit poids non nul vaut 3:

Par les théorèmes 8.3 et 8.4, le code corrige une erreur ($t=\lfloor 2/2\rfloor =1$) ou en détecte deux, pour un rendement $R=4/7\approx 0,5714$.

Le syndrome

Le décodage est l'opération inverse, et elle est d'une élégance qui explique la célébrité du code.

Démonstration. Chaque $s_k$ est une somme modulo 2 de quatre bits reçus; comme dans la démonstration du théorème 8.1, la linéarité donne $s_k(\mathbf{c}\oplus \mathbf{e})=s_k(\mathbf{c})\oplus s_k(\mathbf{e})$, et puisque les équations (8.7) sont exactement les équations de parité satisfaites par un mot de code. Donc : le syndrome ignore le message et ne voit que l'erreur.

Si $\mathbf{e}$ est l'erreur simple en position $j$, alors $s_k(\mathbf{e})=1$ si et seulement si la position $j$ figure dans la liste du contrôle $k$, c'est-à-dire, par construction, si et seulement si le bit de poids $k$ du nombre $j$ vaut 1. Les trois bits $(s_4,s_2,s_1)$ sont donc exactement l'écriture binaire de , d'où . Comme les sept positions donnent sept syndromes non nuls , et que le syndrome nul correspond à l'absence d'erreur, les huit valeurs possibles du syndrome sont toutes atteintes exactement une fois.

Ce dernier point mérite d'être souligné: les 3 bits de syndrome offrent $2^3=8$ valeurs, et il y a exactement $7+1=8$ situations à distinguer (sept erreurs simples et l'absence d'erreur). Rien n'est gaspillé, et rien ne reste en réserve. C'est cette coïncidence numérique qui fait que le code (7,4) est «parfait», notion que nous précisons à la section suivante.

La probabilité d'erreur résiduelle du code (7,4)

Il reste à chiffrer ce que le code apporte sur un canal binaire symétrique. Deux quantités différentes, à ne pas confondre.

La probabilité qu'un bloc de sept bits ne soit pas correctement décodé est la probabilité qu'il subisse deux erreurs ou plus:

À $p=0,01$: $(1-p{)}^7=0,932065$ et $7p(1-p{)}^6=0,065904$, donc .

La probabilité qu'un bit de données donné soit faux après décodage est plus petite, parce qu'un bloc mal décodé ne fausse pas forcément les quatre bits de données. On l'obtient exactement en énumérant les $2^7=128$ motifs d'erreur, en décodant chacun et en comptant les bits de données encore faux. La linéarité permet de supposer le mot nul émis. Le calcul (fait en Python) donne

Chaque coefficient est le nombre total de bits de données encore faux, sommé sur les $\left(\genfrac{}{}{0ex}{}{7}{w}\right)$ motifs de poids $w$, puis divisé par les 4 bits du bloc. Le terme dominant est donc $9p^2$ quand $p$ est petit, et ce 9 se lit directement: sur les $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$ motifs de poids 2, le décodeur laisse en tout bits de données faux, soit bit sur 4 en moyenne, et . Numériquement, (contre pour l'approximation), et .

Comparons honnêtement à la répétition 3, à $p=0,01$:

• répétition 3: erreur $2,98\cdot 10^{-4}$, rendement $0,3333$;
• Hamming (7,4): erreur $8,74\cdot 10^{-4}$, rendement $0,5714$.

Le code de Hamming est 2,9 fois moins fiable et 1,71 fois plus rapide. Il n'y a pas de vainqueur absolu: il y a un compromis, et c'est exactement ce que l'explorateur ci-dessous permet de manipuler.

Une dernière observation, que l'explorateur rend visible et qu'il faut avoir vue une fois: au-delà de $p\approx 0,21$, la courbe du code de Hamming passe au-dessus de celle du canal nu. À $p=0,25$, l'erreur résiduelle vaut $0,262$ contre $0,25$ sans aucun codage. Le décodeur, en «corrigeant» des blocs qui portent presque toujours deux erreurs ou plus, en ajoute plus qu'il n'en retire. Un code correcteur n'est pas une protection inconditionnelle: il faut que le canal soit déjà assez bon pour que sa règle de décision ait un sens. Ce n'est pas un accident du code (7,4), c'est le comportement de tout décodeur au plus proche voisin quand les sphères de correction ne contiennent plus l'essentiel de la masse de probabilité.

La borne de Hamming et les codes parfaits

La question naturelle est maintenant: peut-on faire mieux? Pour un canal donné et une capacité de correction donnée, combien de mots de code peut-on au maximum loger dans $\{0,1{\}}^n$? L'image de l'empilement de sphères répond immédiatement.

Démonstration. Considérons les $M$ boules $B(c,t)$ centrées sur les mots de code. Montrons d'abord qu'elles sont deux à deux disjointes. Soient $c\ne c^{\prime }$ deux mots de code et supposons qu'un mot $y$ appartienne aux deux boules: $d(c,y)\le t$ et . L'inégalité triangulaire (théorème 8.2) donne alors

ce qui contredit la définition de $d_{\min }$. Les boules sont donc disjointes.

Chacune contient, d'après (8.5), exactement ${\sum }_{i=0}^t\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ mots. Leur réunion, contenue dans $\{0,1{\}}^n$ qui compte $2^n$ éléments, a donc pour cardinal .

Il faut bien mesurer ce que «parfait» signifie et ce qu'il ne signifie pas. Un code parfait n'est pas «le meilleur code possible» dans l'absolu: c'est un code sans aucun gaspillage d'espace pour la capacité de correction qu'il vise. Aucun mot reçu n'est ambigu, aucun n'est laissé de côté, chaque mot reçu est décodé, et le décodeur ne peut jamais répondre «je ne sais pas». C'est aussi ce qui fait sa fragilité: un code parfait corrigeant $t$ erreurs n'a aucune marge pour en détecter $t+1$, puisqu'il n'existe aucun mot à distance $t+1$ ou plus de tous les mots de code. C'est précisément l'échec de l'exemple 8.6.

Le code de Hamming (7,4) est le premier d'une famille infinie: pour tout $r\ge 2$, il existe un code de Hamming $(2^r-1,2^r-1-r)$, construit exactement de la même façon — $r$ bits de parité aux positions puissances de deux, le syndrome lu en binaire donnant le numéro du bit fautif — de distance minimale 3, corrigeant une erreur, et parfait. Pour on retrouve (7,4) de rendement ; pour , le code (15,11) de rendement ; pour , le code (255,247) de rendement . Le rendement tend vers 1: plus le bloc est long, moins la protection coûte cher — mais la capacité de correction reste d' erreur par bloc, ce qui devient rapidement insuffisant quand le bloc s'allonge. Ce compromis est la raison pour laquelle on n'utilise pas un code de Hamming (1023,1013) en pratique.

Enfin, un mot sur la rareté des codes parfaits, parce qu'elle est frappante. On sait démontrer — c'est un résultat difficile, établi indépendamment par van Lint et Tietäväinen au début des années 1970 — que les seuls codes binaires parfaits sont: les codes triviaux (le code entier $\{0,1{\}}^n$ et les codes à un mot), les codes de répétition de longueur impaire, les codes de Hamming, et un seul autre, le code de Golay $(23,12,7)$, qui corrige trois erreurs. La liste s'arrête là. Les codes parfaits sont des accidents arithmétiques, et la théorie des codes est en grande partie l'art de bien vivre sans eux.

Les CRC: la redondance par les polynômes

Les codes vus jusqu'ici protègent de petits blocs contre des erreurs isolées. Les trames d'un réseau et les fichiers d'une archive posent un problème différent: les blocs sont longs (des milliers de bits), les erreurs arrivent en rafales, et l'on ne cherche qu'à détecter, la retransmission étant disponible. Le contrôle de redondance cyclique (Cyclic Redundancy Check, CRC) est la réponse universelle à ce problème.

Un bloc de bits est un polynôme

L'idée est de voir une suite de bits comme les coefficients d'un polynôme à coefficients dans $\mathrm{GF}(2)$. Le mot $\text{110101}$ devient

Sur $\mathrm{GF}(2)$, l'addition est le OU exclusif ($1+1=0$), donc addition et soustraction coïncident — il n'y a pas de retenue, et la «soustraction» d'un polynôme est un simple XOR. La division euclidienne fonctionne exactement comme sur les réels: pour tout $A(x)$ et tout $G(x)$ non nul, il existe un unique couple $(Q,R)$ avec $A=QG+R$ et .

La propriété qui justifie l'étape 3 est immédiate: $x^{r}M=QG+R$ donne $T=x^{r}M+R=QG+2R=QG$ sur , puisque . Le bloc transmis est donc par .

Si le canal ajoute un motif d'erreur $E(x)$, le récepteur divise $T+E=QG+E$: le reste est nul si et seulement si $G$ divise $E$. Encore une fois, le contrôle ne voit que l'erreur, jamais le message. On en déduit tout ce qu'un CRC garantit:

• toute erreur simple est détectée dès que $G$ a au moins deux termes non nuls: en effet $E(x)=x^i$, et un $G$ à deux termes ne divise pas un monôme;
• toute erreur de poids impair est détectée si $G$ est divisible par $(x+1)$: un polynôme de poids impair vaut 1 en $x=1$, alors que tout multiple de s'y annule;

C'est cette dernière garantie qui fait la valeur des CRC dans le monde réel: un CRC à 32 bits détecte à coup sûr toute rafale d'au plus 32 bits, ce qu'aucun des codes précédents ne promet.

Où l'on trouve des CRC

Les générateurs ne sont pas choisis au hasard: ils sont normalisés, et sélectionnés pour leurs propriétés de détection sur des longueurs de trame données.

• CRC-32 (générateur de degré 32) protège les trames Ethernet, où il constitue la séquence de contrôle de trame, et il ferme chaque bloc d'un fichier PNG ainsi que chaque entrée d'une archive ZIP ou gzip. Une trame Ethernet dont le CRC est faux est simplement jetée par la carte réseau; c'est aux couches supérieures (TCP, chapitre 10) de redemander les données.
• CRC-16 dans plusieurs protocoles industriels et dans les cartes mémoire.
• CRC-8 dans de petits bus de capteurs, où un seul octet de contrôle est déjà un luxe.

Le calcul est extrêmement bon marché: un registre à décalage à rétroaction en matériel, une boucle sur une table de 256 entrées en logiciel. C'est pour cela qu'on en met partout — et c'est pour cela qu'il ne faut pas leur demander ce qu'ils ne savent pas faire.

Le théorème du codage de canal

Nous avons construit des codes et calculé ce qu'ils valent. Reste la question de fond, celle que Shannon a posée et résolue en 1948: quelle est la limite? Existe-t-il, pour un canal donné, un rendement au-delà duquel aucune protection n'est possible, et en deçà duquel tout est possible?

La capacité

L'interprétation est celle du chapitre 6, et elle vaut la peine d'être refaite. Envoyer un bit, c'est au mieux transmettre un bit d'information. Le canal en détruit une partie: connaissant la sortie, il reste une incertitude sur l'entrée, et cette incertitude conditionnelle vaut exactement $H(p)$ — c'est l'entropie du bit d'erreur, le seul objet inconnu du récepteur. L'information mutuelle entre entrée et sortie, maximisée sur les distributions d'entrée (le maximum étant atteint à l'équiprobabilité), vaut donc $I=1-H(p)$. La capacité est cette quantité.

Trois valeurs à retenir, calculées avec (8.13):

• $p=0$: $H=0$ et $C=1$. Le canal est transparent, aucune redondance n'est nécessaire.
• $p=0,01$: $H(0,01)=0,0808$ et $C=0,9192$. Un canal à un pour cent d'erreur permet encore de transmettre plus de neuf dixièmes de bit d'information par bit envoyé — . C'est beaucoup plus que ce que tous nos codes ont obtenu.

L'énoncé de Shannon

Cet énoncé est d'une brutalité remarquable. Il ne dit pas «on peut faire un peu mieux»: il dit qu'il existe un seuil net. En dessous de $C$, la fiabilité parfaite est atteignable, à un coût en longueur de bloc mais sans aucun sacrifice de rendement supplémentaire. Au-dessus de $C$, rien n'y fait. On ne s'attendait pas à cela avant 1948; on s'attendait à ce que la fiabilité se paie toujours par un rendement tendant vers zéro, comme dans le code de répétition. Shannon a montré que cette intuition — celle qui paraît si évidente quand on regarde le tableau de l'exemple 8.3 — est fausse.

Cinquante ans pour combler l'écart

L'histoire qui suit ce théorème est l'une des plus instructives de l'informatique, parce qu'elle mesure l'écart entre savoir qu'une chose est possible et savoir la faire.

À $p=0,01$, la capacité vaut $0,9192$. Le code de Hamming (7,4), publié deux ans après l'article de Shannon, atteint un rendement de $0,5714$ avec une erreur résiduelle de $8,7\cdot 10^{-4}$. Le théorème affirme qu'à ce même rendement de $4/7$ — bien en dessous de $0,9192$ — on pourrait rendre l'erreur , ou , en allongeant les blocs. Rien dans le code de Hamming ne s'en approche. Inversement, le rendement n'est atteignable de façon fiable que tant que , c'est-à-dire, en résolvant , pour : au-delà, même un codeur idéal doit ralentir.

La chronologie des étapes qui ont comblé cet écart:

• 1949–1950: Golay publie son code $(23,12,7)$, Hamming le sien. Premiers codes correcteurs structurés.
• 1960: Reed et Solomon publient les codes qui portent leur nom, qui travaillent sur des symboles (des octets) plutôt que sur des bits et sont donc naturellement résistants aux rafales. Ce sont eux que l'on trouve dans les disques compacts, les DVD, les codes QR et les liaisons avec les sondes spatiales.
• 1962: Gallager, dans sa thèse, invente les codes LDPC (Low-Density Parity-Check), dont on sait aujourd'hui qu'ils approchent la capacité. Les machines de l'époque ne peuvent pas les décoder, et ils sont oubliés pendant trente ans.
• 1993: Berrou, Glavieux et Thitimajshima présentent les turbocodes, qui approchent la capacité à quelques dixièmes de décibel près avec un décodage itératif praticable. La communauté met plusieurs mois à croire le résultat.
• 1996: MacKay et Neal redécouvrent les codes LDPC de Gallager et montrent qu'ils font aussi bien. Ils équipent aujourd'hui le Wi-Fi, la télévision numérique par satellite et le stockage.
• 2008: Arıkan publie les codes polaires, les premiers dont on démontre qu'ils atteignent la capacité pour tout canal binaire symétrique, avec un encodage et un décodage en $O(n\log n)$. Ils ont été retenus pour les canaux de contrôle de la 5G.

Quarante-cinq ans séparent l'énoncé du théorème de la première famille de codes praticables qui s'en approche, et soixante ans de la première dont on sache démontrer qu'elle l'atteint. Le théorème disait depuis 1948 que ces codes existaient.

Synthèse

• Le chapitre 7 retire la redondance subie d'une source; ce chapitre en ajoute une, choisie, mesurée et placée exprès. La compression précède toujours la protection, et cette séparation ne coûte rien.
• Un bit de parité détecte toute erreur de poids impair et aucune erreur de poids pair. Sur huit bits avec $p=0,01$, il intercepte $96,6\%$ des mots abîmés et en laisse passer $2,6$ pour mille. Il ne corrige rien.
• La distance de Hamming est une vraie distance; l'inégalité triangulaire donne les deux théorèmes fondamentaux: un code de distance minimale $d_{\min }$ détecte $d_{\min }-1$ erreurs et en . Le facteur deux est celui qui sépare «ne pas retomber sur un centre» de «rester dans le bon domaine».

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Hamming, R. W., Error Detecting and Error Correcting Codes, Bell System Technical Journal, vol. 29, n° 2, 1950 (l'article fondateur, remarquablement lisible).
• Shannon, C. E., A Mathematical Theory of Communication, Bell System Technical Journal, 1948 (le théorème du codage de canal y est le théorème 11).
• MacKay, D. J. C., Information Theory, Inference and Learning Algorithms, Cambridge University Press (chapitres 1, 8 à 11; librement disponible en ligne).
• Cover, T. M. et Thomas, J. A., Elements of Information Theory, 2e éd., Wiley, chapitre 7 (capacité et théorème du codage de canal).
• Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley (pour la place de ces codes dans les systèmes courants).
• Kurose, J. F. et Ross, K. W., Computer Networking: A Top-Down Approach, Pearson, section sur la détection d'erreurs au niveau liaison (parité, somme de contrôle, CRC).