Détecter les erreurs

Le CRC : détecter les rafales d'erreurs

Un détecteur plus robuste

Sur un vrai canal, les erreurs arrivent souvent en rafales : plusieurs bits consécutifs abîmés d'un coup (une rayure sur un disque, une interférence brève). Le bit de parité y est très mauvais. Le CRC (Contrôle de Redondance Cyclique) est un détecteur bien plus puissant, utilisé partout : Ethernet, ZIP, disques durs.

L'idée : une division binaire

Le CRC traite le bloc de données comme un grand nombre binaire et le divise par un nombre fixe convenu, le polynôme générateur. Le reste de cette division est le CRC, ajouté à la fin du message. À la réception, on refait la division : si le reste n'est pas nul, il y a eu une erreur.

Calcul par un registre a decalage (division binaire, XOR) :

donnees ->  [ registre a decalage ]  -> a chaque bit entrant :
              b0  b1  b2  b3            (decalage a gauche, puis XOR avec le
               ^                         polynome generateur si le bit sortant vaut 1)
               |__ rebouclage XOR

apres avoir fait entrer tous les bits, le contenu du registre = le CRC
(a la reception, on rejoue la division : reste non nul -> erreur detectee)

Pourquoi il détecte si bien les rafales

Grâce à ses propriétés algébriques, un CRC bien choisi détecte toutes les rafales d'erreurs plus courtes que sa longueur, et l'immense majorité des rafales plus longues. Un CRC de 32 bits laisse passer une erreur non détectée avec une probabilité de l'ordre de 1 sur 4 milliards : négligeable en pratique.

Détecter, pas corriger

Comme le bit de parité, le CRC détecte sans corriger : quand une erreur est repérée, le protocole demande simplement de retransmettre le bloc. C'est le bon choix quand la retransmission est facile (un réseau), moins bon quand elle est impossible (un signal venu d'une sonde spatiale, où l'on préfère corriger sur place).

Piège classique