Contrôle de redondance cyclique

Le CRC d'une trame (chaîne de donnée délimitée) est évalué (échantillonné puis calculé) avant la transmission ou le transfert et inscrit sur quelques bits à la fin de la trame. Après transmission, il est recalculé et comparé au chiffre de fin de trame pour s’assurer que les données sont probablement identiques (probablement seulement car toutes les erreurs ne peuvent être détectées, c'est une détection statistique). Une différence conduit à une retransmission, parfois un code erreur.

Les calculs de CRC les plus utilisés sont conçus afin de pouvoir toujours détecter les erreurs de certains types, comme celles dues par exemple, aux interférences lors de la transmission.

On trouve des fonctions CRC dans différents logiciels comme ceux dédiés à la sauvegarde, à la capture de données (échantillonnage) ainsi que dans les appareils et dispositifs de transmission de signaux numériques : DVB, MPEG-2 TS, DAB, etc.

Le plus simple et largement répandu dans le transfert ordinateur /machine (commande numérique par exemple) est le CRC1, le bit de parité.

L’opération mathématique essentielle dans le calcul d’un CRC est une division modulo 2 dont le reste représente le CRC. Les CRC sont souvent appelés abusivement checksums (sommes de contrôle), mais les sommes de contrôle proprement dites sont le résultat d'une addition. La partie principale de l’algorithme est la suivante :

fonction crc(tableau de bits bitString[1..longueur], entier polynome)
{
    shiftRegister := valeur_initiale  // Généralement tous les bits à 0 ou 1
    pour i de 1 à longueur
    {
        si bit de poids fort de shiftRegister xor bitString[i] vaut 1
        {
            // décaler d'1 bit vers la gauche équivaut à multiplier par 2
            shiftRegister := (shiftRegister décalé d'1 bit vers la gauche) xor polynome
        }
        sinon
        {
            shiftRegister := (shiftRegister décalé d'1 bit vers la gauche)
        }
    }
    retourne shiftRegister
}

• (en) Implémentation de CRC-32 en JavaScript

Les checksums (sommes de contrôle) sont un mode de contrôle fonctionnant aussi par hachage, plus élaboré, portant sur des fichiers plus importants (transfert de fichier, image disque etc.) très visibles dans le monde Linux.

Lors du téléchargement d'une distribution Linux, le MD5sum est disponible au téléchargement à côté de l'image disque. On télécharge les deux, puis un logiciel sur le pc recalcule le MD5sum pour le comparer à l'original pour valider l'intégrité du fichier téléchargé.

• Arvind M. Patel, A Multi-Channel CRC Register, AFIPS'71 (printemps) Proceedings, mai 1971 DOI:10.1145/1478786.1478789
• P. E. Boudreau, R. F. Steen, Cyclic Redundancy Checking by Program, AFIPS'71 (automne) Proceedings, novembre 1971 DOI:10.1145/1479064.1479067
• John R. Hill, A Table Driven Approach to Cyclic Redundancy Check Calculations, ACM SIGCOMM Computer Communication Review, Volume 9 Numéro 2, avril 1979 DOI:10.1145/1015860.1015862
• Georgia Griffiths, G. Carlyle Stones, The Tea-Leaf Reader Algorithm: An Efficient Implementation of CRC-16 and CRC-32, Communications of the ACM, Volume 30 Numéro 7, juillet 1987 DOI:10.1145/28569.28572
• Dilip V. Sarwate, Computation of Cyclic Redundancy Checks via Table Look-Up, Communications of the ACM, Volume 31 Numéro 8, août 1988 DOI:10.1145/63030.63037
• Guido Duerinckx, Cyclic Redundancy Checks in Ada95, ACM SIGAda Letters, Volume XVII Issue 1, janvier/février 1997 DOI:10.1145/249984.249994

• (en) Calcul de CRC-32 en ligne, à partir de texte ou d'un fichier, avec polynôme standard ou personnalisé, et le code source JavaScript correspondant
• (en) A Painless Guide to CRC Error Detection Algorithms
• (en) The Great CRC Mystery - Terry Ritter
• Tutoriel sur le calcul des CRC - DVSoft
• Calcul du CRC 16

• Portail de l’informatique
• Portail des mathématiques
• Portail des télécommunications