Version 0.2
Ce document tente de décrire de façon pédagogique le principe du contrôle de CRC, aussi appelé «checksum» , et de son utilisation dans la procédure HDLC ( une couche de niveau 2 du protocole X25, qui sert de base à nombre d'autres ).
Je l'ai rédigé par ce que j'était insatisfait des support existants, bien que son contenu soit inspiré - les exemples sont repris in extenso - du support de Mr VANWYNSBERGHE, professeur au CNAM de Dijon. C'est un exellent professeur, dévoué à ses étudiants, qu'il en soit ici remercié.
Ce document est placé sous la licence Free Documentation Licence. Vous en trouverez le texte à l'adresse http://www.fsf.org/copyleft/fdl.html . Elle vous permet de copier sans restriction et de modifier ce texte selon vos besoin, pourvu que vous mainteniez cette licence pour les travaux dérivés. Ceci afin d'en assurer la perenité, et notre liberté à tous.
L'auteur original est Sylvain NAHAS . (myself@sylvain-nahas.com). Tous commentaires, suggestions d'ajout ou correction seront le bienvenu ( je suis fâché avec l'ortographe). Si vous trouvez simplement ce travail utile, un email pour le dire ne sera pas mal perçu :-)
Historique des versions
version 0.1 (21/06/2001) : premier jet
version 0.2 (22/06/2001) : ajout des exemples dans la dernière partie pour clarifier le propos. Quelques modifications cosmètiques pour le reste. Ajout de la partie bibliographie et de la signification des abréviations.
Tout d'abord, quelques révisions mathématiques pour ceusses qui en aurait besoin.
Xa * Xb = X (a+b)
X1 = X , X0 = 1
Xa / Xb = X (a-b)
Un polynôme P(x) est une fonction de x de la forme : P(x) = FN * XN + FN-1 * XN-1 + ... + F0 * X0 ,
les parties Fi sont membres de l'ensemble des réels et sont appellées facteurs d'indice i.
N est le degré du polynôme : il s'agit de l'exposant le plus élevé.
La partie Fk * Xk est appelée terme de degré k du polynôme.
La division de polynômes est une opération mathématique donnant comme résultat le calcul de deux valeurs polynomiales : un Quotient et un Reste (c'est une forme de division euclidienne).
Le degré du Reste est égal au plus à celui du Diviseur moins 1.
Ainsi : Dividende = Quotient * Diviseur + Reste
Pour la suite, il n'est pas nécessaire de rentrer dans les détail de l'éxecution.
Une addition ou division de polynôme se fait toujours terme à terme.
Ainsi , si A(x) = 15 * X4 + 6 * X2 + 45 et B(x) = 784 * X3 + 4 * X2 , alors :
A(x) + B(x) = 15 * X4 + 784 * X3 + (6+4) * X2 + 45
A(x) - B(x) = 15 * X4 - 784 * X3 + (6-4) * X2 + 45
Elle ressemble beaucoup à une division euclidienne comme on l'apprend à l'école.
Le résultat donne un quotient et un reste.
Le calcul bit à bit se fait par un ou exclusif .
|
XOR |
1 |
0 |
|---|---|---|
|
1 |
0 |
1 |
|
0 |
1 |
0 |
Par exemple, calculons la division de 11001010110000 par 10101 ...
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
Le reste est 0110 (degré 3) et le quotient 1111101110 (degré 9).
Remarquons que la somme des degrés du quotient et du diviseur est celui du dividende.
Elle se calcule par un ou exclusif entre les deux opérandes.
Ainsi :
110010 - 101010 = 011000
Les contrôles par CRC sont très utilisés. Ils sont plus fiables que les vieux systèmes de contrôles de parité et permette de travailler sur un ensemble binaire sans préjuger de sa structure interne..
CRC signifie Contrôle de Redondance Cyclique.
Considérons un nombre binaire codé sur N bits, par ex. 011001, où N=6 .
Représentons ce nombre sous forme d'un polynome de degré égal au nombre de bit (N) , de la forme : AN * XN + AN-1 * XN-1+ . . . + A0 * X0 ,
où l'indice N est la position à partir du bit de poid faible (à droite) , auquel est affecté l'indice 0,
et le facteur AN la valeur du bit d'indice N. ( Le bit est le facteur ... ).
Ainsi, le nombre 011001 s'écrit : M(x) = 0*X5 + 1*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0 . Comme 0 est élément absorbant, cela se simplifie en : 1*X4 + 1*X3 + 1*X0 = X4 + X3 + X0 = X4 + X3 + 1
Remarque : le polynôme de degré N est représenté par N+1 bits.
> On peut donc utiliser le calcul polynomial pour travailler sur des nombres binaires ! A la division polynomiale correspond la division binaire, à la soustraction des polynômes la soustraction binaire ...
On désire un algorithme qui permette de vérifier qu'un ensemble arbitraire de bits, transmis d'un émetteur à un récepteur, n'ait pas été modifié pendant le transport. Il faut remarquer que cela implique forcement l'envoi d'au moins deux lots d'informations corrélées, entraînant une redondance obligatoire . En fait, le plus simple - et le moins efficace - serait d'émettre deux fois les messages !
L'idée du CRC est de transmettre, conjointement aves les données significative, une valeur calculée par l'émetteur à partir des Data à transmettre. Le récepteur effectue le même calcul de son côté, et si le résultat est identique, alors le message n'a pas été modifié . Dans tout les autres cas, à recom' !
Le calcul va utiliser une opération de base : la division des polynômes.
Appelons M(x) le polynôme représentant les datas à coder. Son degré est représenté par m.
Chacune des deux extrêmités connaissent un polynôme de degré k , appelé générateur, que l'on nommera G(x).
a) La première étape consiste à multiplier M(x) par Xk. Le résultat P(x) = Xk * M(x) est un polynôme de degré m+k . En fait, cela provoque un décalage de M(x) de rang k vers la droite . Ça permet de garantir que la soustraction entre P(x) et un polynôme de degré k est toujours positive.
b) On effectue la division euclidienne de P(x) par G(x) . Le calcul fournit :
un Quotient Q(x) , et
un Reste R(x) de degré k-1.
Soit : P(x) = Q(x) * G(x) + R(x)
c) Le résultat final est calculé par S(x) = M(x) - R(x) = [ Q(x) * G(x) + R(x) ] - R(x) <=> S(x) = Q(x) * G(x) .
Donc, si l'on divise S(x) par G(x) , le reste doit être nul, des deux côtés de la connexion, ou alors les valeurs traitées ne sont pas les mêmes.
> Nous avons notre algorithme de vérification !
Le protocole affublé du nom euphonique de High Level Data Link Control fonctionne en mode synchrone duplex. Il a été normalisé par l'ISO et l'UITT. Il s'agit de la couche de niveau ISO deux du standard X25.
C'est un standard très utilisé. Par exemple dans les protocoles PPP et SLIP du monde internet. Les paquets IP sont encapsulés dans les trames X25 de façon à établir des circuits virtuels à travers un réseau commuté (voir ref. biblio.)
Dans le cas de l'HDLC , l'algorithme de CRC permet, de détecter des paquets d'erreur de 18 bits dans 99,998 des situations ...
Le polynôme générateur standard est X16 + X12 + X5 + 1 (degré 16, codé sur 17 bits)
L'algorithme ci-dessus est appliqué. Bien sûr, les opérations sont pratiquées sur des nombres binaires. Dans la suite, les nombres utilisés en exemple sont plus court que ceux réellement utilisés dans l'HDLC.
Le flux binaire à contrôler est « multiplié » par 100...(16 fois)..0 . Cela reviens à lui ajouter 16 zéro. On obtient un nombre binaire M.
> par exemple, soit 1100101011 une donnée à contrôler et 10101 un polynôme générateur codé en binaire (X4 + X2 + 1).
> le degré étant de 4, on multiplie par X4 , soit 10000. => décalage d'un rang 4 vers la gauche => M = 11001010110000
On opére la division binaire entre M et le Générateur. Le reste est un polynôme de degré 15.
> Le calcul plus haut. donne pour M / G = 11001010110000 / 10101 => Le reste R est 0110
remarque : en aucun cas la valeur du quotient n'est utilisé...
On soustrait de M le Reste R obtenu de la division précédente. Le résultat S est , ô miracle : les Data d'origine suivi du CRC ( appelé champ FCS pour Frame Control Sequence dans une trame HDLC). Le CRC/FCS est codé sur 16 bits dans une trame.
> dans l'exemple ci-dessus , S = M - R = 11001010110000 - 0110 = 11001010110110
Le récepteur divise les données reçues S par la valeur du Générateur. Si l'opération ne donne pas un reste nul, alors il y a eu modification des données lors du transport.
> Exercice : Vous êtes destinataire d'un message. Les données reçues sont 11010010110110. Y'a t'il eu des bits de modifiés lors du transport ? Effectuez le calcul de validation ...
Télécommunications . Principes, infrastructures et services, de Daniel Battu. ISBN 2 10 005530 5