CRC



--Téléchargez CRC en PDF --


Le contrôle de redondance cyclique (Cyclic Redundancy Check – CRC) est le code de contrôle d’intégrité le plus fiable. Il est aussi facile à utiliser. C’est la principale méthode de détection d’erreurs utilisées dans les télécommunications (comme ethernet).

Le CRC consiste à vérifier des blocs entiers de données, appelés trames (ou frames). Comme son nom l’indique, le CRC contient des données redondantes par rapport à la trame, qui permet de détecter les erreurs.

Principe

Comme nous l’avons vu, un nombre binaire peut s’exprimer sous forme de polynôme (pour rappel : 1001_2 = x^3+x^0 = x^3+1 ) Le CRC est le reste de la division euclidienne du message décalé de n bits divisé par un polynôme générateur de degré n, connu de l’émetteur et du récepteur.

CRC = (x^n * M) mod G

où M est le message et G le polynôme générateur.

Le CRC sera de degré n-1 par rapport au polynôme générateur.

Le message reçu par le destinataire sera le message d’origine auquel nous aurons concaténé le CRC : M' = x^n*M + CRC

Pratiquement

Posons M = 111 01012 et G = x4+x²+x1.

  • Comme G est de degré 4, il faut décaler M de 4 bits vers la gauche. On ajoutera donc 4 « 0 » en fin de message. Le CRC sera alors de degré 3.

  • Le CRC est le reste de la division euclidienne entre M et G.

  • Il existe deux petits trucs pour calculer rapidement un CRC :

    • Pour chaque ligne, nous utiliserons l’opération xor, qui est plus rapide que la soustraction et qui donne le même résultat.

    • Comme le quotient n’est pas nécessaire, retenez ceci : à chaque ligne, déplacez-vous d’un bit à droite et regardez le MSB. Si le MSB vaut 1, faites le xor avec G. Sinon, décalez-vous encore d’un rang vers la droite.

1

1

1

0

1

0

1

0

0

0

0

1

0

1

1

0

0

1

0

1

1

0

1

0

1

1

0

0

0 →

0 →

0 →

0 →

1

0

0

0

0

1

0

1

1

0

0

0

1

1

0

Le CRC est d’ordre 3 et vaut 0110.

Pour générer le message à transférer, nous allons concaténer le CRC au message.

Vérification

La procédure de vérification se base sur le même procédé. Le destinataire reçoit le message M’. Pour vérifier si le message est bien transmis, il devra faire la division euclidienne de M’ par G. Le message sera bien transmis si le reste de la division vaut 0.

Reprenons notre message M’.

1

1

1

0

1

0

1

0

1

1

0

1

0

1

1

0

0

1

0

1

1

0

1

0

1

1

0

0

0 →

0 →

0 →

0 →

1

0

1

1

0

1

0

1

1

0

0

0

0

0

0

Le reste de la division vaut bien 0, le message à été correctement transféré. En cas de perturbation du signal, le reste de la division ne sera pas nul, signalant que le message est corrompu.

Utilisez l’exerciseur !


« Méthode du bit de parité Hamming »