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) +...+ a₁x¹ + a₀x⁰ 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) = a₀ = 1, les autres coefficients sont égaux à 0 ou à 1.

Le polynôme CRC est représenté par son vecteur [C] = [a_r-1 a_r-2 ... a₁ a₀] composé de r bits.
exemples 1 Le vecteur [C] = [1 0 1 0 1] représente le polynôme C(X) = X⁴ + X² + 1.
Le vecteur [D] = [1 1 1 1 0] ne représente pas un polynôme CRC car a₀ = 0.
Le polynôme C(X) = X⁵ + X³ + 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] = [b_n-1 b_n-2 ...b₁ b₀] 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. 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 D₅ 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].

assignmentEXERCICES : Codeur CRC assignment

1- Trouvez les bits [C] du polynôme C(X) = x⁵ + x⁴ + x² +1.
2- Quel est l'ordre du polynôme C(X) = x¹⁶ + x¹⁵ + x² +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) = x⁶ + x¹ + 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 ] ?
C(X) = x⁴ + 1.    C(X) = x¹ + 1.    C(X) = x⁵ + x³ + 1.    C(X) = x³ + x² + x¹ + 1.

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. 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 ?
C(X) = x⁴ + 1.    C(X) = x¹ + 1.    C(X) = x⁵ + x³ + 1.    C(X) = x³ + x² + x¹ + 1.
7- Quels sont les bits de la trame [S] de la question 6 ?
8- Vérifiez si la trame reçue est en erreur.
Oui elle est en erreur.   Non elle n'est pas en erreur.
9- Justifiez votre réponse à la question 8 en déterminant les bits de [R^'].