Le CRC

Généralités

Le contrôle de redondance cyclique ou (CRC) est un moyen de contrôle d’intégrité des données efficace et facile à mettre en œuvre.

Il représente la principale méthode de détection d’erreurs utilisée dans les télécommunications.

Le CRC est le résultat d’un calcul effectué sur les octets d’une trame et qui est inséré à la fin de celle-ci avant sa transmission.

Le récepteur effectue alors le même calcul et compare le résultat à celui présent dans la trame pour déterminer s’il y a eu ou non corruption de données.

Calcul du CRC

La division polynomiale est au cœur du calcul du CRC.

Cela signifie que les valeurs binaires utilisées dans le calcul sont traitées comme des polynômes et non comme de simples suites de bits.

Avec cette approche, chaque bit représente un coefficient d’un polynôme

Ainsi, la séquence 10011 peut être vue comme le polynôme 1.x⁴ + 0.x³ + 0.x² + 1.x¹ + 1.x⁰ soit x⁴+x¹+1.

On peut généraliser en disant qu’à chaque séquence de N+1 bits correspond un polynôme de degré N.

Tout comme la division euclidienne classique, la division polynomiale utilisée dans le cadre du calcul du CRC est composée :

d’un dividende → la séquence de bits qui constitue le corps du message à tansmettre
d’un diviseur → une autre séquence de bits — déterminée à l’avance — appelée polynôme générateur.

La division polynomiale est alors effectuée à l’aide d’une division binaire modulo 2 qui implique de simples opérations XOR.

Le reste de cette division constitue le CRC.

Le choix du polynôme générateur — longueur et valeur — va déterminer le type de CRC obtenu. En effet, il existe plusieurs types de CRC :

le CRC-8 (degré 8 ⇒ polynôme générateur de 9 bits)
- CRC8_ITU → polynôme générateur x⁸+x²+x+1
- CRC8_MAXIM → polynôme générateur x⁸+x⁵+x⁴+1
le CRC-16 (degré 16 ⇒ polynôme générateur de 17 bits),
- CRC16_KERMIT → polynôme générateur x¹⁶+x¹²+x⁵+1
- CRC16_MODBUS → polynôme générateur x¹⁶+x¹⁵+x²+1
…

Le calcul de chaque CRC dépend aussi d’autres paramètres comme sa valeur initiale lors de son calcul, l’ordre des bits du message … (voir plus loin)

Les valeurs du polynôme générateur sont plus ou moins standardisées.

Comme dit plus haut, la division binaire modulo 2 du message par le polynôme générateur revient en fait simplement à faire des OU EXCLUSIFs entre le dividende (→ le message à envoyer) et le diviseur (→ le polynôme générateur).

Ci-dessous, un exemple de calcul du CRC-3 dît GSM — dont le polynôme générateur vaut x³+x+1 c’est-à-dire 1011 — sur le message 10010100.
(Le détail du calcul figure après l’illustration)

 10010100000        | 1011
 1011      .        +---------
  0100     .        |10101011
  0000     .        |(quotient sans intérêt)
   1001    .        |
   1011    .        |
    0100   .        |
    0000   .        |
     1000  .        |
     1011  .        |
      0110 .        |
      0000 .        |
       1100.        |
       1011.        |
        1110        |
        1011        |
        0101 <- CRC |

Détails du calcul :

on rajoute trois ‘0’ au message car le polynôme générateur est de degré 3
on prend les 4 1^ers bits du message (→ 1001).

comme le bit de poids fort est ‘1’ :

on met ‘1’ dans le quotient
on aligne le diviseur (→ 1011) sous les 4 1^ers bits du message (→ 1001)

on fait un OU EXCLUSIF entre ces 2 groupes de 4 bits et on obtient 0010 (← 1001 ^ 1011 = 0010).
Note : Le 1^er '0' du résultat n’est pas représenté dans l’illustration pour plus de clarté

Ne pas oublier que nous sommes dans un contexte de division polynomiale et non de division classique.

Dans une division classique, 1001₂ ÷ 1011₂ (→ 9₁₀ ÷ 11₁₀) donnerait un quotient de 0 et un reste de 1001₂ (→ 9₁₀).

Ici, la division binaire modulo 2 effectuée doit être interprétée comme x³+1 ÷ x³+x+1.

Pour faire ce calcul, nous divisons le plus grand terme en degré du dividende (x³) par le terme en degré le plus élevé du diviseur (x³ également). Cela nous donne le premier terme du quotient (→ 1). Nous multiplions ensuite le diviseur par ce terme (→ 1011 x 1 = 1011) et le combinons au dividende (→ 1001) avec un XOR, ce qui donne un nouveau polynôme (1001 ^ 1011 = 0010).

