Qu'est-ce que CRC (contrôle de redondance cyclique) ?
Méthode de détection d'erreurs qui traite les bits de données comme un polynôme, y ajoute le reste de sa division par un polynôme générateur et laisse le récepteur refaire le calcul pour détecter les erreurs. Elle est très utilisée dans Ethernet, PCI Express, l'USB et les formats de fichiers.
Nom japonais: CRC(巡回冗長検査)
« CRC (contrôle de redondance cyclique) » apparaît dans 8 questions d'entraînement réparties sur 3 thèmes, dont Bases de la théorie de l'information et du codage, Circuits logiques, Interfaces d'E/S et bus.
Domaine: Interfaces d'E/S et bus
Principe
Un CRC traite les bits de données comme les coefficients d'un polynôme en arithmétique modulo 2 et calcule le reste de sa division par un polynôme générateur. En arithmétique modulo 2, l'addition comme la soustraction sont des XOR, si bien que la division consiste à répéter « si le bit de tête vaut 1, appliquer un XOR avec le générateur puis décaler d'un rang ». Pour un CRC de w bits, le reste de w bits obtenu après avoir ajouté w zéros est envoyé avec les données, et le récepteur refait le calcul pour vérifier qu'il correspond. Les normes réelles ajoutent des conventions comme une valeur initiale, l'inversion de l'ordre des bits de chaque octet et un XOR final.
Erreurs détectées et usages
Un CRC de w bits détecte toute erreur en rafale de longueur inférieure ou égale à w, et la probabilité de laisser passer d'autres erreurs aléatoires est d'environ 2⁻ʷ. Il ne fait cependant que détecter les erreurs sans pouvoir les corriger : les systèmes se rétablissent donc par retransmission. Les CRC sont utilisés dans le FCS d'Ethernet (CRC-32), les paquets PCI Express, l'USB, le bus CAN, les commandes de stockage et des formats de fichiers comme ZIP et PNG ; en matériel, on peut les calculer avec un registre à décalage à rétroaction linéaire composé d'étages à bascule et de portes XOR.
Questions fréquentes
En quoi un CRC diffère-t-il d'une somme de contrôle ?
Une somme de contrôle utilise une opération simple comme l'addition des octets et laisse facilement passer des données permutées ou des erreurs qui se compensent, alors qu'un CRC repose sur la division de polynômes, distingue la position des bits et détecte de façon fiable les erreurs en rafale.
Un CRC peut-il corriger des erreurs ?
En général, non. Un CRC détecte si une erreur s'est produite, mais pas quel bit est erroné : les mémoires qui ont besoin de correction utilisent donc un ECC comme un code de Hamming.