La détection et la correction des erreurs
Partie 2 sur 2
4Le contrôle de redondance cyclique (CRC)
Le contrôle de redondance cyclique, noté CRC (Cyclic Redundancy Check), est un contrôle d’intégrité à la fois puissant et facile à mettre en œuvre. On le qualifie, à juste titre, de principale méthode de détection d’erreurs des télécommunications. C’est la somme de contrôle de l’Ethernet, du Wi-Fi, des archives ZIP, des images PNG et de nombreux disques.
4.1Le principe
Le CRC protège des blocs de données appelés trames (frames en anglais : un bloc de données avec son début et sa fin). À chaque trame, on associe un code de contrôle, parfois appelé lui-même « CRC » par abus de langage, ou FCS (Frame Check Sequence, « séquence de contrôle de la trame ») lorsqu’il fait 32 bits.
Une précision importante. On lit parfois que le code CRC permet « de détecter les erreurs, mais aussi de les réparer ». C’est inexact dans l’usage courant : un CRC détecte, il ne répare pas. Quand le contrôle échoue, on jette la trame ou on la redemande. La réparation relève des codes de la partie 5.
4.2Les polynômes : une façon de voir les bits
Le CRC traite une suite de bits comme un polynôme, dont chaque bit est un coefficient. Le bit le plus à droite est le coefficient de X0 (qui vaut 1), celui d’à côté le coefficient de X1, puis X2, etc. Exemple : la suite 0110101001 s’écrit X8 + X7 + X5 + X3 + 1. Une suite de n bits donne un polynôme de degré n − 1 au plus. Tous les calculs se font « modulo 2 », c’est-à-dire sans retenue : 1 + 1 donne 0. Additionner, c’est simplement faire un OU exclusif (le résultat est 1 si les deux bits diffèrent, 0 sinon).
Ne vous laissez pas impressionner par le mot « polynôme » : il s’agit surtout d’un moyen de dire « divisez cette suite de bits par cette autre suite, sans retenue ». Un polynôme prédéfini, connu de l’émetteur et du récepteur, sert de diviseur : c’est le polynôme générateur, noté G(X).
4.3Le calcul, en cinq gestes
- L’émetteur et le récepteur ont convenu d’un diviseur G, de degré d (ici G = 1011, soit X3 + X + 1, de degré 3).
- L’émetteur ajoute d zéros à la fin du message M. Ici, trois zéros.
- Il divise ce nombre par G, sans retenue, et ne garde que le reste, qui tient sur d bits.
- Il colle ce reste à la fin du message d’origine, à la place des zéros, et envoie le tout.
- Le récepteur divise ce qu’il reçoit par G. Si le reste est nul, aucune erreur n’a été détectée.
Avec le message 11010011101100 et G = 1011, le reste vaut 100 : la trame envoyée est 11010011101100100, et sa division par 1011 donne bien 000. Si le sixième bit est changé pendant le voyage, le reste devient 110 : l’erreur est détectée.
4.4L’exemple, corrigé
Prenons le message 1011 0001 0010 1010 (B12A en hexadécimal, voir l’hexadécimal) et G(X) = X3 + 1, c’est-à-dire 1001. On lit parfois que, G étant de degré 3, il faut « ajouter 4 bits nuls » et que l’on obtient un CRC de 4 bits, 0011. C’est une erreur : un diviseur de degré 3 laisse un reste de 3 bits, donc on ajoute trois zéros (un diviseur de n bits, ici 4, donne un reste de n − 1 bits). Le bon calcul donne le CRC 001 et la trame 1011000100101010001, dont la division par 1001 donne un reste nul. On trouve aussi le message « noté B1 » en hexadécimal : le message complet de 16 bits vaut B12A.
4.5Les polynômes en usage
Le choix du polynôme décide de ce que le CRC détecte. Plus il est long, plus il attrape d’erreurs. Un CRC de n bits repère en particulier toutes les rafales d’erreurs (suites de bits consécutifs abîmés) d’au plus n bits. En voici plusieurs :
- CRC-12 : X12 + X11 + X3 + X2 + X + 1.
- CRC-16 : X16 + X15 + X2 + 1.
- CRC-CCITT (recommandation V.41 de l’organisme international de normalisation des télécommunications) : X16 + X12 + X5 + 1, notamment utilisé dans le protocole de liaison HDLC (un protocole qui découpe les données en trames sur une liaison point à point).
- CRC-32, celui de l’Ethernet : X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1.
- CRC « ARPA » (24 bits) : X24 + X23 + X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1.
Il n’est pas utile de les retenir : retenez que chaque protocole a choisi le sien, et qu’un contrôle ne marche que si l’émetteur et le récepteur utilisent le même.
Pour s’exercer
Exercice 2 : vérifier un CRC
Avec G = 1001, la trame envoyée est 1011000100101010001. Le récepteur reçoit 1011010100101010001 (le sixième bit a changé). Peut-il s’en apercevoir sans connaître le message d’origine ?
Voir la réponse
Oui. Il divise la trame reçue par 1001, sans retenue. Pour la trame d’origine, le reste est 000. Pour la trame reçue, le reste vaut 010, donc non nul : l’erreur est détectée. Il n’a pas besoin de connaître le message d’origine, seulement le diviseur convenu. En revanche, ce reste ne lui dit pas directement quel bit est faux : il doit redemander la trame.
5Les codes qui corrigent
Détecter ne suffit pas toujours. Une sonde spatiale à des millions de kilomètres ne peut pas « redemander » une image, et un disque rayé ne peut pas renvoyer une seconde fois le morceau de musique. Il faut des codes qui ajoutent assez de redondance pour retrouver l’original.
5.1Le code de Hamming : corriger un bit
Le code de Hamming (du nom de Richard Hamming, chercheur américain qui l’a inventé dans les années 1940 après avoir vu ses calculs perdus par des erreurs de machine) place des bits de parité à des endroits choisis, de sorte que chacun contrôle un sous-groupe différent de bits. Quand une erreur survient, l’ensemble des parités qui échouent forme un nombre, appelé syndrome, qui donne directement la position du bit faux.
Dans la version la plus simple, 4 bits de données sont protégés par 3 bits de contrôle, soit 7 bits au total. Pour les données 1011, le mot de code est 0110011. Si le cinquième bit est changé, deux des trois contrôles échouent (le premier et le troisième), ce qui s’écrit 101, c’est-à-dire 5 en binaire : on sait que c’est le cinquième bit qu’il faut remettre. Une version étendue repère en plus deux erreurs, sans les corriger.
5.2Reed-Solomon : corriger des paquets
Pour des erreurs groupées (une rayure efface plusieurs octets de suite), on utilise des codes qui travaillent sur des blocs d’octets plutôt que sur des bits isolés. Le plus célèbre est le code de Reed-Solomon, du nom de ses deux inventeurs (1960). Vous l’utilisez sans le savoir : il corrige les rayures des disques optiques (voir les disques optiques pour la lecture d’un disque), les codes carrés (QR codes), certaines transmissions par satellite et les données de nombreux supports.
5.3Dans la mémoire et le stockage
- La mémoire à correction d’erreurs (ECC, pour Error-Correcting Code) des serveurs corrige un bit faux par mot et en détecte deux (voir la mémoire vive).
- Les disques SSD (sans pièce mobile, à mémoire flash) et les disques durs corrigent en permanence des erreurs de lecture avec des codes performants, sans que l’on s’en aperçoive.
- Le RAID (regroupement de plusieurs disques en un seul ensemble) reconstruit un disque entier perdu grâce à un disque de parité, c’est la même idée de parité à l’échelle des disques (voir le RAID).
Pour s’exercer
Exercice 3 : détecter ou corriger ?
Pour chaque cas, dites s’il suffit de détecter l’erreur ou s’il faut pouvoir la corriger : (a) un téléchargement de fichier par le web ; (b) la lecture d’un disque optique rayé ; (c) une image envoyée par une sonde lointaine ; (d) une trame sur un réseau local.
Voir la réponse
(a) Détecter suffit : on peut redemander la partie du fichier. (b) Il faut corriger : le disque ne peut pas « renvoyer » les données ; c’est le rôle du code de Reed-Solomon. (c) Il faut corriger : l’émission prend trop de temps, et la redemande n’est pas toujours possible. (d) Détecter suffit : une trame fautive est jetée et le protocole des couches supérieures la redemande.
6Usages et limites
6.1Où retrouvez-vous ces contrôles ?
- Une trame Ethernet (le réseau filaire local le plus courant) se termine par un CRC de 32 bits. Une carte réseau qui le trouve faux jette la trame (voir Ethernet).
- TCP et IP ajoutent leurs propres sommes de contrôle, plus simples, sur les en-têtes et les données (voir TCP).
- Les archives compressées (ZIP, RAR) stockent le CRC de chaque fichier pour vérifier l’extraction (voir la compression).
- Les codes-barres et numéros de cartes bancaires comportent une clé de contrôle : le dernier chiffre se calcule à partir des autres.
6.2« Erreur de CRC » : que veut dire ce message ?
Les forums regorgent de questions du type « erreur de CRC sur mon fichier téléchargé », « erreur de CRC sur mon disque dur », « erreur de CRC pendant l’installation ». Dans tous les cas, le message signifie la même chose : le CRC recalculé ne correspond pas au CRC attendu, donc les données ne sont pas celles d’origine. Les causes possibles sont un téléchargement interrompu ou incomplet, un support abîmé (disque optique rayé, disque dur en fin de vie), une mémoire défectueuse, ou un fichier modifié. La démarche est toujours la même : refaire le téléchargement, vérifier le support, essayer sur une autre machine. Si le même fichier est fautif plusieurs fois de suite, le support est en cause.
6.3Les limites à connaître
- Aucun contrôle ne détecte toutes les erreurs : avec un CRC de 32 bits, une altération au hasard passe inaperçue une fois sur environ quatre milliards, mais elle peut passer.
- Plus la redondance est grande, plus l’on détecte et corrige, mais plus on envoie de données inutiles : c’est un compromis.
- Ces contrôles protègent contre le hasard (bruit, usure). Ils ne protègent pas contre une personne qui modifie volontairement les données, comme on le voit dans le « coin cyber ».