Correction d'erreurs par code de Hamming expliquée (avec les calculs)

Encodez Hamming(7,4), calculez un syndrome, corrigez chaque erreur d'un bit, étendez le code en SECDED et vérifiez le décodeur sans exagérer ses capacités.

Denny

7 mai 20269 min de lecture

Chalkboard feature illustration for “Correction d'erreurs par code de Hamming expliquée (avec les calculs)”

En bref : Hamming(7,4) répartit quatre bits de données dans sept positions. Trois contrôles de parité attribuent à chaque position une colonne non nulle unique de trois bits ; lorsqu’un seul bit est inversé, le syndrome correspond donc à l’indice binaire de cette position. Le décodeur peut alors la réinverser. Le code Hamming(7,4) simple ne distingue pas une erreur de deux bits de certaines erreurs d’un bit ; l’ajout d’un bit de parité globale l’étend en SECDED dans les limites du modèle d’erreur supposé.

Un bit de parité peut signaler qu’un nombre impair de positions a changé, mais un seul contrôle ne permet pas d’identifier laquelle. La construction de Hamming emploie plusieurs contrôles de parité qui se chevauchent. Le motif des contrôles en échec — le syndrome — joue le rôle d’une adresse.

Cette idée est puissante, car l’encodeur, le contrôleur et le correcteur peuvent tous être réalisés avec des réseaux XOR et une logique de décodage. Elle possède aussi une limite stricte : la règle de correction familière suppose qu’au plus une erreur touche le bloc protégé, sauf si un code étendu ajoute un contrôle supplémentaire.

Positionnement des bits

Numérotez les positions du mot de code à partir de 1. Les puissances de deux accueillent la parité :

Position	1	2	3	4	5	6	7
Rôle	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Indice binaire	001	010	011	100	101	110	111

Chaque contrôle de parité correspond à un bit de la position binaire :

$P_1$ couvre les positions dont le bit 0 de l’indice vaut 1 : 1, 3, 5 et 7.
$P_2$ couvre les positions dont le bit 1 de l’indice vaut 1 : 2, 3, 6 et 7.
$P_4$ couvre les positions dont le bit 2 de l’indice vaut 1 : 4, 5, 6 et 7.

Chaque position possède un motif d’appartenance non nul unique. La position 5, par exemple, appartient aux contrôles 1 et 4 puisque $5=101_2$ .

Cette convention fondée sur un indice commençant à un est pratique, mais elle n’a rien de mystérieux : les colonnes de la matrice de contrôle de parité sont simplement les étiquettes binaires de 1 à 7.

Encodage avec une parité paire

Choisissez chaque bit de parité de sorte que le XOR de l’ensemble qu’il couvre soit nul :

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

Ces équations rendent le code systématique : les données d’origine apparaissent sans modification aux positions 3, 5, 6 et 7, tandis que la parité occupe les autres positions.

On pourrait employer une parité impaire en modifiant de manière cohérente les résultats attendus des contrôles. La parité paire rend la forme algébrique linéaire particulièrement directe, puisque tout mot de code valide possède un syndrome nul.

Exemple d’encodage : données 1011

Attribuons :

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

Alors :

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

Plaçons ces valeurs dans les sept positions :

Position	1	2	3	4	5	6	7
Rôle	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Bit	0	1	1	0	0	1	1

En lisant les positions de 1 à 7, on obtient le mot de code :

Certains ouvrages affichent les mots de code dans le sens visuel inverse. Le calcul reste correct dès lors que la convention de position est explicite et appliquée partout de façon cohérente.

Calcul du syndrome

Notons les positions reçues $R_1$ à $R_7$ . Recalculons les contrôles de parité complets :

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

Interprétons le syndrome comme suit :

S=(S_4S_2S_1)_2

Pour un mot de code valide et inchangé, $S=000$ . Si une seule position $i$ est inversée, chaque contrôle couvrant $i$ bascule. Le syndrome obtenu est alors la colonne binaire attribuée à la position $i$ .

Correction d’une inversion à la position 5

Inversons la position 5 de l’exemple encodé :

envoyé :  0 1 1 0 0 1 1
reçu :    0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

On obtient :

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

Par conséquent :

S_4S_2S_1=101_2=5

