AlgèbreNotion · Glossaire
code CRC
Un CRC (contrôle de redondance cyclique) est une valeur de contrôle destinée à détecter des erreurs dans un bloc de données. Le bloc est assimilé à un polynôme sur un corps fini puis divisé par un polynôme générateur prédéfini ; le reste est ajouté au message. Le destinataire le recalcule sur les données reçues : une discordance signale une altération.
Sommaire
Ce que vous allez apprendre
- Identifier le rôle d'un CRC dans une transmission ou une copie.
- Refaire un calcul binaire complet avec le générateur 1011.
- Interpréter correctement un reste nul sans lui attribuer une garantie absolue.
- Distinguer un CRC d'une somme de contrôle, d'un code correcteur et d'un hachage cryptographique.
En clair
Imaginez que vous envoyiez la suite de bits 1101. Avant l'envoi, un calcul convenu produit trois bits supplémentaires, ici 001. Le message devient 1101001. Ces bits jouent le rôle d'une empreinte courte : le destinataire refait le même calcul et compare le résultat.
Si un bit a changé pendant la transmission, le contrôle donne généralement un autre reste. Le CRC signale alors que les données sont suspectes. Il ne localise pas forcément l'erreur et ne répare pas le message.
Définition
Un code CRC, ou contrôle de redondance cyclique, est une valeur de détection d'erreurs calculée sur une suite de bits. Les bits sont interprétés comme les coefficients d'un polynôme à coefficients dans le corps à deux éléments. Dans cette arithmétique, l'addition et la soustraction correspondent toutes deux au ou exclusif, noté XOR, sans retenue.
Le polynôme du message est noté . Le polynôme générateur convenu est noté , et son degré est noté . On ajoute d'abord r zéros au message, ce qui revient à multiplier son polynôme par . Le reste de la division par le générateur fournit au plus r bits de contrôle :
Le mot transmis correspond à . Il est divisible par , car additionner et soustraire sont la même opération dans ce corps. Le récepteur divise le mot reçu par le même générateur. Un reste non nul prouve qu'une discordance est survenue. Un reste nul signifie seulement qu'aucune erreur détectable par ce générateur n'a été observée.
Un exemple, pas à pas
Calculons le CRC du message 1101 avec le générateur 1011. Ce générateur est de degré 3, donc le reste comportera trois bits.
Données :
message : 1101 ;
générateur : 1011 ;
nombre de zéros ajoutés : 3 ;
suite à diviser : 1101000.
message : 1101 ;
générateur : 1011 ;
nombre de zéros ajoutés : 3 ;
suite à diviser : 1101000.
1. Sur les quatre premiers bits, le XOR donne 1101 ⊕ 1011 = 0110. On retire le zéro de tête et l'on abaisse le bit suivant : 1100.
2. Le calcul donne 1100 ⊕ 1011 = 0111. En abaissant le bit suivant, on obtient 1110.
3. Puis 1110 ⊕ 1011 = 0101. Le dernier bit abaissé donne 1010.
4. Enfin, 1010 ⊕ 1011 = 0001. Les trois derniers bits forment le reste 001.
2. Le calcul donne 1100 ⊕ 1011 = 0111. En abaissant le bit suivant, on obtient 1110.
3. Puis 1110 ⊕ 1011 = 0101. Le dernier bit abaissé donne 1010.
4. Enfin, 1010 ⊕ 1011 = 0001. Les trois derniers bits forment le reste 001.
Le CRC vaut donc 001 et le mot transmis est 1101001. Le schéma synthétise l'ajout du reste et le contrôle effectué à la réception.
Pour refaire le contrôle, on divise 1101001 par 1011 avec les mêmes XOR successifs. Le reste obtenu est 000 : le mot construit respecte bien la règle du générateur.
En pratique
Dans une liaison numérique, l'émetteur joint un CRC à chaque trame. Le récepteur rejette ou redemande une trame lorsque le reste calculé n'est pas celui attendu. Si la liaison doit aussi corriger des bits sans retransmission, un code correcteur est préférable.
Lors d'une copie ou d'une sauvegarde, un CRC calculé avant et après l'opération aide à repérer une altération accidentelle. Pour résister à une modification volontaire, on choisit plutôt une fonction de hachage cryptographique assortie d'un mécanisme d'authentification.
Dans un protocole ou un format de fichier, le nom du CRC ne suffit pas toujours. Il faut appliquer exactement le polynôme, la taille et les conventions de calcul prescrits ; sinon deux logiciels peuvent produire des valeurs différentes pour les mêmes octets.
À ne pas confondre
Somme de contrôle. Elle additionne des valeurs selon une règle numérique, tandis qu'un CRC effectue une division polynomiale sur les bits. Un échange de bits peut laisser une somme simple inchangée alors que le CRC choisi le signale.
Code correcteur d'erreurs. Un CRC produit surtout un verdict de cohérence. Si le système retrouve automatiquement la position d'un bit erroné et le corrige, il emploie une redondance correctrice, pas le CRC seul.
Hachage cryptographique. Un CRC vise les altérations accidentelles et reste linéaire. Si un adversaire ne doit pas pouvoir fabriquer un autre contenu accepté, il faut un hachage cryptographique et, selon le besoin, une authentification.
Limites et pièges
Reste nul, données pas nécessairement intactes. Un CRC de r bits ne possède que 2r valeurs possibles. Des messages différents ont donc forcément parfois le même CRC. Il faut lire un accord comme « aucune erreur détectée », jamais comme une preuve d'identité absolue.
Mauvais jeu de paramètres. Le polynôme ne décrit pas toujours à lui seul une variante de CRC. L'ordre de lecture des bits, la valeur initiale et une éventuelle transformation finale peuvent intervenir. Une divergence systématique sur un message test connu indique qu'il faut comparer tous les paramètres.
Capacité liée au générateur. Deux polynômes de même degré ne détectent pas exactement les mêmes motifs d'erreur. Il faut employer le générateur imposé par le protocole et évaluer ses garanties pour la longueur réelle des messages.
Altération volontaire. La structure algébrique d'un CRC permet de construire des modifications qui conservent le contrôle. Lorsqu'une falsification est possible, il faut ajouter une authentification cryptographique plutôt qu'allonger seulement le CRC.
Pour aller plus loin
La Division euclidienne éclaire le principe quotient-reste qui se transpose ici aux polynômes binaires et produit les bits de contrôle.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres