Parité, codes de Hamming et correction d’erreurs

Les bits ne restent pas toujours en place. Un neutron issu d’un rayon cosmique ou une particule alpha émise par le boîtier même de la puce peut inverser un bit en mémoire ; le bruit électrique corrompt des bits sur un fil ; les cellules de mémoire flash s’usent et fuient. Le remède repose toujours sur la même idée : stocker ou envoyer quelques bits redondants, calculés à partir des données, pour rendre les dégâts visibles. Avec un peu de redondance, on peut détecter les erreurs ; avec davantage, on peut les corriger.

La parité

Le schéma le plus simple ajoute un seul bit de parité à un groupe de bits de données, choisi pour que le nombre total de bits à 1 soit pair (parité paire) ou impair (parité impaire). La lettre C s’écrit 100 0011 en ASCII : trois bits à 1, donc en parité paire son bit de parité vaut 1, ce qui donne 1100 0011. Si un seul bit s’inverse en route, le nombre de 1 devient impair et le récepteur sait que quelque chose ne va pas.

La parité détecte tout nombre impair de bits inversés et rate tout nombre pair : deux inversions s’annulent. Elle ne peut pas non plus dire quel bit s’est inversé : elle détecte, mais ne corrige pas. Le x86 calcule encore un bit de parité sur chaque résultat arithmétique, dans l’indicateur PF, mis à 1 quand l’octet de poids faible du résultat contient un nombre pair de bits à 1. Dans le simulateur, test al, al avec al = 0x41 (deux bits à 1) met PF à 1, et avec 0x43 (trois) le met à 0. C’est un héritage des processeurs 8 bits d’Intel des années 1970.

La distance de Hamming

Pour raisonner sur ce qu’un code sait faire, Richard Hamming a introduit en 1950 une façon de mesurer à quel point deux suites de bits diffèrent. La distance de Hamming entre deux suites de même longueur est le nombre de positions où elles diffèrent : on fait leur XOR et on compte les bits à 1. 1011001 et 1001011 diffèrent en deux positions : leur distance vaut 2.

Un code est l’ensemble des mots de code valides : des bits de données plus des bits de contrôle, calculés selon une règle fixe. La distance d’un code est la plus petite distance entre deux de ses mots de code. Elle détermine tout :

• pour détecter jusqu’à d bits inversés, il faut une distance d’au moins d + 1 : alors d inversions ne peuvent pas transformer un mot de code valide en un autre ;
• pour corriger jusqu’à d bits inversés, il faut une distance d’au moins 2d + 1 : alors un mot de code avec d inversions reste plus proche de l’original que de tout autre mot valide.

Un code de parité a une distance de 2 : chaque inversion isolée produit un mot invalide, il détecte donc une erreur et n’en corrige aucune. Pour corriger les erreurs simples, il faut une distance de 3.

Combien de bits de contrôle ?

Disons que chaque mot a m bits de données et r bits de contrôle, n = m + r au total. Pour corriger toute erreur simple, chaque mot de code valide doit se réserver n + 1 motifs : lui-même et les n mots situés à une inversion de lui. Il y a 2ᵐ mots de code et seulement 2ⁿ motifs, donc (n + 1) × 2ᵐ ≤ 2ⁿ, ce qui se simplifie en m + r + 1 ≤ 2ʳ. Le plus petit r pour les tailles de mot courantes :

Le nombre de bits de contrôle ne croît qu’avec le logarithme de la taille du mot : corriger les erreurs dans de grands mots coûte peu.

Un code de Hamming, pas à pas

Hamming a aussi montré comment atteindre cette borne. On numérote les bits du mot de code à partir de 1. Les positions qui sont des puissances de deux (1, 2, 4, 8…) contiennent des bits de parité ; toutes les autres contiennent des données. Chaque bit de parité couvre les positions dont le numéro, en binaire, a ce bit à 1 :

Avec 7 positions, c’est le code Hamming(7,4) : 4 bits de données aux positions 3, 5, 6 et 7, et 3 bits de parité. Encodons les données 1011 :

position:  1  2  3  4  5  6  7
role:      p1 p2 d1 p4 d2 d3 d4
data:            1     0  1  1
p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0
p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1
p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0
codeword:  0  1  1  0  0  1  1

(⊕ est le XOR : le résultat vaut 1 quand un nombre impair d’entrées vaut 1, ce qui est exactement un calcul de parité.) Supposons maintenant que le bit 5 s’inverse. Le récepteur recalcule chaque contrôle de parité sur les bits qu’il couvre, bit de parité compris. Chaque contrôle en échec apporte son propre numéro de position, et leur somme, le syndrome, est la position du bit fautif :

• le contrôle 1 (positions 1, 3, 5, 7) échoue : +1
• le contrôle 2 (positions 2, 3, 6, 7) passe
• le contrôle 4 (positions 4, 5, 6, 7) échoue : +4

Le syndrome vaut 1 + 4 = 5 : on réinverse le bit 5 et les données sont restaurées. C’est toute l’astuce du placement : chaque position a un numéro binaire unique, et l’ensemble des contrôles qui la couvrent épelle ce numéro. Un syndrome nul signifie qu’il n’y a pas d’erreur. Le programme ci-dessous déroule toute la séquence :

Il affiche le mot de code 0110011, le mot corrompu 0110111, un syndrome de 5, et le mot corrigé 0110011. Changez la position inversée pour n’importe quelle valeur de 1 à 7 et le syndrome suit. Vérifier les 16 mots de code confirme que ce code a une distance de 3.

