Code de Hamming

informatique et en télécommunications , les codes de Hamming constituent une famille de codes correcteurs d'erreurs linéaires . Ils peuvent détecter les erreurs d'un bit et de deux bits, ou corriger les erreurs d'un bit sans détecter les erreurs non corrigées. À l'inverse, le code de parité simple ne peut corriger les erreurs et ne détecte qu'un nombre impair de bits erronés. Les codes de Hamming sont des codes parfaits : ils atteignent le taux de correction maximal possible pour des codes de même longueur de bloc et de distance minimale de trois bits. Richard W. Hamming a inventé les codes de Hamming en 1950 afin de corriger automatiquement les erreurs introduites par les lecteurs de cartes perforées . Dans son article original, Hamming a développé son idée générale, mais s'est concentré plus particulièrement sur le code Hamming(7,4) qui ajoute trois bits de parité à quatre bits de données.

En termes mathématiques , les codes de Hamming sont une classe de codes binaires linéaires. À chaque entier $longueur de bloc de longueur de message matrice de contrôle de parité d'un code de Hamming est construite en listant toutes les colonnes de longueur code dual du code de Hamming est donc le code de Hadamard simplifié, également appelé code simplex. La matrice de contrôle de parité a la propriété que deux à deux quelconques de ses colonnes sont linéairement indépendantes .$

En raison de la redondance limitée qu'ils ajoutent aux données, les codes de Hamming ne peuvent détecter et corriger les erreurs que lorsque le taux d'erreur est faible. C'est le cas dans la mémoire vive (RAM), où les erreurs binaires sont extrêmement rares et où les codes de Hamming sont largement utilisés. La mémoire dotée de ce système de correction est appelée mémoire ECC . Dans ce contexte, on utilise souvent un code de Hamming étendu, comportant un bit de parité supplémentaire. Les codes de Hamming étendus atteignent une distance de Hamming de quatre, ce qui permet au décodeur de distinguer une erreur binaire unique d'une erreur binaire quelconque. En ce sens, les codes de Hamming étendus corrigent les erreurs simples et détectent les erreurs doubles ( SECDED) .

Richard Hamming , l'inventeur des codes de Hamming, travaillait aux laboratoires Bell à la fin des années 1940 sur l' ordinateur Bell modèle V , une machine électromécanique à relais dont le temps de cycle se mesurait en secondes. Les données étaient saisies sur une bande de papier perforée de 2,2 cm de large, comportant jusqu'à six trous par rangée. En semaine, lorsqu'une erreur était détectée au niveau des relais, la machine s'arrêtait et des voyants clignotaient afin que les opérateurs puissent corriger le problème. En dehors des heures de travail et le week-end, en l'absence d'opérateurs, la machine passait simplement à la tâche suivante.

Hamming travaillait les week-ends et était de plus en plus frustré de devoir recommencer ses programmes à partir de zéro à cause des erreurs détectées. Dans un entretien enregistré, il déclara : « Je me suis dit : “Bon sang ! Si la machine peut détecter une erreur, pourquoi ne peut-elle pas la localiser et la corriger ?” » . Au cours des années suivantes, il travailla sur le problème de la correction d’erreurs, développant un ensemble d’algorithmes de plus en plus performants. En 1950, il publia ce que l’on appelle aujourd’hui le code de Hamming, toujours utilisé de nos jours dans des applications telles que la mémoire ECC .

Codes antérieurs à Hamming

Plusieurs codes simples de détection d'erreurs ont été utilisés avant les codes de Hamming, mais aucun n'était aussi efficace que les codes de Hamming pour un même encombrement spatial.

Parité

bit indiquant si le nombre de bits à 1 (positions de bits valant 1) dans les données précédentes était pair ou impair . Si un nombre impair de bits est modifié lors de la transmission, la parité du message change et l'erreur peut être détectée à ce stade ; toutefois, le bit modifié peut être le bit de parité lui-même. Par convention, une parité de 1 indique un nombre impair de bits à 1 dans les données, et une parité de 0 indique un nombre pair de bits à 1. Si le nombre de bits modifiés est pair, le bit de contrôle est valide et l'erreur n'est pas détectée.

