← Tous les textes du Grand Oral
MathsMaths expertesNSISI
Ce texte s'appuie sur l'option maths expertes : congruences modulo $2$, calcul matriciel. Côté spécialité : loi binomiale, dénombrement, Python.
Une rayure sur un disque, une tache sur un QR code, un rayon cosmique qui traverse une barrette de mémoire, un signal radio venu d'une sonde à vingt milliards de kilomètres : les données numériques sont sans cesse abîmées. Pourtant, la musique d'un disque rayé sort intacte et le QR code taché s'ouvre quand même. Ce n'est pas de la chance : avant d'envoyer ou d'enregistrer un message, on lui ajoute des bits calculés avec soin, qui permettent au destinataire de repérer et de réparer les erreurs. Ce sont les codes correcteurs d'erreurs.
Ce texte part des idées les plus simples (vérifier une parité, répéter) pour arriver au code inventé par Richard Hamming en 1950, que l'on peut entièrement comprendre avec les congruences et les matrices des maths expertes. Il rassemble des connaissances ; à chacun d'y choisir une direction et d'y construire sa question.
Un message numérique est une suite de bits, des $0$ et des $1$. On appelle canal tout ce qui le transporte ou le conserve : un câble, une onde radio, la surface d'un disque, une mémoire. Un canal réel fait des erreurs : de temps en temps, un $0$ devient un $1$ ou l'inverse.
Pour raisonner, on adopte un modèle simple, le canal binaire symétrique : chaque bit est inversé avec la même probabilité $p$, indépendamment des autres. Avec $p = 0{,}01$, un bit sur cent arrive faux. Envoyons des blocs de $4$ bits sans aucune protection : le nombre d'erreurs dans un bloc suit la loi binomiale de paramètres $4$ et $0{,}01$, et
$$P(\text{bloc faux}) = 1 - 0{,}99^4 \approx 0{,}039.$$Près de $4$ blocs sur $100$ arrivent abîmés, et le destinataire ne s'en aperçoit même pas. Pour une photo de plusieurs millions de bits, c'est inacceptable. Il existe deux réponses : détecter l'erreur pour redemander le message, ou la corriger directement. Quand le message vient d'une sonde qui met des heures à recevoir une demande, ou d'un disque qu'on ne peut pas relire autrement, seule la correction est possible.
Un bit est un reste dans la division par $2$. On calcule donc avec les congruences modulo $2$ : on ne garde que le reste, $0$ pour un nombre pair, $1$ pour un nombre impair. Les tables sont très courtes :
| $+$ | $0$ | $1$ | $\times$ | $0$ | $1$ | |
|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $0$ | $0$ | $0$ | |
| $1$ | $1$ | $0$ | $1$ | $0$ | $1$ |
La seule surprise est $1 + 1 \equiv 0 \pmod 2$. On en tire deux règles qui servent tout le temps : ajouter $1$ à un bit revient à l'inverser, et pour tout bit $x$, $x + x \equiv 0$ : soustraire et additionner, c'est la même chose. En informatique, cette addition s'appelle le « ou exclusif » (XOR). Une somme de bits modulo $2$ vaut $1$ exactement quand elle contient un nombre impair de $1$.
Voici la protection la plus simple. Pour envoyer les bits 1011, on ajoute un cinquième bit égal à leur somme modulo $2$ :
$$1 + 0 + 1 + 1 = 3 \equiv 1 \pmod 2.$$On envoie 10111 : la somme des cinq bits est maintenant paire. Le destinataire refait la somme ; si elle est impaire, il sait que le message a été abîmé.
Étape 1. Le mot envoyé $m$ a une somme $S \equiv 0 \pmod 2$.
Étape 2. Si un seul bit est inversé, ce bit change de $1$ : il passe de $0$ à $1$ (la somme augmente de $1$) ou de $1$ à $0$ (elle diminue de $1$). Dans les deux cas, la nouvelle somme vaut $S \pm 1 \equiv 1 \pmod 2$.
Étape 3. La somme reçue est impaire : l'erreur est détectée. Plus généralement, un nombre impair d'erreurs est toujours détecté, un nombre pair ne l'est jamais.
Le bit de parité a deux limites. Il ne dit pas quel bit est faux : on ne peut que redemander le message. Et deux erreurs se compensent : 10111 reçu en 01111 a encore une somme paire. Avec $p = 0{,}01$ et des mots de $8$ bits, la probabilité d'un nombre pair et non nul d'erreurs, qui passent inaperçues, vaut environ $0{,}0026$. Les premiers ordinateurs et les transmissions par modem utilisaient ce contrôle, et le numéro de Sécurité sociale ou les codes-barres emploient des cousins de cette idée, les clés de contrôle.
Pour corriger, l'idée la plus naturelle est de répéter. On envoie chaque bit trois fois : $0$ devient 000 et $1$ devient 111. Le destinataire décide à la majorité : 010 est lu comme $0$ et 110 comme $1$. Une erreur parmi les trois copies est donc corrigée.
Le décodage se trompe quand au moins deux des trois copies sont inversées. Le nombre $X$ de copies inversées suit la loi binomiale de paramètres $3$ et $p$, car les trois copies sont inversées indépendamment avec la même probabilité. Ainsi
$$\begin{aligned} P(X \geqslant 2) &= P(X = 2) + P(X = 3) \\ &= \binom{3}{2} p^2 (1 - p) + p^3 \\ &= 3p^2 - 2p^3. \end{aligned}$$Avec $p = 0{,}01$ :
$$3 \times 0{,}0001 - 2 \times 0{,}000\,001 = 0{,}000\,298.$$La probabilité qu'un bit soit faux passe de $0{,}01$ à environ $0{,}0003$ : elle est divisée par plus de $30$. Mais le prix est lourd : pour $1$ bit utile, on en envoie $3$. On dit que le rendement du code est de $\frac{1}{3}$ : la transmission est trois fois plus lente, ou le disque trois fois moins rempli. Toute la question est de faire aussi bien en payant moins.
À la fin des années 1940, Richard Hamming travaille aux laboratoires Bell, aux États-Unis, sur un calculateur à relais qui lit ses programmes sur des cartes perforées. Le calculateur sait détecter certaines erreurs de lecture ; en semaine, un opérateur intervient alors. Le week-end, la machine tourne seule : à la première erreur détectée, elle abandonne le travail et passe au suivant. Hamming raconte avoir trouvé, deux week-ends de suite, ses calculs abandonnés, et s'être demandé : si la machine sait qu'il y a une erreur, pourquoi ne trouve-t-elle pas où elle est, pour la corriger ? Sa réponse, publiée en 1950, est le code qui porte son nom. Le récit vient des souvenirs de Hamming lui-même et a sans doute été un peu arrangé avec le temps.
Le code de Hamming (7,4) transforme $4$ bits utiles en un mot de $7$ bits. On numérote les positions de $1$ à $7$. Les $4$ bits utiles $d_1, d_2, d_3, d_4$ sont placés aux positions $3$, $5$, $6$ et $7$ ; les positions $1$, $2$ et $4$, les puissances de $2$, reçoivent trois bits de contrôle. Chaque bit de contrôle est un bit de parité, mais sur un groupe de positions :
- le contrôle $c_1$ rend paire la somme des positions $1, 3, 5, 7$ ;
- le contrôle $c_2$ rend paire la somme des positions $2, 3, 6, 7$ ;
- le contrôle $c_4$ rend paire la somme des positions $4, 5, 6, 7$.
Le choix des groupes n'est pas un hasard. Écrivons chaque position en base $2$ : $5 = 101$, $6 = 110$ … Le groupe de $c_1$ réunit les positions dont l'écriture se termine par un $1$, celui de $c_2$ celles dont le chiffre des « deux » vaut $1$, celui de $c_4$ celles dont le chiffre des « quatre » vaut $1$. Chaque position appartient donc à une combinaison de groupes différente de toutes les autres : c'est ce qui va permettre de la retrouver.
Codons les $4$ bits 1011, c'est-à-dire $d_1 = 1$, $d_2 = 0$, $d_3 = 1$, $d_4 = 1$. Ils vont aux positions $3$, $5$, $6$ et $7$. On calcule les contrôles modulo $2$ :
$$\begin{aligned} c_1 &\equiv d_1 + d_2 + d_4 = 1 + 0 + 1 \equiv 0, \\ c_2 &\equiv d_1 + d_3 + d_4 = 1 + 1 + 1 \equiv 1, \\ c_4 &\equiv d_2 + d_3 + d_4 = 0 + 1 + 1 \equiv 0. \end{aligned}$$En rangeant les sept bits dans l'ordre des positions, on obtient le mot envoyé 0110011 : positions $1$ à $7$, on lit $c_1$, $c_2$, $d_1$, $c_4$, $d_2$, $d_3$, $d_4$.
En maths expertes, on range les bits utiles dans une matrice colonne $D$ à $4$ lignes et le mot envoyé dans une matrice colonne $C$ à $7$ lignes. Les formules de codage sont linéaires : chaque bit du mot est une somme de bits utiles. Elles s'écrivent donc $C = G \times D$ modulo $2$, avec la matrice génératrice
$$G = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$$La ligne $i$ de $G$ dit quels bits utiles on additionne pour obtenir le bit de position $i$ : la première ligne $(1\ 1\ 0\ 1)$ traduit $c_1 = d_1 + d_2 + d_4$, la troisième $(1\ 0\ 0\ 0)$ recopie $d_1$ en position $3$. Avec $D = (1\ 0\ 1\ 1)$ en colonne, le calcul ligne par ligne redonne 0110011. Comme $D$ peut prendre $2^4 = 16$ valeurs, le code contient $16$ mots, parmi les $2^7 = 128$ mots de $7$ bits.
Les trois règles de parité s'écrivent elles aussi comme un produit. On forme la matrice de contrôle $H$ à $3$ lignes et $7$ colonnes, dont la colonne $j$ est l'écriture de $j$ en base $2$ (de haut en bas : chiffre des quatre, des deux, des unités) :
$$H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}.$$La première ligne de $H$ a des $1$ aux positions $4, 5, 6, 7$ : c'est le groupe du contrôle $c_4$. La deuxième correspond au groupe de $c_2$, la troisième à celui de $c_1$. Pour un mot reçu $R$, on appelle syndrome la matrice colonne $S = H \times R$ modulo $2$ : ses trois coefficients sont les trois sommes de contrôle.
Étape 1 : un mot du code a un syndrome nul. Si $C$ est un mot du code, chacune des trois lignes de $H \times C$ est la somme d'un groupe de contrôle, qui est paire par construction. Donc $H \times C \equiv 0$. On peut le vérifier d'un coup : le produit $H \times G$ est la matrice nulle modulo $2$. Par exemple, la première colonne de $G$ a des $1$ aux positions $1, 2, 3$, et chaque ligne de $H$ contient un nombre pair de $1$ parmi ces trois positions ($0$, $2$ et $2$).
Étape 2 : une erreur s'écrit comme une addition. Inverser le bit de position $j$, c'est lui ajouter $1$ modulo $2$. Si $E_j$ est la colonne de $7$ bits nulle sauf un $1$ en ligne $j$, le mot reçu est $R = C + E_j$.
Étape 3 : on utilise la distributivité du produit matriciel.
$$\begin{aligned} H \times R &= H \times C + H \times E_j \\ &\equiv 0 + H \times E_j \pmod 2. \end{aligned}$$Étape 4 : on calcule $H \times E_j$. Multiplier une matrice par $E_j$ extrait sa colonne $j$. Le syndrome est donc la colonne $j$ de $H$, qui est par construction l'écriture de $j$ en base $2$.
Conclusion. Le syndrome est nul s'il n'y a pas d'erreur, et sinon il donne directement la position du bit faux : il suffit d'inverser ce bit pour retrouver le mot envoyé.
Exemple complet. On a envoyé 0110011 et le bit de position $6$ a été inversé : on reçoit 0110001. Calculons les trois lignes du syndrome :
- positions $4, 5, 6, 7$ : $0 + 0 + 0 + 1 = 1$ ;
- positions $2, 3, 6, 7$ : $1 + 1 + 0 + 1 = 3 \equiv 1$ ;
- positions $1, 3, 5, 7$ : $0 + 1 + 0 + 1 = 2 \equiv 0$.
Le syndrome se lit 110, c'est-à-dire $4 + 2 = 6$ : le bit faux est en position $6$. On l'inverse, on retrouve 0110011, puis on lit les bits utiles aux positions $3, 5, 6, 7$ : 1011. Le destinataire a réparé l'erreur sans rien demander à personne.
La distance de Hamming entre deux mots de même longueur est le nombre de positions où ils diffèrent. Entre 0110011 et 0110001, elle vaut $1$ ; entre 0000000 et 1110000, elle vaut $3$. Elle vérifie l'inégalité triangulaire $d(x, z) \leqslant d(x, y) + d(y, z)$ : à chaque position où $x$ et $z$ diffèrent, le mot $y$ diffère forcément de $x$ ou de $z$, donc cette position est comptée au moins une fois à droite.
Un canal qui fait $k$ erreurs déplace le mot envoyé à la distance $k$ de lui-même. Corriger, c'est remplacer le mot reçu par le mot du code le plus proche. Cela ne marche que si les mots du code sont bien écartés les uns des autres.
Étape 1 : on se ramène à un seul mot. Si $C$ et $C'$ sont deux mots du code, leur somme $C + C'$ a un $1$ exactement là où ils diffèrent. C'est encore un mot du code, car $H \times (C + C')$ $= H \times C + H \times C'$ $\equiv 0$. La distance entre $C$ et $C'$ est donc le nombre de $1$ d'un mot non nul du code : il suffit de montrer qu'un mot non nul du code contient au moins trois $1$.
Étape 2 : pas de mot avec un seul $1$. Un tel mot est un $E_j$, et $H \times E_j$ est la colonne $j$ de $H$, qui n'est pas nulle. Ce n'est pas un mot du code.
Étape 3 : pas de mot avec deux $1$. Un tel mot est $E_i + E_j$ avec $i \neq j$, et $H \times (E_i + E_j)$ est la somme des colonnes $i$ et $j$. Cette somme est nulle modulo $2$ seulement si les deux colonnes sont égales, ce qui est faux puisque les colonnes de $H$ sont les écritures de sept nombres différents.
Conclusion. Un mot non nul du code contient au moins trois $1$, et la distance minimale vaut exactement $3$ puisque 1110000 est un mot du code.
Conséquence : une erreur est toujours corrigée. Si le mot reçu $R$ est à la distance $1$ du mot envoyé $C$, alors pour tout autre mot $C'$ du code, l'inégalité triangulaire donne
$$\begin{aligned} d(R, C') &\geqslant d(C, C') - d(C, R) \\ &\geqslant 3 - 1 = 2. \end{aligned}$$Le mot envoyé est le seul mot du code à la distance $1$ : le choisir ne laisse aucun doute. Avec deux erreurs, en revanche, le mot reçu peut se trouver plus près d'un autre mot du code : le code de Hamming (7,4) corrige une erreur, pas deux.
Autour de chaque mot du code, considérons la boule formée du mot lui-même et des $7$ mots obtenus en inversant un seul de ses bits : elle contient $1 + 7 = 8$ mots. Deux boules ne se touchent pas : un mot commun serait à la distance $1$ de deux mots du code, qui seraient alors à une distance au plus $2$, ce qui est impossible. Les $16$ boules disjointes contiennent donc
$$16 \times 8 = 128 = 2^7 \text{ mots}.$$C'est exactement le nombre total de mots de $7$ bits. Les boules remplissent tout l'espace sans se chevaucher : chaque mot reçu, quel qu'il soit, est à la distance au plus $1$ d'un unique mot du code. On dit que le code est parfait : aucun bit de contrôle n'est gaspillé. Ce n'est pas un hasard de petits nombres : avec $r$ bits de contrôle, le syndrome peut prendre $2^r$ valeurs, une pour « pas d'erreur » et une pour chaque position ; il faut donc $n + 1 \leqslant 2^r$, et les codes de Hamming réalisent l'égalité $n = 2^r - 1$ : $7$ bits avec $3$ contrôles, $15$ avec $4$, $31$ avec $5$ …
Le code de Hamming envoie $7$ bits pour $4$ bits utiles : son rendement est $\frac{4}{7} \approx 0{,}57$, bien meilleur que le $\frac{1}{3}$ de la répétition. Un bloc de $4$ bits utiles est mal décodé quand au moins deux des $7$ bits sont inversés. Notons $F$ cet événement et $X$ le nombre de bits inversés, qui suit la loi binomiale de paramètres $7$ et $p$ :
$$\begin{aligned} P(F) &= 1 - P(X = 0) - P(X = 1) \\ &= 1 - (1 - p)^7 - 7p(1 - p)^6. \end{aligned}$$Pour la répétition, chacun des $4$ bits utiles est faux avec la probabilité $q = 3p^2 - 2p^3$, donc le bloc est faux avec la probabilité $1 - (1 - q)^4$. Avec $p = 0{,}01$ :
| Stratégie | Bits envoyés pour 4 bits utiles | P(bloc faux) |
|---|---|---|
| Aucune protection | $4$ | $\approx 0{,}0394$ |
| Répéter trois fois | $12$ | $\approx 0{,}0012$ |
| Hamming (7,4) | $7$ | $\approx 0{,}0020$ |
Hamming divise le risque par environ $20$ en ajoutant seulement $3$ bits, là où la répétition en ajoute $8$. La figure ci-dessous montre ces trois probabilités quand $p$ varie.
Choisissez les $4$ bits utiles en cliquant dessus, puis jouez le rôle du canal : cliquez sur un bit du mot envoyé pour l'inverser. Le décodeur calcule le syndrome et corrige. Essayez ensuite d'abîmer deux bits : le décodeur se trompe, comme prévu par la théorie.
Les cases orange sont les bits de contrôle (positions $1$, $2$ et $4$), les cases bleu-vert les bits utiles. Une case entourée de rouge est un bit inversé par le canal.
Le programme suivant envoie des milliers de blocs de $4$ bits à travers un canal qui inverse chaque bit avec la probabilité $p$, avec les trois stratégies, et compte les blocs mal reçus. D'après la loi des grands nombres, plus le nombre de blocs est grand, plus il est probable que chaque fréquence observée soit proche de la probabilité calculée plus haut. Avec $p = 0{,}05$, ces probabilités valent environ $0{,}185$, $0{,}029$ et $0{,}044$.
Changez la valeur de p : au-delà de $0{,}2$, on voit les codes perdre leur efficacité. Pour un canal très
bruité, il faut des codes plus longs et plus puissants.
En 1948, deux ans avant la publication de Hamming, son collègue des laboratoires Bell Claude Shannon démontre un théorème surprenant : tout canal a une capacité, et l'on peut transmettre avec une probabilité d'erreur aussi petite qu'on veut à tout rendement inférieur à cette capacité. Pour le canal binaire symétrique avec $p = 0{,}01$, la capacité est d'environ $0{,}92$ : on pourrait en théorie envoyer $92$ bits utiles pour $100$ bits transmis, presque sans erreur. Mais Shannon prouve que de tels codes existent sans dire comment les construire. Les décennies suivantes ont été une longue course pour s'approcher de cette limite ; les codes « turbo » (1993) et les codes LDPC, utilisés dans la 4G, la 5G et le wifi, en sont aujourd'hui très proches. Le texte Claude Shannon, Ed Thorp et le hasard vaincu raconte la vie de Shannon.
Sur un CD, une rayure ne touche pas un bit isolé mais des milliers de bits consécutifs : c'est une erreur en rafale, contre laquelle le code de Hamming ne peut rien. Les CD utilisent des codes de Reed et Solomon (1960), qui travaillent non pas sur des bits mais sur des octets, vus comme les éléments d'un corps fini à $256$ éléments, et qui s'appuient sur des polynômes. On les combine avec un entrelacement : les octets d'un même bloc sont dispersés le long de la piste, si bien qu'une rayure abîme un peu de nombreux blocs plutôt que beaucoup d'un seul. D'après les descriptions de la norme, une rafale de l'ordre de plusieurs milliers de bits, soit environ $2$ mm de piste, est corrigée entièrement.
Un QR code contient lui aussi des octets de contrôle de Reed-Solomon. La norme prévoit quatre niveaux, notés L, M, Q et H : au niveau H, environ $30\,\%$ des données peuvent être perdues sans que le code devienne illisible. C'est ce qui permet d'imprimer un logo au milieu d'un QR code ou de le lire malgré une tache : le prix est un code plus dense, avec plus de petits carrés.
La sonde Mariner 9, en orbite autour de Mars en 1971, envoyait ses images avec un code de Reed et Muller qui transformait $6$ bits en $32$ : un rendement faible, mais capable de corriger jusqu'à $7$ erreurs par mot. Les sondes Voyager, lancées en 1977, ont utilisé un code de Golay pour les images de Jupiter et Saturne, puis, plus loin dans le système solaire, un code de Reed-Solomon combiné à un code dit convolutif. Plus la sonde s'éloigne, plus le signal est faible et plus le code doit être fort : c'est l'une des raisons pour lesquelles Voyager communique encore, à un débit de l'ordre de la centaine de bits par seconde.
Dans la mémoire d'un ordinateur, un rayon cosmique ou une particule radioactive peut inverser un bit. Les serveurs, les avions et les satellites utilisent des mémoires dites ECC (pour error-correcting code), qui protègent chaque groupe de $64$ bits par $8$ bits de contrôle : c'est un code de Hamming allongé d'un bit de parité global, qui corrige une erreur et détecte deux erreurs. Vérifiez la condition du dénombrement : avec $7$ bits de contrôle, $2^7 = 128 \geqslant 64 + 7 + 1$, et le huitième bit sert à la détection des doubles erreurs.
Ce texte n'est pas un Grand Oral. Il rassemble des connaissances dans lesquelles chacun peut choisir une direction, la creuser et formuler sa propre question. Quelques directions possibles :
- Mathématiques : le calcul modulo $2$ et le bit de parité ; la loi binomiale pour comparer des stratégies ; les matrices génératrice et de contrôle, le syndrome ; la distance de Hamming et l'inégalité triangulaire ; le dénombrement qui rend un code parfait.
- NSI : programmer un codeur et un décodeur ; le ou exclusif sur les octets ; simuler un canal bruité ; la différence entre détecter puis redemander, et corriger.
- SI : la lecture d'un CD ou d'un QR code ; les transmissions avec les sondes spatiales ; la fiabilité des mémoires dans l'aéronautique et l'espace.
Le jury peut interroger sur les chapitres mobilisés. Avec ce thème, il est utile de connaître parfaitement, en maths expertes : les congruences et leurs règles de calcul, le produit de matrices et sa distributivité. Côté spécialité : la loi binomiale et le calcul de $P(X \geqslant k)$, les coefficients binomiaux, le principe multiplicatif du dénombrement, les boucles et les listes en Python.
Pour réviser les chapitres de spécialité, l'application Maths FlashBac reprend tout le cours en cartes.
- Code de Hamming, code de Reed-Solomon et code correcteur (Wikipédia).
- Sur ce site : La cryptographie (cacher un message, quand les codes correcteurs cherchent à le protéger), Claude Shannon, Ed Thorp et le hasard vaincu et Le triangle de Pascal (les coefficients binomiaux).