Français
Menu

Qu'est-ce que Code de Hamming ?

Le code correcteur d'erreurs le plus connu parmi ceux qui corrigent les erreurs de 1 bit. Avec r bits de contrôle, un mot de code fait 2^r − 1 bits, dont 2^r − 1 − r bits portent des données. Le code de Hamming (7, 4), avec r = 3, ajoute 3 bits de contrôle à 4 bits de données. Chaque bit de contrôle est la parité d'un groupe de bits qui se chevauchent, et le résultat des contrôles refaits à la réception (le syndrome) donne la position du bit erroné en binaire. Sa distance de Hamming minimale vaut 3, et le SECDED, qui ajoute 1 bit de parité globale, peut aussi détecter les erreurs de 2 bits. Il est utilisé par exemple pour l'ECC des mémoires de serveurs.

Nom japonais: ハミング符号

« Code de Hamming » apparaît dans 5 questions d'entraînement réparties sur 2 thèmes, dont Bases de la théorie de l'information et du codage, Circuits logiques.

Domaine: Bases de la théorie de l'information et du codage

Fonctionnement du code (7, 4)

Les positions des bits sont numérotées de 1 à 7, et les positions qui sont des puissances de 2, 1, 2 et 4, sont les bits de contrôle. Le contrôle 1 rend pair le nombre de 1 sur les positions dont le numéro écrit en binaire a un 1 au rang des unités (1, 3, 5, 7), le contrôle 2 sur celles qui ont un 1 au rang des deux (2, 3, 6, 7), et le contrôle 4 sur celles qui ont un 1 au rang des quatre (4, 5, 6, 7). Seuls échouent les contrôles correspondant aux chiffres binaires valant 1 dans le numéro de la position erronée : additionner les poids des contrôles en échec donne donc la position erronée.

Rendement et longueur du code

Avec r bits de contrôle, le mot de code fait 2^r − 1 bits, et plus le code est long, comme (7, 4), (15, 11) et (31, 26), plus le rendement est élevé : 4/7 ≈ 0,57, 11/15 ≈ 0,73 et 26/31 ≈ 0,84. En contrepartie, un mot de code ne peut corriger que 1 bit : plus le mot de code est long, plus il risque de subir une erreur de 2 bits ou plus.

SECDED et mémoires

Ajouter 1 bit de parité globale à un code de Hamming porte la distance de Hamming minimale à 4, ce qui permet la correction d'une erreur simple (SEC) et la détection d'une erreur double (DED). 64 bits de données demandent 8 bits de contrôle, d'où la largeur de 72 bits des mémoires de serveurs. La mémoire flash et les autres dispositifs qui doivent traiter plus d'erreurs utilisent des codes BCH ou des codes LDPC.

S'entraîner : questions sur Code de Hamming

Quelle valeur est la plus proche du rendement du code de Hamming (7, 4), qui ajoute 3 bits de contrôle à 4 bits de données pour former un mot de code de 7 bits ?

  1. AEnviron 0,43
  2. BEnviron 0,57
  3. C1,75
Afficher la réponse et l'explication

Réponse : B. Environ 0,57

Le rendement est k/n, la part de la longueur n du mot de code qu'occupent les k bits de données. Pour le code de Hamming (7, 4), il vaut 4/7 ≈ 0,57 : environ 57 % des bits envoyés sont des données. Un rendement plus faible signifie plus de bits de contrôle et permet plus facilement de résister aux erreurs, mais diminue l'efficacité de l'envoi des données.

Dans un code de Hamming (7, 4), les sept bits sont numérotés de 1 à 7 à partir de la gauche, et les bits 1, 2 et 4 sont les bits de contrôle. Ils sont fixés de sorte que le nombre de 1 soit pair dans les bits 1, 3, 5 et 7 (contrôle 1), dans les bits 2, 3, 6 et 7 (contrôle 2) et dans les bits 4, 5, 6 et 7 (contrôle 4). Si le mot reçu 0110001 contient une erreur sur 1 bit, quel est le bit erroné ?

  1. ALe bit 2
  2. BLe bit 3
  3. CLe bit 6