De plus, la parité n'indique pas quel bit contient l'erreur, même lorsqu'elle la détecte. Les données doivent être entièrement rejetées et retransmises depuis le début. Sur un support de transmission bruité , une transmission réussie peut prendre beaucoup de temps, voire ne jamais avoir lieu. Cependant, malgré sa faible précision, due à l'utilisation d'un seul bit, la méthode de parité présente la surcharge la plus faible.

Code deux sur cinq

code 2 sur 5 est un schéma de codage qui utilise cinq bits, composés exactement de trois 0 et de deux 1. Cela permet

Ce système offre suffisamment de combinaisons possibles pour représenter les chiffres de 0 à 9. Il peut détecter toutes les erreurs sur un seul bit, toutes les erreurs sur un bit impair et certaines erreurs sur un bit pair (par exemple, l'inversion des deux bits à 1). Cependant, il ne peut corriger aucune de ces erreurs.

Répétition

code à répétition nomenclature pour décrire le système, incluant le nombre de bits de données et de bits de correction d'erreurs dans un bloc. Par exemple, la parité comprend un bit pour chaque mot de données. Ainsi, en supposant des mots ASCII de sept bits, Hamming a décrit cela comme un code (8,7) , avec huit bits au total, dont sept sont des données. L'exemple de répétition serait (3,1) , suivant la même logique. Le taux de codage est le second nombre divisé par le premier, soit 1/3 dans notre exemple de répétition.

Hamming a également constaté les problèmes liés à l'inversion de deux bits ou plus et a décrit cela comme la « distance » (désormais appelée distance de Hamming , en son honneur). La parité a une distance de 2 ; ainsi, une inversion de bit peut être détectée mais non corrigée, et toute inversion de deux bits sera invisible. La répétition (3,1) a une distance de 3, car trois bits doivent être inversés dans le même triplet pour obtenir un autre mot de code sans erreur visible. Elle peut corriger les erreurs d'un bit ou détecter – mais pas corriger – les erreurs de deux bits. Une répétition (4,1) (chaque bit est répété quatre fois) a une distance de 4 ; ainsi, l'inversion de trois bits peut être détectée mais non corrigée. Lorsque trois bits sont inversés dans le même groupe, il peut arriver que toute tentative de correction produise un mot de code erroné. En général, un code de distance k peut détecter mais ne peut pas corriger XOR de tous les bits contenant un 1) soit égal à 0. Nous utilisons les positions 1, 10, 100, etc. (en binaire) comme bits correcteurs d'erreurs, ce qui garantit qu'il est possible de les configurer de sorte que l'indice XOR du message entier soit égal à 0. Si le destinataire reçoit une chaîne dont l'indice XOR est égal à 0, il peut conclure qu'il n'y a pas eu de corruption ; sinon, l'indice XOR indique l'indice du bit corrompu.

Un algorithme peut être déduit de la description suivante :

Numérotez les bits en commençant par 1 : bit 1, 2, 3, 4, 5, 6, 7, etc.
Écrivez les nombres binaires : 1, 10, 11, 100, 101, 110, 111, etc.
Tous les bits dont la position est une puissance de deux (qui ont un seul bit 1 dans la forme binaire de leur position) sont des bits de parité : 1, 2, 4, 8, etc. (1, 10, 100, 1000).
Toutes les autres positions binaires, comportant deux bits à 1 ou plus dans leur représentation binaire, sont des bits de données.
Chaque bit de données est inclus dans un ensemble unique de 2 bits de parité ou plus, déterminé par la forme binaire de sa position de bit.
1. Le bit de parité 1 couvre toutes les positions de bits dont le bit de poids faible est activé : bit 1 (le bit de parité lui-même), 3, 5, 7, 9, etc.
2. Le bit de parité 2 couvre toutes les positions de bits dont le deuxième bit le moins significatif est activé : bits 2–3, 6–7, 10–11, etc.
3. Le bit de parité 4 couvre toutes les positions de bits dont le troisième bit le moins significatif est activé : bits 4–7, 12–15, 20–23, etc.
4. Le bit de parité 8 couvre toutes les positions de bits dont le quatrième bit le moins significatif est activé : bits 8–15, 24–31, 40–47, etc.
5. En général, chaque bit de parité couvre tous les bits où le ET bit à bit de la position de parité et de la position du bit est non nul.

Si un octet de données à encoder est 10011010, alors le mot de données (en utilisant _ pour représenter les bits de parité) serait __1_001_1010, et le mot de code est 011100101010.

Le choix de la parité, paire ou impaire, est sans importance, mais le même choix doit être utilisé pour l'encodage et le décodage.

Cette règle générale peut être représentée visuellement :

bits de données codés		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Position du bit		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Couverture du bit de parité	p1
	p2
	p4
	p8
	p16

Seuls 20 bits codés (5 de parité et 15 de données) sont affichés, mais le motif se poursuit indéfiniment. L'élément clé des codes de Hamming, visible à l'œil nu, est que chaque bit est associé à un ensemble unique de bits de parité. Pour détecter les erreurs, il faut vérifier tous les bits de parité. Le motif d'erreurs, appelé syndrome d'erreur , permet d'identifier le bit erroné. Si tous les bits de parité sont corrects, il n'y a pas d'erreur. Sinon, la somme des bits de parité erronés permet d'identifier le bit erroné. Par exemple, si les bits de parité en positions 1, 2 et 8 indiquent une erreur, alors le bit 1 + 2 + 8 = 11 est erroné. Si un seul bit de parité indique une erreur, c'est ce bit qui est erroné.

Avec $peut être couvert. Après déduction des éléments de parité, Il reste des bits disponibles pour servir de données. Lorsque Bits de parité Bits totaux bits de données Nom Taux 231Hamming(3,1) (Code de triple répétition)1/3 \approx 0,333374 Hamming(7,4) 4/7 \approx 0,57141511Hamming(15,11)11/15 \approx 0,73353126Hamming(31,26)26/31 \approx 0,83966357Hamming(63,57)57/63 \approx 0,9057127120Hamming(127,120)120/127 \approx 0,9458255247Hamming(255,247)247/255 \approx 0,9699511502Hamming(511,502)502/511 \approx 0,982... Hamming$

compromis entre la certitude (la capacité à détecter de manière fiable les erreurs sur trois bits) et la résilience (la capacité à continuer de fonctionner malgré les erreurs sur un seul bit).
Pour k bits de données, un schéma SECDED requiert :
Soit q la première puissance de 2 supérieure à k .
Soit l la partie entière de (log ₂ ( k )) et h l + 1.
Si k ≤ q - l - 1 , les bits supplémentaires requis sont l . Sinon, le nombre requis est h .
Ce code de Hamming étendu était répandu dans les systèmes de mémoire informatique, à commencer par l'IBM 7030 Stretch en 1961 où il est connu sous le nom de SECDED (ou SEC-DED, abréviation de correction d'erreur simple, détection d'erreur double ) . Les formes courantes pour les systèmes de mémoire incluent (39,32) et (72,64). (Bien qu'il soit plus efficace d'utiliser une longueur de mot de code de la forme 2 ^m - 1, la taille des mots de données informatiques actuels, étant des puissances de 2, empêche ce choix, même si les systèmes de communication et de stockage de données en tirent parti.) Les serveurs du XXIe siècle, tout en conservant généralement le niveau de protection SECDED, n'utilisent plus la méthode de Hamming, préférant des conceptions avec des mots de code plus longs (128 à 256 bits de données) et des arbres de contrôle de parité équilibrés modifiés . Le code de Hamming (72,64) reste populaire dans certaines conceptions matérielles, notamment les familles de FPGA Xilinx .

[7,4] Code de Hamming

Représentation graphique des quatre bits de données et des trois bits de parité, et indication des bits de parité correspondant à chaque bit de données.

En 1950, Hamming a introduit le code de Hamming [7,4]. Ce code encode quatre bits de données en sept bits en ajoutant trois bits de parité. Comme expliqué précédemment, il peut détecter et corriger les erreurs sur un seul bit, ou détecter (mais non corriger) les erreurs sur un ou deux bits.

Avec l'ajout d'un bit de parité global, il devient le code de Hamming étendu [8,4] et peut à la fois détecter et corriger les erreurs sur un seul bit et détecter (mais pas corriger) les erreurs sur deux bits.

Construction de G et H

La matrice $est appelée matrice génératrice (canonique) d'uncode linéaire ( n, k ),$

et $est appelée matrice de contrôle de parité .$

Voici la construction de G et H sous forme standard (ou systématique). Quelle que soit leur forme, G et H pour les codes de blocs linéaires doivent satisfaire aux conditions suivantes :

$, une matrice entièrement nulle.$

Puisque [7, 4, 3] = [ n , k , d ] = [2 ^m − 1, 2 ^m − 1 − m , 3]. La matrice de contrôle de parité H d'un code de Hamming est construite en listant toutes les colonnes de longueur m qui sont indépendantes deux à deux.

Ainsi, H est une matrice dont le membre de gauche est constitué de tous les n- uplets non nuls, l'ordre des n- uplets dans les colonnes de la matrice n'ayant pas d'importance. Le membre de droite est simplement la matrice identité ( n − k ) .

Ainsi, G peut être obtenu à partir de H en prenant la transposée du membre de gauche de H avec la matrice identité k - matrice identité du membre de gauche de G.

La matrice du générateur de code $et la matrice de contrôle de parité sont:$

Enfin, ces matrices peuvent être transformées en codes non systématiques équivalents par les opérations suivantes :

Permutations de colonnes (échange de colonnes)
Opérations élémentaires sur les lignes (remplacement d'une ligne par une combinaison linéaire de lignes)

Codage

Exemple

À partir de la matrice ci-dessus, nous avons 2 ^k = 2 ^4 = 16 mots de code. Soit $soit un vecteur ligne de bits de données binaires, Le mot de code pour chacun des 16 vecteurs de données possibles est donné par le produit matriciel standard où l'opération de sommation est effectuée modulo-2.$

Par exemple, prenons $En utilisant la matrice génératrice d'après ce qui précède, nous avons (après application du modulo 2 à la somme),$

[8,4] Code de Hamming avec un bit de parité supplémentaire

Le même exemple [7,4] que précédemment, avec un bit de parité supplémentaire. Ce diagramme ne correspond pas à la matrice H de cet exemple.

Le code de Hamming [7,4] peut facilement être étendu à un code [8,4] en ajoutant un bit de parité supplémentaire au mot codé (7,4) (voir Hamming(7,4) ). Ceci peut être résumé à l'aide des matrices modifiées :

Notez que H n'est pas sous forme standard. Pour obtenir G, on peut utiliser des opérations élémentaires sur les lignes afin d'obtenir une matrice équivalente à H sous forme systématique :

Par exemple, la première ligne de cette matrice est la somme des deuxième et troisième lignes de H sous forme non systématique. En utilisant la construction systématique des codes de Hamming présentée ci-dessus, la matrice A apparaît clairement et la forme systématique de G s'écrit comme suit :

La forme non systématique de G peut être réduite par lignes (en utilisant des opérations élémentaires sur les lignes) pour correspondre à cette matrice.

L'ajout de la quatrième ligne calcule en fait la somme de tous les bits du mot de code (données et parité) comme le quatrième bit de parité.

Par exemple, 1011 est codé (en utilisant la forme non systématique de G au début de cette section) en 01 1 0 011 0, où les chiffres bleus représentent les données ; les chiffres rouges sont les bits de parité du code de Hamming [7,4] ; et le chiffre vert est le bit de parité ajouté par le code [8,4]. Le chiffre vert rend la parité des mots de code [7,4] paire.

Finalement, on peut démontrer que la distance minimale est passée de 3 dans le code [7,4] à 4 dans le code [8,4]. Par conséquent, ce code peut être défini comme le code de Hamming [8,4].

Pour décoder le code de Hamming [8,4], commencez par vérifier le bit de parité. Si ce dernier indique une erreur, la correction d'erreur simple (code de Hamming [7,4]) précisera l'emplacement de l'erreur, tandis que l'absence d'erreur indiquera le bit de parité. Si le bit de parité est correct, la correction d'erreur simple indiquera le résultat du OU exclusif (bit à bit) des deux emplacements d'erreur. Si ces emplacements sont égaux (« absence d'erreur »), alors soit une erreur de double bit ne s'est pas produite, soit elle s'est annulée d'elle-même. Sinon, une erreur de double bit s'est produite.