FR

Codes de détection et de correction d’erreurs

Parité, code de Hamming, distance de Hamming, sommes de contrôle et CRC

Systèmes de numération : Binaire et hexadécimal Code Gray Codes BCD Virgule flottante et fixe Parité, Hamming et CRC

Bit de parité

Données

Code de Hamming

É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.

Données

parité · données · parité globale · bit inversé.

Distance de Hamming entre deux mots

Mots

Calculateur de CRC et de sommes de contrôle

É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.

Trame

Le CRC pas à pas : la division polynomiale

Division

Pourquoi ils sont nécessaires

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 :

Distance de Hamming

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 :

\[ \text{détecte jusqu’à } d - 1 \text{ erreurs} \qquad \text{corrige jusqu’à } \left\lfloor \frac{d-1}{2} \right\rfloor \text{ erreurs} \]
CodeDistance minimaleDétecteCorrige
Données sans redondance1rienrien
Bit de parité, 2 parmi 521 erreurrien
Hamming32 erreurs1 erreur
Hamming avec parité globale (SECDED)43 erreurs1 erreur et en détecte 2
Répéter chaque bit 3 fois32 erreurs1 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.

Parité

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.

Le code de Hamming

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 :

\[ 2^{r} \ge m + r + 1 \]
Exemple : Hamming (7, 4) avec les données 1011

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.

CodeBits de donnéesBits de paritéRendement
Hamming (7, 4)4357 %
Hamming (15, 11)11473 %
Hamming (31, 26)26584 %
Hamming (63, 57)57690 %
SECDED (72, 64), mémoire ECC64889 %

SECDED : corriger une erreur et en détecter deux

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.

Sommes de contrôle

Elles sont rapides et faciles à programmer, mais détectent bien moins qu’un CRC de même taille.

CRC (contrôle de redondance cyclique)

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.

Exemple : message 11010011101100 avec le générateur 1011 (\(x^3 + x + 1\))

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 :

Pourquoi le même « CRC-16 » donne des nombres différents

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.

Le CRC dans l’industrie

Autres codes correcteurs

Voir aussi : convertisseur binaire et hexadécimal, code 2 parmi 5 et simulateur de portes logiques (le XOR).