Code de Hamming : corriger un bit en repérant sa position

Choisissez les quatre bits de données, puis inversez les bits de votre choix dans le canal, à l’aide des boutons ou en cliquant sur le schéma. Le décodeur refait les trois contrôles de parité, lit leurs échecs comme un nombre binaire et inverse le bit ainsi désigné. Parcourez les étapes une fois, puis essayez deux inversions.

Exemple résolu — Code de Hamming : corriger un bit en repérant sa position

Mot envoyé : bits de contrôle	0110011
Mot reçu	0110111
Syndrome	1012
Données restituées	1011
Rendement, bits de données par bit envoyé	57,1%

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Code de Hamming : corriger un bit en repérant sa position

Un code de Hamming ajoute des bits de contrôle aux données afin de repérer et de réinverser un bit erroné. Chaque bit de contrôle impose une parité paire à un ensemble choisi de positions : c’est un contrôle de parité. Le décodeur répète ces contrôles sur le mot reçu. Le motif des échecs, appelé syndrome, se lit comme un nombre binaire qui donne la position du bit erroné ; 0 signifie qu’il n’y en a aucun. Un chiffre de contrôle indique seulement qu’une erreur existe ; ici, sa position est connue. Le code étendu ajoute un bit qui rend paire la parité du mot entier. Il corrige alors toute inversion unique et détecte toute paire d’inversions sans la corriger : c’est le principe SECDED.

Ce que signifie chaque symbole

dᵢ: les quatre bits de données, aux positions 3, 5, 6 et 7
p₁, p₂, p₄: les bits de contrôle, chacun placé à la position qui lui donne son nom ; p₀ est le bit de parité globale du code étendu
s: le syndrome, 4s₄ + 2s₂ + s₁, où s_k vaut 1 lorsque le cercle k contient un nombre impair de uns à l’arrivée
P: la parité des huit bits reçus dans le code étendu : 1 indique un nombre impair d’inversions
p: le taux d’erreur binaire, c’est-à-dire la probabilité qu’un bit donné s’inverse, indépendamment de tous les autres

Suppose: Chaque bit s’inverse indépendamment, avec la même probabilité p. Les canaux et les mémoires réels connaissent aussi des erreurs en rafale, qui touchent plusieurs bits voisins à la fois. Or une rafale constitue précisément le type d’inversions multiples que ces codes gèrent le moins bien.
Ne tient plus quand: À partir de trois inversions. Le code étendu interprète trois inversions comme une seule, car le contrôle global devient impair, puis corrige un bit qui était juste : le tableau exhaustif montre que les 896 triples inversions produisent toutes des données erronées sans signalement.

La somme des cercles en échec donne le bit inversé 🖖

Appuyez sur Une inversion. Le bit 5 est inversé dans le canal : les cercles 1 et 4 contiennent maintenant un nombre impair de uns, tandis que le cercle 2 reste pair. Ainsi, 1 + 4 = 5. Ce résultat ne dépend pas d’un choix avantageux du préréglage. Le cercle k contrôle exactement les positions dont l’écriture binaire contient k. Une erreur en position i perturbe donc précisément les cercles dont la somme vaut i : la place d’un bit dans le schéma est aussi son adresse. En 1950, Hamming cherchait justement un « nombre de contrôle » donnant la position de toute erreur unique, zéro signifiant qu’il n’y en a aucune. Trois contrôles offrent huit réponses ; le mot de sept bits en exige exactement huit, une pour chacune des sept positions et une pour « aucune erreur ». Il ne reste donc aucune possibilité libre : parmi les 128 mots de sept bits, 16 sont des mots du code et les 112 autres s’obtiennent chacun par une seule inversion d’un unique mot du code. Le tableau sous le graphique décode correctement les 112. La présence des bits de contrôle aux positions 1, 2 et 4 a une raison simple. Leur écriture binaire ne contient qu’un seul 1 : chaque bit de contrôle n’appartient donc qu’à un cercle et peut être fixé par son propre contrôle, comme l’expliquait Hamming.

Deux inversions, et le décodeur endommage un troisième bit 🖖

Appuyez sur Deux inversions. Les bits 3 et 5 deviennent erronés. Le cercle 1 les contient tous les deux : perturbé deux fois, il reste pair. Les cercles 2 et 4 deviennent impairs, si bien que le syndrome vaut 6, une position parfaitement valide. Le décodeur inverse alors le bit 6, qui était juste. Deux bits de données étaient erronés à l’arrivée ; après correction, ils sont trois. La grille montre le même résultat pour chaque paire : les 21 paires, et donc les 336 doubles inversions sur les 16 mots de données, produisent des données erronées sans signalement. Appuyez sur Bits de contrôle seuls : les positions 1 et 2 ne portent aucune donnée, les données arrivent intactes, mais le syndrome 3 conduit le décodeur à endommager d₁. Appuyez maintenant sur Étendu, deux inversions. Le huitième bit rend paire la parité des huit bits ; une inversion rend donc toujours le contrôle global impair, et deux le laissent toujours pair. Devant une parité globale paire et un syndrome non nul, le décodeur signale le mot sans rien modifier, dans les 448 cas de double inversion. Il ne peut pas les corriger : les positions 3 et 5 donnent le syndrome 6, tout comme les positions 1 et 7. Le signalement fut le point de départ de Hamming. Son article de 1950 s’ouvre sur les deux calculateurs à relais construits par les laboratoires Bell pour l’Aberdeen Proving Ground. Ils ne laissaient passer aucune panne de relais sans la détecter ; au début, il s’en produisait environ deux ou trois par jour parmi 8 900 relais. Laissées sans surveillance la nuit et le week-end, les machines s’arrêtaient fréquemment.

