Cyclic redundancy check
Un Contrôle de Redondance Cyclique, en Anglais Cyclic Redundancy Check,
est un type de redondance de hachage utilisé pour produire une somme de contrôle (checksum) qui est un petit entier calculé depuis un gros bloc de données (comme du trafic réseau ou un fichier informatique) dans le but de détecter les erreurs de transmission ou de copie.
Les CRCs sont calculés avant et après la transmission ou duplication, puis comparés pour s'assurer que ce sont les mêmes. Les calculs de CRC les plus utilisés sont bâtis de manière à ce que les erreurs de certains types, comme celles dues aux interférences dans les transmissions, soient toujours détectées.
Introduction
L'opération mathématique essentielle dans le calcul d'un CRC est une division modulo 2, et le reste de cette division représente le CRC. Les CRCs sont souvent désignés sous le nom de checksums (sommes de contrôle), mais une telle désignation n'est pas correcte car, d'un point de vue technique, une somme de contrôle est calculée avec des additions et non des divisions. La partie principale de l'algorithme est la suivante :
function crc(bit array bitString[1..len], int polynomial) {
shiftRegister := initial value // commonly all 0 bits or all 1 bits
for i from 1 to len {
if most significant bit of shiftRegister xor bitString[i] = 1
shiftregister := (shiftregister left shift 1) xor polynomial
else
shiftRegister := shiftregister left shift 1
}
return shiftregister
}