Sous l’hypothèse d’une seule erreur, inversez la position reçue 5. Le mot corrigé redevient 0110011, et les positions 3, 5, 6 et 7 restituent les données 1011.

Une inversion d’une position de parité fonctionne de la même manière. Si la position 2 change, le syndrome vaut 010 et le correcteur inverse la position 2.

Représentation matricielle

Avec le vecteur de mot de code

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

une matrice de contrôle de parité possible est :

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

Le syndrome vaut :

\mathbf s=H\mathbf r\pmod 2

La colonne $i$ de H est la représentation binaire de $i$ , ordonnée sous la forme $(S_1,S_2,S_4)^T$ . Un vecteur d’erreur d’un bit dont le 1 occupe la position $i$ renvoie donc exactement la colonne $i$ .

Cette formulation se généralise plus facilement que la mémorisation de cercles qui se chevauchent. Elle rend aussi la linéarité explicite : le XOR de deux mots de code valides produit un autre mot de code valide.

Pourquoi le code de Hamming simple ne peut pas corriger deux erreurs en toute sécurité

La distance de Hamming minimale de Hamming(7,4) est :

d_{\min}=3

Un code de distance minimale $d_{\min}$ peut :

détecter jusqu’à $d_{\min}-1$ erreurs quelconques s’il décide seulement si un mot est valide ou non ;
corriger jusqu’à $\left\lfloor(d_{\min}-1)/2\right\rfloor$ erreurs en choisissant le mot de code le plus proche.

Hamming(7,4) peut donc corriger une erreur. Il peut aussi détecter une altération de deux bits comme « n’étant pas un mot de code » si aucune correction n’est tentée. Mais son syndrome non nul de trois bits ne permet pas de savoir s’il provient d’une seule erreur ou d’une paire particulière d’erreurs.

Quand un décodeur standard à correction d’une erreur reçoit une erreur de deux bits, le XOR des colonnes correspondant aux deux positions erronées équivaut à une troisième colonne non nulle. Le décodeur inverse alors cette troisième position et crée une différence de trois bits par rapport au mot transmis. Il s’agit d’une correction erronée, et non d’une correction de deux erreurs.

Précisez toujours le modèle d’erreur supposé par le décodeur. La règle « syndrome non nul, donc inverser cette position » n’est valable que si le système a établi qu’au plus une position protégée est incorrecte.

Hamming étendu et SECDED

Ajoutez un bit de parité globale $P_0$ aux sept bits du mot de Hamming. Le code étendu à huit bits possède $d_{\min}=4$ et permet la correction d’une erreur et la détection de deux erreurs (SECDED), à condition qu’un mot de code ne contienne pas plus de deux erreurs.

Calculez :

le syndrome d’origine à trois bits S sur les positions 1 à 7 ;
un contrôle de parité globale P sur les huit positions reçues.

Pour une parité globale paire :

Syndrome S	Contrôle global P	Interprétation avec 0 à 2 erreurs	Action
000	0	aucune erreur	accepter
non nul	1	une erreur aux positions 1 à 7	corriger la position S
000	1	erreur dans la position de parité globale	corriger ou signaler l’erreur du bit de parité
non nul	0	deux erreurs	signaler une erreur incorrigible ; ne pas appliquer une correction simple

Cette restriction est essentielle. Trois erreurs ou davantage peuvent imiter une autre ligne du tableau. SECDED n’est pas un détecteur d’erreurs illimité.

Les systèmes réels de mémoire et de communication peuvent utiliser des codes de Hamming raccourcis, de l’entrelacement, des codes par symboles, des codes BCH ou Reed–Solomon, des codes LDPC, des codes produits ou des procédés propriétaires. Ne déduisez pas la capacité ECC d’un système à partir des seules largeurs visibles de ses données et bits de contrôle.

Dimensionnement général d’un code de Hamming

Pour $m$ bits de données et $r$ bits de parité de Hamming, il faut assez de motifs de syndrome pour représenter chaque position du mot de code ainsi que le cas sans erreur :

2^r\ge m+r+1

La famille binaire complète des codes de Hamming utilise :

n=2^r-1

k=n-r=2^r-r-1

Bits de parité r	Longueur n	Bits de données k	Code complet
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