Envoyer chaque bit deux fois coûte aussi huit bits et ne corrige rien 🖖

L’envoi de chaque bit en double et le code étendu consacrent tous deux huit bits à quatre bits de données. Si les deux copies d’un bit diffèrent, le récepteur sait qu’une erreur s’est produite, mais ignore laquelle est juste ; il ne peut que signaler le bloc. Pour p = 0,01, cela concerne 7,69×10⁻² des blocs, tandis que 3,77×10⁻⁴ passent avec une erreur lorsque les deux copies d’un même bit s’inversent ensemble. Le code de Hamming étendu corrige toute inversion unique, signale 2,64×10⁻³ des blocs et en laisse passer 5,34×10⁻⁵ avec une erreur : à budget égal, il produit 29 fois moins de signalements et 7 fois moins de blocs erronés. Les courbes en tirets et en trait plein le donnent gagnant sur les deux critères jusqu’à p = 0,066, soit un canal qui inverse un bit sur quinze. Trois copies de chaque bit font mieux que le code à sept bits par bloc pour toutes les valeurs de p proposées par le curseur, ici 1,19×10⁻³ contre 2,03×10⁻³. Elles demandent toutefois 12 bits au lieu de 7 ; la comparaison équitable reste donc celle à huit bits.

Problème entièrement résolu

Combien de bits de contrôle faut-il pour un mot de 64 bits ? 4 étapes
Protégez 64 bits de données de la même manière. Appuyez sur Étendu, une inversion : quatre bits de contrôle pour quatre bits de données, soit un rendement de 50,0 %. Déterminez combien de bits de contrôle exige un mot de 64 bits pour offrir la même garantie — corriger toute inversion unique et signaler toute paire d’inversions — puis calculez le coût du mot plus long pour la valeur p = 0,001 de ce préréglage.

Ouvrez ce problème dans l'outil
1. Avec r bits de contrôle, le syndrome peut prendre 2^r valeurs. L’une doit signifier « aucune erreur », et chacune des m + r positions doit avoir sa propre valeur ; il faut donc 2^r ≥ m + r + 1. Sur cette page, m = 4 et r = 3 satisfait exactement l’inégalité, sans aucune valeur libre.
  
  $2^{r} \geq m + r + 1, m = 4 : 2^{3} = 8 = 4 + 3 + 1$
2. Pour m = 64, six bits de contrôle donnent 64 valeurs, alors qu’il en faut 71 ; sept en donnent 128, assez pour 72 positions. Un mot de 71 bits corrige donc toute inversion unique.
  
  $m = 64 : 2^{6} = 64 < 71, 2^{7} = 128 \geq 72 \Rightarrow r = 7, n = 71$
3. L’ajout d’un bit de parité globale porte la longueur à 72 bits, dont 8 bits de contrôle, pour un rendement de 88,9 % au lieu des 50,0 % affichés sur la page.
  
  $n = 64 + 7 + 1 = 72, \frac{64}{72} = 88 . 9%$
4. Un mot plus long recueille plus souvent deux inversions, précisément le cas que SECDED ne sait plus réparer. Pour un mot de 8 bits, cette probabilité est la somme des deux valeurs indiquées sur la page.
  
  $P_{\geq 2} (n) = 1 - q^{n} - n p q^{n - 1}, P_{\geq 2} (8) = 2.78 \times 1 0^{- 5} + 5.57 \times 1 0^{- 8} = 2.79 \times 1 0^{- 5}$
Réponse

Huit bits de contrôle, un mot de 72 bits, un rendement de 88,9 %. Pour p = 0,001, la probabilité qu’il subisse au moins deux inversions est de 2,44×10⁻³. Si les mêmes 64 bits sont répartis entre seize mots de 8 bits, ils sont perdus dès que l’un de ces mots l’est, avec une probabilité de 4,46×10⁻⁴. Le mot long risque donc environ 5,5 fois plus de perdre ses 64 bits, en échange de huit fois moins de bits de contrôle.

$P_{\geq 2} (72) = 2.44 \times 1 0^{- 3}, 1 - (1 - P_{\geq 2} (8))^{16} = 4.46 \times 1 0^{- 4}, \frac{2 . 44}{0 . 446} \approx 5.5$

Parcours

Pourquoi un algorithme est correct

Références (2)

The code itself, the requirement that the checking number give the position of any single error, the check positions 1, 2, 4 and the reason for them, the extended code that adds double-error detection, and the relay computers that motivated it: R. W. Hamming, "Error Detecting and Error Correcting Codes." Bell System Technical Journal 29(2), April 1950, pp. 147-160. DOI 10.1002/j.1538-7305.1950.tb00463.x
How Hamming told the story in his later course: a relay computer that could detect an error, retried three times and then dropped the problem, and the question that followed: R. W. Hamming, The Art of Doing Science and Engineering: Learning to Learn, Session 12, "Error-Correcting Codes". Lecture slides, Naval Postgraduate School, Monterey (course delivered 1995).

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.