Une distance de 3 veut aussi dire que deux erreurs le trompent. Inversez plutôt les bits 2 et 6 de 0110011, et le syndrome vaut 4 : le décodeur « corrige » le bit 4, qui était juste, et trois bits sont maintenant faux. La même méthode marche à toutes les tailles : 16 bits de données demandent 5 bits de contrôle, et le principe ne change pas.

SECDED : ce que fait la mémoire ECC

La parade standard au problème des deux erreurs est d’ajouter un bit de plus : un bit de parité global sur tout le mot de code. La distance du code passe à 4, assez pour corriger une erreur et en détecter deux. C’est le SECDED (single error correction, double error detection) :

• syndrome nul, parité globale correcte : pas d’erreur ;
• syndrome non nul, parité globale fausse : une erreur, à la position du syndrome, qu’on corrige ;
• syndrome non nul, parité globale correcte : deux erreurs, qu’on signale, sans toucher aux données.

La mémoire ECC applique le SECDED à chaque mot de 64 bits, avec 8 bits de contrôle : les 7 du tableau ci-dessus, plus le bit de parité global. Un module de mémoire ECC fait donc 72 bits de large au lieu de 64, en général avec une puce mémoire supplémentaire pour huit, soit 12,5 % de mémoire en plus, que le contrôleur mémoire vérifie à chaque lecture. Les erreurs d’un bit sont corrigées en silence et journalisées ; les erreurs de deux bits sont signalées au système d’exploitation, qui arrête en général le programme concerné, ou toute la machine, plutôt que de laisser se propager des données corrompues. Les contrôleurs nettoient aussi la mémoire en tâche de fond (scrubbing), en relisant et corrigeant chaque mot périodiquement pour que les erreurs simples ne s’accumulent pas en erreurs doubles. Les serveurs utilisent presque tous de la mémoire ECC ; la plupart des PC grand public et des téléphones non. Les puces DDR5 ajoutent en interne leur propre ECC sur la puce, mais il corrige les erreurs à l’intérieur de la puce et ne remplace pas l’ECC à l’échelle du module.

Les grands systèmes vont plus loin : le Chipkill d’IBM et les schémas similaires répartissent chaque mot sur plusieurs puces, pour que les données survivent à la panne d’une puce mémoire entière.

Les CRC : attraper les rafales

Le bruit sur un fil ou une rayure sur un disque abîment souvent plusieurs bits voisins d’un coup : c’est une erreur en rafale (burst error). Pour les détecter, l’outil de choix est le contrôle de redondance cyclique (CRC). L’idée : traiter le message comme un immense polynôme binaire, le diviser par un polynôme générateur fixe en utilisant le XOR au lieu de la soustraction, et envoyer le reste avec les données. Le récepteur refait la division ; si le reste diffère, les données ont été abîmées.

Le CRC-32, la variante utilisée par Ethernet, ZIP, gzip et PNG, a un reste de 32 bits. Il s’écrit en quelques lignes en logiciel, un bit à la fois. La constante 0xEDB88320 est le polynôme générateur, écrit avec ses bits inversés :

def crc32(data: bytes) -> int:
    crc = 0xFFFFFFFF
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ 0xEDB88320 if crc & 1 else crc >> 1
    return crc ^ 0xFFFFFFFF

Cette fonction et zlib.crc32 de Python, l’implémentation derrière les vrais fichiers ZIP et PNG, donnent des résultats identiques :

0xCBF43926 est la valeur de contrôle publiée pour cette variante, et changer une seule lettre change toute la somme de contrôle. Un CRC-32 détecte toute rafale d’au plus 32 bits, et des dégâts plus étendus passent inaperçus avec une probabilité d’environ 1 sur 4 milliards. Chaque bloc d’un fichier PNG se termine par le CRC-32 de son contenu ; le vidage hexadécimal PNG du chapitre sur le boutisme se termine par l’un d’eux, ba b3 4b b3. Un CRC ne fait que détecter : Ethernet jette une trame dont le CRC est faux et laisse la reprise aux couches supérieures, par exemple TCP qui retransmet. Et un CRC n’est pas une mesure de sécurité : quiconque modifie les données peut le recalculer. Se protéger contre des modifications délibérées demande un hachage ou une signature cryptographiques.

Où l’on corrige les erreurs

Les codes Reed–Solomon et LDPC sont plus élaborés que les codes de Hamming et corrigent de nombreuses erreurs par bloc, mais ils reposent sur les mêmes idées : la redondance, et une distance entre mots de code valides. Ils ont leur place avec les périphériques qui les utilisent, dans le niveau composants et puces.

À retenir

• Des bits redondants rendent visible une corruption silencieuse : assez pour détecter les erreurs, ou, avec davantage, pour les corriger.
• Un bit de parité détecte tout nombre impair de bits inversés ; l’indicateur PF du x86 calcule la parité d’un octet sur chaque résultat.
• La distance de Hamming d’un code fixe sa puissance : une distance d + 1 détecte d erreurs, 2d + 1 en corrige d.
• Corriger les erreurs simples sur m bits de données demande r bits de contrôle avec m + r + 1 ≤ 2ʳ : 3 pour 4 bits, 7 pour 64.
• Dans un code de Hamming, les bits de parité sont aux puissances de deux, et les contrôles en échec s’additionnent pour donner la position du bit fautif : données 1011 → 0110011 ; inversez le bit 5 et le syndrome vaut 5.
• Le SECDED ajoute un bit de parité global : la mémoire ECC stocke 72 bits par mot de 64 bits, corrige une erreur et en détecte deux.
• Le CRC-32 détecte les erreurs en rafale dans les trames Ethernet et les fichiers ZIP et PNG ; il s’écrit en six lignes et donne les mêmes résultats que zlib.crc32. Les codes Reed–Solomon et LDPC corrigent les erreurs des disques, SSD, CD, QR codes et liaisons radio.