Afficher la réponse et l'explication

Réponse : C. Le bit 6

Dans le mot reçu 0110001, les bits 1, 3, 5 et 7 valent 0, 1, 0, 1, soit un nombre pair de 1 (le contrôle 1 donne 0) ; les bits 2, 3, 6 et 7 valent 1, 1, 0, 1, soit un nombre impair (le contrôle 2 donne 1) ; et les bits 4, 5, 6 et 7 valent 0, 0, 0, 1, soit un nombre impair (le contrôle 4 donne 1). En lisant les résultats des contrôles 4, 2 et 1 dans cet ordre, 110, comme un nombre binaire, on obtient 6 : c'est donc le bit 6 qui est erroné. En inversant le bit 6, on obtient 0110011, qui satisfait les trois contrôles.

Questions fréquentes

Que se passe-t-il avec un code de Hamming en cas d'erreur sur 2 bits ?

Dans un code de Hamming sans parité globale, une erreur sur 2 bits fait quand même pointer le syndrome vers une position non nulle : un bit correct est alors inversé et l'erreur passe à 3 bits. Pour l'éviter, les mémoires et dispositifs similaires utilisent le SECDED, qui ajoute une parité globale, et signalent une erreur sur 2 bits comme une erreur au lieu de la corriger.

Les codes de Hamming sont-ils encore utilisés aujourd'hui ?

Oui. Ils sont simples et rapides à calculer, et donc très utilisés là où la latence doit rester faible, comme l'ECC des mémoires et la protection des caches et des registres. Là où il faut corriger efficacement beaucoup d'erreurs, comme dans les communications, on utilise des codes plus puissants comme les codes LDPC.

« Code de Hamming » dans les explications

Questions mentionnant « Code de Hamming » (5)

  1. Quelle valeur est la plus proche du rendement du code de Hamming (7, 4), qui ajoute 3 bits de contrôle à 4 bits de données pour former un mot de code de 7 bits ?
  2. Dans un code de Hamming (7, 4), les sept bits sont numérotés de 1 à 7 à partir de la gauche, et les bits 1, 2 et 4 sont les bits de contrôle. Ils sont fixés de sorte que le nombre de 1 soit pair dans les bits 1, 3, 5 et 7 (contrôle 1), dans les bits 2, 3, 6 et 7 (contrôle 2) et dans les bits 4, 5, 6 et 7 (contrôle 4). Si le mot reçu 0110001 contient une erreur sur 1 bit, quel est le bit erroné ?
  3. On ajoute à 32 bits de données un code SECDED, qui corrige les erreurs sur 1 bit et détecte les erreurs sur 2 bits. Le nombre r de bits de contrôle d'un code de Hamming est la plus petite valeur qui satisfait 2^r ≥ nombre de bits de données + r + 1, et le SECDED y ajoute 1 bit de parité globale. Combien de bits de contrôle faut-il ?
  4. Cinq mots de code du code de Hamming (7, 4) sont alignés et envoyés dans l'ordre suivant : le bit 1 de chacun des cinq mots de code, puis le bit 2 de chacun, et ainsi de suite (entrelacement de profondeur 5). Le récepteur rétablit l'ordre d'origine puis corrige une erreur sur 1 bit dans chaque mot de code. Quelle est la longueur maximale d'une erreur en rafale, concentrée sur des bits consécutifs, qui peut toujours être corrigée ?
  5. Pour ajouter un bit de parité paire à la donnée de 7 bits 1011001, quelle est la valeur du bit de parité ?

Termes associés

Bit de parité ECC (code correcteur d'erreurs) Canal binaire symétrique Codage de Huffman Codage par plages (RLE) Code préfixe Compression avec perte Compression sans perte Correction d'erreurs directe (FEC) Distance de Hamming

Retour au glossaire