Parité, code de Hamming, distance de Hamming, sommes de contrôle et CRC
Écrivez les bits de données et les bits de parité sont calculés. Ensuite, cliquez sur n’importe quel bit du mot pour l’inverser comme s’il s’agissait d’une erreur de transmission, et voyez ce que fait le récepteur : le syndrome indique la position du bit erroné. Essayez avec une et deux erreurs, avec et sans le bit de parité globale.
parité · données · parité globale · bit inversé.
Écrivez la trame en octets hexadécimaux (avec ou sans espaces) ou en texte. La colonne « dans la trame » donne les octets dans l’ordre où ils sont envoyés.
Aucun canal n’est parfait : une trame RS-485 qui passe près d’un variateur, un bit de mémoire touché par une particule ou une rayure sur un disque peuvent changer un 0 en 1. Pour s’en rendre compte, l’émetteur ajoute aux données des bits de redondance calculés à partir d’elles, et le récepteur refait le calcul. Si cela ne correspond pas, il y a deux stratégies :
La distance de Hamming entre deux mots de même taille est le nombre de bits qui diffèrent : entre 1011101 et 1001001, il y en a 2. La distance minimale \(d\) d’un code est la plus petite entre deux mots valides quelconques, et elle fixe ce qu’il peut faire :
| Code | Distance minimale | Détecte | Corrige |
|---|---|---|---|
| Données sans redondance | 1 | rien | rien |
| Bit de parité, 2 parmi 5 | 2 | 1 erreur | rien |
| Hamming | 3 | 2 erreurs | 1 erreur |
| Hamming avec parité globale (SECDED) | 4 | 3 erreurs | 1 erreur et en détecte 2 |
| Répéter chaque bit 3 fois | 3 | 2 erreurs | 1 erreur (à la majorité) |
L’idée est géométrique : si les mots valides sont au moins à distance 3, un mot avec une erreur reste plus près de l’original que de n’importe quel autre.
C’est le code le plus simple : on ajoute un bit pour que le nombre total de uns soit pair (parité paire) ou impair (parité impaire). Il détecte tout nombre impair d’erreurs, mais pas deux bits inversés en même temps. C’est la parité des ports série (8E1 signifie 8 bits de données, parité paire et 1 bit de stop ; Modbus RTU utilise la parité paire par défaut) et de certaines mémoires anciennes. Dans un circuit, on la calcule avec une chaîne de portes XOR.
Avec la parité bidimensionnelle, les données sont rangées dans un tableau et on ajoute la parité de chaque ligne et de chaque colonne. Une erreur change la parité d’une ligne et d’une colonne, et leur croisement indique le bit à corriger.
Richard Hamming l’a imaginé en 1950, lassé de voir les pannes des machines à relais gâcher ses calculs du week-end. Les positions du mot sont numérotées à partir de 1 ; celles qui sont des puissances de 2 (1, 2, 4, 8…) portent des bits de parité et les autres les données. Chaque bit de parité \(p_k\) couvre les positions dont le numéro en binaire a à 1 le bit de poids \(k\) : \(p_1\) couvre 1, 3, 5, 7… ; \(p_2\) couvre 2, 3, 6, 7… ; \(p_4\) couvre 4–7, 12–15… Avec \(r\) bits de parité, on protège \(m\) bits de données si :
Les données vont aux positions 3, 5, 6 et 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) et \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). Le mot envoyé est \(0110011\). Si \(0110111\) arrive (la position 5 est fausse), le récepteur recalcule les trois parités sur ce qu’il a reçu : \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). Le syndrome \(s_4 s_2 s_1 = 101_2 = 5\) est exactement la position de l’erreur, et il suffit d’inverser ce bit.
| Code | Bits de données | Bits de parité | Rendement |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), mémoire ECC | 64 | 8 | 89 % |
Avec deux erreurs, le Hamming simple donne un syndrome non nul et « corrige » un bit qui était juste, ce qui aggrave le mot. Pour l’éviter, on ajoute un bit de parité globale P sur tout le mot (single error correction, double error detection) :
C’est le schéma de la mémoire ECC des serveurs et de nombreux microcontrôleurs pour l’automobile et la sécurité : 8 bits de contrôle pour 64 bits de données.
Elles sont rapides et faciles à programmer, mais détectent bien moins qu’un CRC de même taille.
Le CRC traite le message comme un polynôme à coefficients 0 et 1 (\(1011 = x^3 + x + 1\)) et le divise par un polynôme générateur de degré \(r\). Dans cette arithmétique (modulo 2), additionner et soustraire reviennent au OU exclusif et il n’y a pas de retenues. L’émetteur ajoute \(r\) zéros au message, divise et envoie le reste à leur place ; le récepteur divise la trame entière et, s’il n’y a pas d’erreur, le reste vaut 0.
On ajoute 3 zéros et on divise en soustrayant (XOR) le générateur sous chaque 1 restant à gauche. Le reste est 100, on envoie donc 11010011101100100. C’est l’exemple chargé dans le calculateur ci-dessus.
Avec un bon polynôme de degré \(r\), le CRC détecte :
En plus du polynôme, chaque CRC définit la valeur initiale du registre, si les bits de chaque octet entrent réfléchis (en commençant par le bit de poids faible, comme ils sortent d’une UART), si le résultat est réfléchi et avec quelle valeur se fait le OU exclusif final. C’est pourquoi CRC-16/MODBUS, CRC-16/ARC et CRC-16/CCITT donnent des résultats différents avec les mêmes données. Pour savoir lequel utilise un appareil, on calcule celui de la chaîne de texte 123456789 et on le compare à sa valeur de contrôle : 4B37 pour Modbus, 29B1 pour CCITT-FALSE, CBF43926 pour CRC-32.
Voir aussi : convertisseur binaire et hexadécimal, code 2 parmi 5 et simulateur de portes logiques (le XOR).