L'ALGORITHME CRC : 'CYCLIC REDUNDANCY CHECK / CODE'



1. Définitions :
Avant d'expliquer le fonctionnement de l'algorithme CRC il est nécessaire de définir les paramètres importants à l'exécution de cet algorithme.
1.a Le polynôme CRC : Une expression mathématique P(x) = a(r-1)x(r-1) + a(r-2)x(r-2) +...+ a1x1 + a0x0 est dite un polynôme si et seulement si les puissances de x sont ≥ 0 et les coefficients de la variable x ∈ ℝ. Un polynôme CRC nommé C(X) est un sous ensemble des polynômes P(x). Un P(x) est un C(X) si et seulement si il remplit la condition suivantes :
  • Les coefficients a(r-1) = a0 = 1, les autres coefficients sont égaux à 0 ou à 1.
Le polynôme CRC est représenté par son vecteur [C] = [ar-1 ar-2 ... a1 a0] composé de r bits.
exemples 1 Le vecteur [C] = [1 0 1 0 1] représente le polynôme C(X) = X4 + X2 + 1.
Le vecteur [D] = [1 1 1 1 0] ne représente pas un polynôme CRC car a0 = 0.
Le polynôme C(X) = X5 + X3 + X + 1 est représenté par [C] = [1 0 1 0 1 1].
1.b Ordre et dimension : La dimension d'un vecteur [C] est nommée dim[C] = r le nombre des bits de ce vecteur. L'ordre du polynôme C(X) est O{C(X)} = r-1. L'ordre du polynôme est égal à la plus grande puissance présente dans le polynôme. On peut écrire que O{C(X)} = dim [C] - 1.
1.c Choix du polynôme CRC : Soit la séquence [S] = [bn-1 bn-2 ...b1 b0] composée de n bits. Pour coder cette séquence par un polynôme CRC il faut et il suffit que dim[C] ≤ dim[S].
2. Fonctionnement du codeur CRC :
Le schéma bloc ci-dessous nous montre l'opération du codeur CRC. codeur CRC En utilisant un polynôme CRC approprié, le codeur effectue le calcul {[S] modulo-2 [C]} qui est une division binaire mod-2. Il produit les bits nommés [R] qui sont les restes de cette division. Les bits [R] sont les bits de contrôle employés afin de détecter un bit de la trame [S] en erreur. La dimension de [R] est égale à dim[C] -1 ou bien : dim[R] = dim[C]-1 = O{C(X)}.
2.a Division binaire modulo-2 : La division binaire mod-2 est illustrée par la figure ci-dessous. Dans cet exemple les bits de données S = [1 1 0 1 0] et les bits [C] = [1 0 0 0 1]. On ajoute à la fin de la trame [S] 4 '0' [0 0 0 0 0] . Ces 4 '0' représentent ce qui va devenir à la fin de la division les bits de contrôle [R]. Note : On ajoute 4 '0' car la dimension de [R] = dim[C] - 1 = 4. À la fin de la division modulo-2 on obtient les bits de contrôle R = [1 1 0 1 0] . En téléphonie et selon le format D5 les bits de [R] sont placés au début des trames 2, 6, 10, 14, 18 et 22 et dans notre exemple ils sont juxtaposés à la fin de la trame transmise [S || R].
division modulo 2

assignmentEXERCICES : Codeur CRC assignment

1- Trouvez les bits [C] du polynôme C(X) = x5 + x4 + x2 +1.
2- Quel est l'ordre du polynôme C(X) = x16 + x15 + x2 +1?
3- La trame [S] = [1 0 0 1 0 1 1] est codée par le polynôme C(X) de la question 1. Quelle est le nombre des bits de contrôle [R] ?
4- La trame [S] = [1 0 0 1 0 1 1 0] est codée par le polynôme C(X) = x6 + x1 + 1. Trouvez les bits de contrôle [R] ?
5- Lequel des polynômes ci-dessous ne peut pas coder la trame [S] = [1 0 0 1 0 ] ?
        



LE DÉCODEUR CRC

3. Fonctionnement du décodeur CRC :
L'opération du décodeur est similaire à celle du codeur. En fait le récepteur utilise le même polynôme C(X) et divise modulo-2 la trame reçue [S || R]. Soit [R'] les bits du reste de cette division la trame reçue n'est pas en erreur si et seulement si [R'] = [0...0]. La figure suivante représente l'opération du décodeur CRC. décodeur CRC division modulo-2 au décodeur CRC Note : La division ci-dessus fait suite à l'exemple précédent. La trame transmise est [S || R] = [ 1 1 0 1 0 || 1 0 1 1 ]. Elle est divisée mod-2 par [C] = [1 0 0 0 1] et le reste de cette division est [R'] = [ 0 0 0 0 ] alors la trame [S] n'est pas en erreur vérifiant ainsi la théorie de l'algorithme CRC.
4. Applications du CRC :
L'algorithme CRC est utilisé dans plusieurs systèmes de télécommunication. La table ci-dessous nous donne ces différents systèmes ainsi que le polynôme employé.
Systèmes Descriptif polynôme
CRC-6
ITU G.704
Structures de trame synchrone T1 et E1 x6 + x1 + 1
CRC-16-CCITT X.25 : Services bancaires, Bluetooth, PPP (HDLC) x16 + x12 + x5 +1
CRC-16 USB x16 + x15 + x2 +1
CRC-32-IEEE802.3 Ethernet (LAN), MPEG2 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1


assignmentEXERCICES : DÉCODEUR CRC assignment

6- La trame [S||R] = [1 0 1 1 0 1 1 0 1 0] est à la sortie d'un codeur CRC. Si dim[R] = 4 lequel des polynômes C(X) est utilisé par le décodeur afin de déterminer si la trame est en erreur ?
        
7- Quels sont les bits de la trame [S] de la question 6 ?
8- Vérifiez si la trame reçue est en erreur.
  
9- Justifiez votre réponse à la question 8 en déterminant les bits de [R'].