on insère à droite du résultat le bit suivant du message (→ 0). On obtient les 4 bits 0100
comme ces 4 bits débutent par un ‘0’, on rajoute ‘0’ au quotient et au lieu d’aligner le diviseur (→ 1011) sous ces 4 bits, on met la valeur 0000
on effectue, comme dans l’étape 3, un OU EXCLUSIF entre 0100 et 0000 pour obtenir 0100 (1^er ‘0’ toujours pas représenté dans l’illustration)
on insère à droite du résultat le bit suivant du message (→ 1). On obtient les 4 bits 1001
on répète le processus jusqu’à ce qu’on atteigne le dernier bit du message
la valeur obtenue avec le dernier OU EXCLUSIF (→ le reste de la division) représente la valeur du CRC

Vérification du calcul dans la calculatrice en ligne Galois Field GF(2) Calculator link :

CRCs standardisés

On l’a vu, à chaque CRC standardisé est associé un polynôme générateur précis.

Cependant, d’autres paramètres sont également définis pour chaque CRC :

valeur initiale : c’est la valeur initiale du CRC à prendre en compte en début de calcul
entrée reflétée (→ Reflected Input ou RefIn) : indique s’il faut inverser chaque octet du message d’entrée avant qu’il soit utilisé dans le calcul du CRC
sortie reflétée (→ Reflected Output ou RefOut) : indique si la valeur du CRC doit être inversée avant d’être retournée
valeur XOR final : valeur avec laquelle il faut faire un OU EXCLUSIF avec le CRC calculé avant qu’il ne soit retourné
contrôle de CRC (→ Check): valeur parfois donnée qui correspond à la valeur du CRC à obtenir lorsqu’on l’applique au message d’entrée “123456789” (→ octets 0x30, 0x31…0x39)

Tableau 1. Exemple des caractéristiques du CRC-8 Maxim
Name	Width	Polynom	Init	RefIn	RefOut	XorOut	Check
CRC-8	8	0x31 (x8+x5+x4+1)	0x00	true	true	0x00	0xA1

La valeur hexadécimale du polynôme générateur ne mentionne jamais le bit de poids fort car il est forcément toujours égal à 1.

Dans l’exemple donné, le polynôme générateur est x⁸+x⁵+x⁴+1, ce qui correspond à la séquence de bits 100110001, donc normalement 0x131 en hexadécimal. Or, dans le tableau, est indiqué simplement 0x31.

Il faudra donc bien veiller à utiliser 100110001 (→ 0x131) et non 110001 (→ 0x31) pour le polynôme générateur à utiliser comme diviseur dans la division polynomiale.

Calcul d’un CRC-8 Maxim dans un calculateur en ligne :

On voit que le résultat obtenu sur la séquence 0x31, 0x32 … 0x39 correspond bien à celui indiqué dans le champ “Check” des caractéristiques du CRC-8 Maxim.

Étude de cas

On va coder ici un script Python qui permet de calculer le CRC-8 utilisé dans les trames renvoyées par un capteur de débit SF04 de chez Sensirion.

Les détails sur ce CRC ainsi qu’une proposition d’algorithme et de code source C pour le calculer sont présents dans ce document pdf .

Ci-dessous la transcription Python du code source proposé dans le document :

def calculeCRC8(data) :
    POLYNOME_GENERATEUR = 0x131
    crc = 0x00 # valeur initiale
    for octet in data :
        crc ^= octet
        for bit in range(0,8):
            if(crc & 0x80 != 0):
                crc = (crc << 1) ^ POLYNOME_GENERATEUR
            else :
                crc <<= 1
    return crc

if __name__ == "__main__":
    trame = [0x87, 0x01]
    crc8 = calculeCRC8(trame)
    print(f"CRC-8 Sensirion sur {[hex(d) for d in trame]}: {hex(crc8)}") 
    # Affiche : 
    # CRC-8 Sensirion sur ['0x87', '0x1']: 0xbc (1)

1	0xBC est bien la valeur du CRC donnée dans l’exemple utilisé dans le document.

Références :

CRC Calculator (Javascript)
→ calculateur en ligne de différents CRCs
…et son article associé pour une description détaillée du calcul du CRC
Galois Field GF(2) Calculator
→ calculateur en ligne qui détaille la division polynomiale
CRC : Cyclic Redundancy Check
→ article synthétique sur le calcul de CRC

🞄 🞄 🞄