Calcul de CRC (Cyclic Redundancy Check)

Principe général

Définition

Le CRC est un code détecteur d'erreurs basé sur l'arithmétique polynomiale en corps de Galois GF(2).

Principe

Les données sont considérées comme un polynôme
Division polynomiale par un polynôme générateur
Le reste de la division = CRC

Propriétés

Détection d'erreurs en rafale
Détection de toutes les erreurs impaires (si polynôme contient facteur \((x+1)\))
Détection de toutes les erreurs doubles
Probabilité de non-détection : \(2^{-n}\) pour CRC de n bits

Arithmétique en GF(2)

Règles de base

Addition : XOR (pas de retenue)
Soustraction : XOR (identique à l'addition)
Multiplication : ET logique

Table d'opérations

+	0	1
0	0	1
1	1	0

×	0	1
0	0	0
1	0	1

Exemples

\(1 + 1 = 0\) (pas de retenue)
\(1011 + 1101 = 0110\) (XOR bit à bit)
\(1011 - 1101 = 0110\) (identique à l'addition)

Représentation polynomiale

Conversion binaire → polynôme

Exemple : \(1101_2\)

\(1 \cdot x^3 + 1 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0 = x^3 + x^2 + 1\)

Polynômes générateurs courants

Nom	Bits	Polynôme	Expression
CRC-8	8	0x07	\(x^8 + x^2 + x + 1\)
CRC-16-CCITT	16	0x1021	\(x^{16} + x^{12} + x^5 + 1\)
CRC-16-IBM	16	0x8005	\(x^{16} + x^{15} + x^2 + 1\)
CRC-32	32	0x04C11DB7	\(x^{32} + x^{26} + x^{23} + ... + 1\)
CRC-CAN	15	0xC599	\(x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1\)

Méthode de calcul

Algorithme général

Ajouter n zéros aux données (n = degré du polynôme générateur)
Diviser les données étendues par le polynôme générateur
Le reste de la division = CRC
Remplacer les n zéros par le CRC

Division polynomiale en GF(2)

Règles : * Pas de soustraction, uniquement XOR * Si le bit de poids fort = 1 → XOR avec le diviseur * Si le bit de poids fort = 0 → décalage sans XOR

Exemple détaillé : CRC-3

Données et polynôme

Message : \(1101\) (4 bits) Polynôme générateur : \(G(x) = x^3 + x + 1 = 1011_2\) (degré 3)

Étape 1 : Ajout de zéros

Message étendu : \(1101\,000\) (ajout de 3 zéros)

Étape 2 : Division

         1100  ← Quotient (non utilisé)
       ________
1011 | 1101000
       1011     ← XOR car bit de poids fort = 1
       ----
        110000
        1011   ← XOR car bit de poids fort = 1
        ----
         11100
         1011  ← XOR car bit de poids fort = 1
         ----
          1110
          1011 ← XOR car bit de poids fort = 1
          ----
           101 ← Reste = CRC

Étape 3 : Résultat

CRC : \(101_2\) Message transmis : \(1101\,101\) (message original + CRC)

Vérification

À la réception, on divise \(1101101\) par \(1011\) :

         1111
       ________
1011 | 1101101
       1011
       ----
        110101
        1011
        ----
         11001
         1011
         ----
          10111
          1011
          ----
           1001
           1011
           ----
            010 ← Reste ≠ 0 → ERREUR!

Si pas d'erreur : Reste = \(000\)

Exemple détaillé : CRC-8

Données et polynôme

Message : \(11010011\) (8 bits = 0xD3) Polynôme : CRC-8 = \(x^8 + x^2 + x + 1 = 1\,0000\,0111_2\) (0x107)

Calcul

Message étendu : \(11010011\,00000000\) (ajout de 8 zéros)

                 10110110  ← Quotient
              _______________
100000111 | 1101001100000000
            100000111         ← XOR
            ---------
             001001011
              100000111       ← XOR (décalage)
              ---------
               101001100
               100000111      ← XOR
               ---------
                 1001011000
                 100000111    ← XOR (décalage)
                 ---------
                   01011110
                    100000111 ← XOR (décalage)
                    ---------
                     10111010
                     100000111 ← XOR
                     ---------
                       0111101 ← Reste = CRC

CRC : \(01111101_2 = 0x7D\)

Message transmis

\(11010011\,01111101\) = 0xD37D

Calcul pratique (méthode bit par bit)

Algorithme

def crc_calcul(data, poly, n_bits):
    # Ajouter n_bits zéros
    crc = data << n_bits

    # Masque pour le bit de poids fort
    msb_mask = 1 << (n_bits + len(bin(data)) - 3)

    # Division
    for i in range(len(bin(data)) - 2):
        if crc & msb_mask:  # Si bit de poids fort = 1
            crc ^= poly << (len(bin(data)) - 3 - i)

    # Extraire les n_bits de poids faible
    return crc & ((1 << n_bits) - 1)

Exemple Python : CRC-8

def crc8(data):
    poly = 0x07  # x^8 + x^2 + x + 1
    crc = data << 8  # Ajouter 8 zéros

    for i in range(8):  # 8 bits de données
        if crc & 0x8000:  # Bit de poids fort
            crc ^= (poly << 7)
        crc <<= 1

    return (crc >> 8) & 0xFF

# Test
message = 0xD3
crc = crc8(message)
print(f"CRC-8 de 0x{message:02X} = 0x{crc:02X}")

Calcul par table (méthode rapide)

Principe

Précalculer le CRC de toutes les valeurs possibles (0-255 pour CRC-8)
Utiliser une table de lookup
Beaucoup plus rapide pour traiter de grandes quantités de données

Algorithme

def generer_table_crc8(poly):
    table = []
    for i in range(256):
        crc = i
        for j in range(8):
            if crc & 0x80:
                crc = (crc << 1) ^ poly
            else:
                crc <<= 1
            crc &= 0xFF
        table.append(crc)
    return table

def crc8_table(data, table):
    crc = 0
    for byte in data:
        crc = table[crc ^ byte]
    return crc

# Génération de la table
table_crc8 = generer_table_crc8(0x07)

# Calcul
message = [0xD3, 0x45, 0x12]
crc = crc8_table(message, table_crc8)

CRC-16 CCITT (exemple protocole série)

Paramètres

Polynôme : 0x1021 (\(x^{16} + x^{12} + x^5 + 1\))
Valeur initiale : 0xFFFF
XOR final : 0x0000
Réflexion : Non

Algorithme

def crc16_ccitt(data):
    crc = 0xFFFF  # Valeur initiale
    poly = 0x1021

    for byte in data:
        crc ^= (byte << 8)  # XOR avec l'octet dans les 8 bits de poids fort

        for i in range(8):
            if crc & 0x8000:  # Bit de poids fort
                crc = (crc << 1) ^ poly
            else:
                crc <<= 1
            crc &= 0xFFFF  # Garder 16 bits

    return crc

# Test
message = [0x01, 0x02, 0x03]
crc = crc16_ccitt(message)
print(f"CRC-16 CCITT = 0x{crc:04X}")

CRC-32 (Ethernet, ZIP, PNG)

Paramètres

Polynôme : 0x04C11DB7
Valeur initiale : 0xFFFFFFFF
XOR final : 0xFFFFFFFF
Réflexion : Oui (bits et octets)

Algorithme

def crc32(data):
    crc = 0xFFFFFFFF
    poly = 0xEDB88320  # Polynôme réfléchi

    for byte in data:
        crc ^= byte
        for i in range(8):
            if crc & 1:
                crc = (crc >> 1) ^ poly
            else:
                crc >>= 1

    return crc ^ 0xFFFFFFFF

# Test
message = b"Hello"
crc = crc32(message)
print(f"CRC-32 = 0x{crc:08X}")

CRC dans le bus CAN

Spécificités CAN

Polynôme : \(x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1\)
Binaire : \(1100\,0101\,1001\,1001\) (0xC599)
Champ : SOF + Arbitrage + Contrôle + Données
Bit stuffing : Appliqué AVANT calcul CRC

Calcul CRC CAN

def crc_can(data_bits):
    poly = 0xC599  # Polynôme CAN
    crc = 0

    for bit in data_bits:
        crc ^= (bit << 14)  # Injecter le bit en position 14

        if crc & 0x4000:  # Bit de poids fort du CRC-15
            crc = (crc << 1) ^ poly
        else:
            crc <<= 1

        crc &= 0x7FFF  # Garder 15 bits

    return crc

Détection d'erreurs

Capacité de détection

Type d'erreur	CRC-8	CRC-16	CRC-32
1 bit	100%	100%	100%
2 bits	100%	100%	100%
Impair	100%	100%	100%
Rafale ≤ n bits	100%	100%	100%
Rafale > n bits	\(1-2^{-n}\)	\(1-2^{-n}\)	\(1-2^{-n}\)

Distance de Hamming

CRC-8 : Détecte jusqu'à 3 erreurs
CRC-16 : Détecte jusqu'à 3 erreurs
CRC-32 : Détecte jusqu'à 5 erreurs

Comparaison avec autres codes

Code	Taille	Détection	Correction	Complexité
Parité	1 bit	1 erreur	Non	Très faible
Checksum	8-16 bits	Limitée	Non	Faible
CRC	8-32 bits	Excellente	Non	Moyenne
Hamming	Variable	Bonne	1 erreur	Élevée
Reed-Solomon	Variable	Excellente	Oui	Très élevée

Applications

Protocoles de communication

CAN : CRC-15
Ethernet : CRC-32
USB : CRC-5, CRC-16
Modbus : CRC-16

Stockage

Disques durs : CRC-32
ZIP : CRC-32
PNG : CRC-32
RAID : CRC-64

Autres

Mémoires : ECC (codes de Hamming)
QR Code : Reed-Solomon
Satellites : Codes convolutifs