Les variantes raccourcies omettent certaines positions de données tout en conservant la structure des contrôles. Les variantes étendues ajoutent le bit de parité globale et font passer la distance de 3 à 4.

Le surcoût doit toujours être accompagné de son dénominateur. Hamming(7,4) ajoute 3 bits de contrôle pour 4 bits de données : cela représente un surcoût de 75 % par rapport à la charge utile, ou 3/7 du mot transmis. Hamming(63,57) ajoute 6/57, soit environ 10,5 % par rapport à la charge utile ; les bits de contrôle occupent 6/63, soit environ 9,5 % du mot de code.

Architecture matérielle

Une implémentation systématique simple comporte quatre étages :

données ─▶ générateur de parité ─▶ mot de code
                                  │
mot reçu ─▶ matrice de contrôle ─▶ syndrome
                                      │
                       décodeur de syndrome ─▶ masque one-hot d'inversion
mot reçu ───────────────────────────── XOR ─▶ mot corrigé ─▶ extraction des données

Pour Hamming(7,4) :

l’encodeur calcule les trois équations de parité ;
le contrôleur calcule les trois équations du syndrome ;
un décodeur 3 vers 8 peut produire un masque de position one-hot, la sortie 0 signifiant qu’aucune correction n’est requise ;
sept portes XOR appliquent ce masque ;
le câblage extrait les positions 3, 5, 6 et 7.

Le nombre exact de portes et le timing dépendent de la factorisation des arbres XOR, des termes partagés, des bibliothèques de cellules ou de l’implémentation FPGA. Un décodeur large peut répartir le calcul du syndrome et la correction dans plusieurs étages de pipeline. Si un registre d’état signale « corrigé » et « incorrigible », alignez ces indicateurs sur l’étage de pipeline des données correspondantes.

Plan de vérification

Pour le code à sept bits :

Encoder les 16 entrées de données possibles.
Confirmer que chaque mot encodé possède un syndrome nul.
Pour chaque mot de code, inverser séparément chacune des sept positions.
Confirmer que le syndrome correspond à la position inversée.
Appliquer la correction et vérifier que les 16×7 cas restituent les données d’origine.
Injecter des erreurs représentatives de deux bits et montrer pourquoi un décodeur simple à correction d’une erreur effectue une correction erronée.

Pour la version étendue à huit bits :

Répéter chaque test d’une position, y compris pour la position de parité globale.
Tester les $\binom82=28$ motifs de deux positions pour chaque mot de données.
Vérifier que chaque paire est signalée comme incorrigible et qu’aucune correction simple n’est appliquée.
Ajouter des assertions garantissant que la correction n’est autorisée que pour S != 0 avec une discordance de parité globale.

La simulation fonctionnelle démontre la table de vérité implémentée pour les motifs de bits testés ou énumérés exhaustivement. Elle ne fournit pas un taux physique d’erreurs transitoires, ne démontre pas l’indépendance des défaillances et ne remplace pas une analyse de fiabilité au niveau du système.

Erreurs de conception fréquentes

Numéroter les positions à partir de zéro tout en interprétant le syndrome comme une adresse commençant à un.
Afficher le mot dans l’ordre inverse sans documenter la convention.
Mélanger un encodage à parité paire avec un contrôle à parité impaire.
Corriger tout syndrome non nul sans borner le nombre d’erreurs.
Considérer SECDED comme capable de détecter toute erreur de poids trois ou supérieur.
Oublier que les bits de contrôle et le bit de parité globale peuvent eux aussi être défaillants.
Comparer des « pourcentages de surcoût » utilisant des dénominateurs différents.
Supposer que tous les produits annoncés comme ECC implémentent le même code.

Hamming(7,4) est précieux parce que tout son mécanisme reste visible : des colonnes de contrôle de parité uniques transforment une erreur d’un bit en adresse. Une fois ce principe compris, la parité simple apparaît comme une matrice de contrôle à une ligne, tandis que les codes en blocs plus puissants deviennent des extensions de la même idée centrale — une redondance structurée adaptée à un modèle de défaillance explicite.

Référence

R. W. Hamming, « Error Detecting and Error Correcting Codes », Bell System Technical Journal, 1950