code de Hamming

Un message binaire voyage comme une rangée de 0 et de 1. Si un seul bit change pendant la transmission ou le stockage, quelques bits de contrôle permettent de retrouver sa position.

Le code de Hamming ajoute ces bits de parité avant l'envoi. Chacun surveille un groupe différent de positions. À l'arrivée, la combinaison des contrôles qui échouent forme une adresse : celle du bit à retourner pour réparer le message.

Un code de Hamming est un code correcteur binaire linéaire. Il transforme des bits d'information en mots de code plus longs en ajoutant des bits de parité. Pour le code Hamming(7,4), quatre bits d'information occupent les positions 3, 5, 6 et 7, tandis que les positions 1, 2 et 4 portent les contrôles de parité. Chaque position est repérée par son numéro écrit en binaire ; chaque contrôle porte sur les positions où l'un des chiffres binaires de ce numéro vaut 1.

La matrice de contrôle est notée H. Un mot de code est noté c et sa transposée c^T. Dans l'arithmétique binaire, où 1 + 1 = 0, la condition de validité s'écrit $H{c}^T=0Hc^T=0$. Pour un mot reçu r, le syndrome s est $s=H{r}^{T}s=Hr^T$. Un syndrome nul indique que les contrôles sont satisfaits ; pour une unique erreur, un syndrome non nul donne exactement le numéro du bit erroné.

La linéarité signifie que la somme binaire de deux mots de code valides reste un mot de code valide. Cette structure facilite l'encodage, l'analyse et la mise en œuvre du code pour la transmission comme pour le stockage.

On encode les quatre bits d'information 1, 0, 1, 1 avec Hamming(7,4), en parité paire. Les bits de contrôle occupent les positions 1, 2 et 4 ; les données occupent 3, 5, 6 et 7.

1. Le contrôle 1 porte sur 1, 3, 5 et 7. Les données y valent 1, 0 et 1 : le bit 1 vaut donc 0 pour conserver un nombre pair de 1.

2. Le contrôle 2 porte sur 2, 3, 6 et 7. Les trois données valent 1 : le bit 2 vaut 1. Le contrôle 4 porte sur 4, 5, 6 et 7 ; le bit 4 vaut 0. Le mot envoyé est 0110011.

3. Pendant la transmission, le bit 6 passe de 1 à 0. Le mot reçu est 0110001. Les contrôles 2 et 4 échouent, tandis que le contrôle 1 reste satisfait.

4. Lus dans l'ordre 4, 2, 1, les résultats forment 110 en binaire, soit 6. Le récepteur retourne le bit 6 et retrouve 0110011.

Le contrôle est refaisable : les groupes 1, 2 et 4 du mot corrigé contiennent respectivement 2, 4 et 2 bits égaux à 1, donc trois parités paires.

Lors d'une transmission binaire, l'émetteur calcule les bits de parité et le récepteur recalcule le syndrome. Hamming convient lorsque l'on veut corriger automatiquement une erreur isolée avec peu de redondance.

Dans une mémoire, les bits de contrôle sont stockés avec les données. À la lecture, une erreur sur un seul bit peut être localisée et corrigée avant que le mot soit remis au programme.

Si deux erreurs simultanées doivent aussi être distinguées d'une erreur simple, on préfère une variante étendue munie d'un bit de parité global. Pour des erreurs groupées ou nombreuses, il faut un code correcteur conçu pour ce modèle de bruit.

Bit de parité simple. Un unique bit de parité signale qu'un nombre impair de bits a changé, mais ne localise pas l'erreur. Dans le mot reçu 0110001, les trois contrôles distincts de Hamming désignent précisément la position 6.

Code de répétition. Répéter chaque bit puis décider à la majorité corrige aussi certaines erreurs, mais en dupliquant davantage l'information. Hamming croise des groupes de parité : la combinaison des échecs fournit directement une position.

Deux bits changent. Le code de Hamming standard est garanti pour une seule erreur. Avec deux erreurs, le syndrome peut imiter la position d'une troisième : corriger aveuglément ce bit produirait alors un mot faux. Il faut signaler l'incertitude ou employer un code étendu adapté.

Syndrome nul. Il signifie seulement que tous les contrôles de parité sont satisfaits. Il ne prouve pas l'absence de toute combinaison d'erreurs : plusieurs bits modifiés peuvent transformer un mot de code valide en un autre.

Convention de parité. L'exemple utilise la parité paire et numérote les positions à partir de 1. Une autre convention change les valeurs intermédiaires ou la présentation, mais l'émetteur et le récepteur doivent appliquer exactement la même règle.

La lecture de la fiche algèbre linéaire éclaire les matrices, la linéarité et les opérations binaires qui structurent les mots de code et leurs syndromes.