- Introduction sur les calculs CRC
- Routines de calcul CRC gratuites à télécharger
Introduction sur les calculs CRC
Chaque fois que des données numériques sont stockées ou interfacées, la corruption des données peut se produire. Depuis le début de l’informatique, les gens ont pensé à des moyens de traiter ce type de problème., Pour les données série, ils ont trouvé la solution pour attacher un bit de parité à chaque octet envoyé. Ce mécanisme de détection simple fonctionne si un nombre impair de bits dans un octet change, mais un nombre pair de faux bits dans un octet ne sera pas détecté par le contrôle de parité. Pour surmonter ce problème, les gens ont recherché des mécanismes sonores mathématiques pour détecter plusieurs faux bits. Le calcul CRC ou la vérification de redondance cyclique en a été le résultat. De nos jours, les calculs CRC sont utilisés dans tous les types de communications. Tous les paquets envoyés sur une connexion réseau sont vérifiés avec un CRC., De plus, chaque bloc de données sur votre disque dur a une valeur CRC qui lui est attachée. Le monde informatique moderne ne peut pas se passer de ces calculs CRC. Voyons donc pourquoi ils sont si largement utilisés. La réponse est simple, ils sont puissants, détectent de nombreux types d’erreurs et sont extrêmement rapides à calculer, en particulier lorsque des puces matérielles dédiées sont utilisées.
On pourrait penser que l’utilisation d’une somme de contrôle peut remplacer les calculs CRC appropriés. Il est certainement plus facile de calculer une somme de contrôle, mais les sommes de contrôle ne trouvent pas toutes les erreurs. Prenons un exemple de chaîne et calculons une somme de contrôle d’un octet., L’exemple de chaîne est « Lammert » qui convertit en valeurs ASCII . La somme de contrôle d’un octet de ce tableau peut être calculée en ajoutant toutes les valeurs, plutôt que de la diviser par 256 et de conserver le reste. La somme de contrôle résultante est 210. Vous pouvez utiliser la calculatrice ci-dessus pour vérifier ce résultat.
Dans cet exemple, nous avons utilisé un octets somme de contrôle qui nous donne 256 valeurs différentes. L’utilisation d’une somme de contrôle de deux octets entraînera 65 536 valeurs de somme de contrôle différentes possibles et lorsqu’une valeur de quatre octets est utilisée, il y a plus de quatre milliards de valeurs possibles., Nous pourrions conclure qu’avec une somme de contrôle de quatre octets, la chance que nous ne détectons pas accidentellement une erreur est inférieure à 1 à 4 milliards. Cela semble plutôt bon, mais ce n’est que de la théorie. En pratique, les bits ne changent pas de manière purement aléatoire pendant les communications. Ils échouent souvent en rafales, ou électrique pointes. Supposons que dans notre exemple de tableau, le bit significatif le plus bas du caractère ‘L‘ est défini, et le bit significatif le plus bas du caractère ‘a‘ est perdu pendant la communication. Le récepteur verra ensuite le tableau représentant la chaîne « M’mmert »., La somme de contrôle de cette nouvelle chaîne est toujours de 210, mais le résultat est évidemment faux, seulement après deux bits modifiés. Même si nous avions utilisé une somme de contrôle longue de quatre octets, nous n’aurions pas détecté cette erreur de transmission. Le calcul d’une somme de contrôle peut donc être une méthode simple pour détecter les erreurs, mais ne donne pas beaucoup plus de protection que le bit de parité, indépendamment de la longueur de la somme de contrôle.
L’idée derrière un calcul de valeur de contrôle est simple. Utilisez une fonction F (bval,cval) qui entre un octet de données et une valeur de contrôle et produit une valeur de contrôle recalculée., En fait, les calculs de somme de contrôle décrits ci-dessus peuvent être définis de cette manière. Notre exemple de somme de contrôle d’un octet aurait pu être calculé avec la fonction suivante (en langage C) que nous appelons à plusieurs reprises pour chaque octet de la chaîne d’entrée. La valeur initiale de cval est 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
L’idée derrière calcul de CRC est de regarder les données comme un grand nombre binaire. Ce nombre est divisé par une certaine valeur et le reste du calcul est appelé CRC., La division dans le calcul CRC semble d’abord coûter beaucoup de puissance de calcul, mais elle peut être effectuée très rapidement si nous utilisons une méthode similaire à celle apprise à l’école. Nous allons par exemple calculer le reste pour le caractère ‘m‘—qui est 1101101 en notation binaire—en le divisant par 19 ou 10011. Veuillez noter que 19 est un nombre impair. Cela est nécessaire, comme nous le verrons plus loin. Veuillez vous référer à vos manuels scolaires car la méthode de calcul binaire ici n’est pas très différente de la méthode décimale que vous avez apprise lorsque vous étiez jeune. Cela pourrait seulement sembler un peu étrange., Les notations diffèrent également entre les pays, mais la méthode est similaire.
1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder
Avec décimale calculs vous pouvez rapidement vérifier que 109 divisé par 19 donne un quotient de 5 à 14 ans comme le reste. Mais ce que nous voyons aussi dans le schéma, c’est que chaque bit supplémentaire à vérifier ne coûte qu’une comparaison binaire et dans 50% des cas une soustraction binaire., Vous pouvez facilement augmenter le nombre de bits de la chaîne de données de test—par exemple à 56 bits si nous utilisons notre exemple de valeur « Lammert »—et le résultat peut être calculé avec 56 comparaisons binaires et une moyenne de 28 soustractions binaires. Cela peut être implémenté directement dans le matériel avec seulement très peu de transistors impliqués. Les algorithmes logiciels peuvent également être très efficaces.
Pour les calculs CRC, aucune soustraction normale n’est utilisée, mais tous les calculs sont effectués modulo 2. Dans cette situation, vous ignorez les bits de transport et, en effet, la soustraction sera égale à une opération exclusive ou., Cela semble étrange, le reste résultant a une valeur différente, mais d’un point de vue algébrique, la fonctionnalité est égale. Une discussion à ce sujet nécessiterait une connaissance de niveau universitaire de la théorie algébrique des champs et je suppose que la plupart des lecteurs ne sont pas intéressés par cela. Veuillez consulter la fin de ce document pour les livres qui en discutent en détail.
Maintenant, nous avons une méthode de calcul CRC qui est implémentable à la fois dans le matériel et le logiciel et a également un sentiment plus aléatoire que le calcul d’une somme de contrôle ordinaire. Mais comment fonctionnera-t-il dans la pratique lorsqu’un ou plusieurs bits se trompent?, Si nous choisissons le diviseur – 19 dans notre exemple-pour être un nombre impair, vous n’avez pas besoin de mathématiques de haut niveau pour voir que chaque erreur de bit sera détectée. En effet, chaque erreur de bit laissera le dividende changer avec une puissance de 2. Si par exemple le bit n passe de 0 à 1, la valeur du dividende augmentera avec 2n. Si par contre le bit n passe de 1 à 0, la valeur du dividende diminuera avec 2n. Comme vous ne pouvez diviser aucune puissance de deux par un nombre impair, le reste du calcul CRC changera et l’erreur ne passera pas inaperçue.,
La deuxième situation que nous voulons détecter est lorsque deux bits simples changent dans les données. Cela nécessite des mathématiques qui peuvent être lues dans le livre de Tanenbaum mentionné ci-dessous. Vous devez sélectionner votre diviseur très soigneusement pour être sûr que, indépendamment de la distance entre les deux mauvais bits, vous aurez toujours les détecter. Il est connu que les valeurs couramment utilisées 0x8005 et 0x1021 des calculs CRC16 et CRC-CCITT fonctionnent très bien à ce problème., Veuillez noter que d’autres valeurs peuvent ou non, et vous ne pouvez pas facilement calculer quelle valeur divisatrice est appropriée pour détecter les erreurs de deux bits et laquelle ne l’est pas. Comptez sur des recherches mathématiques approfondies sur cette question effectuées il y a quelques décennies par des mathématiciens hautement qualifiés et utilisez les valeurs obtenues par ces personnes.
De plus, avec notre calcul CRC, nous voulons détecter toutes les erreurs où un nombre impair de bits change. Ceci peut être réalisé en utilisant un diviseur avec un nombre pair de bits. En utilisant les mathématiques modulo 2, vous pouvez montrer que toutes les erreurs avec un nombre impair de bits sont détectées., Comme je l’ai déjà dit, en mathématiques modulo 2, la fonction de soustraction est remplacée par le ou exclusif. Il y a quatre opérations XOR possibles.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
Nous voyons que, pour toutes les combinaisons de valeurs des bits, la singularité de l’expression reste le même. Lors du choix d’un diviseur avec un nombre pair de bits, l’étrangeté du reste est égale à l’étrangeté du dividende. Par conséquent, si l’étrangeté du dividende change parce qu’un nombre impair de bits change, le reste changera également., Ainsi, toutes les erreurs qui modifient un nombre impair de bits seront détectées par un calcul CRC qui est effectué avec un tel diviseur. Vous avez peut-être vu que les valeurs de diviseur couramment utilisées 0x8005 et 0x1021 ont en fait un nombre impair de bits, et pas même comme indiqué ici. En effet, à l’intérieur de l’algorithme, il y a un bit supplémentaire « caché” 216 qui rend la valeur de diviseur utilisée réelle 0x18005 et 0x11021 à l’intérieur de l’algorithme.,
Enfin, nous voulons détecter toutes les erreurs de rafale avec notre calcul CRC avec une longueur maximale à détecter, et toutes les erreurs de rafale plus longues à détecter avec une forte probabilité. Une erreur de rafale est assez courante dans les communications. C’est le type d’erreur qui se produit à cause de la foudre, de la commutation de relais, etc. lorsque, pendant une petite période, tous les bits sont à un., Pour vraiment comprendre cela, vous devez également avoir une certaine connaissance de l’algèbre modulo 2, alors veuillez accepter qu’avec un diviseur de 16 bits, vous serez capable de détecter toutes les rafales d’une longueur maximale de 16 bits, et toutes les rafales plus longues avec au moins 99,997% de certitude.
Dans une approche mathématique pure, le calcul CRC est écrit comme des calculs polynomiaux. La valeur du diviseur n’est le plus souvent pas décrite comme un nombre binaire, mais un polynôme d’un certain ordre. Dans la vie normale certains polynômes sont utilisés plus souvent que les autres., Les trois utilisés dans le calcul CRC en ligne sur cette page sont les 16 bits de large CRC16 et CRC-CCITT et les 32 bits de large CRC32. Ce dernier est probablement le plus utilisé maintenant, car entre autres c’est le générateur CRC pour toute la vérification et la validation du trafic réseau.
Pour les trois types de calculs CRC, j’ai une bibliothèque de logiciels libres disponible. Le programme de test peut être utilisé directement pour tester des fichiers ou des chaînes. Vous pouvez également regarder les codes source et intégrer ces routines CRC dans votre propre programme., Veuillez prendre connaissance des valeurs d’initialisation du calcul CRC et des éventuels post-traitements nécessaires tels que les bits de retournement. Si vous ne le faites pas, vous pourriez obtenir des résultats différents de ceux des autres implémentations CRC. Tout ce pré et post-traitement se fait dans l’exemple de programme, il ne devrait donc pas être difficile de faire fonctionner votre propre implémentation. Un test couramment utilisé consiste à calculer la valeur CRC pour la chaîne ASCII « 123456789”., Si le résultat de votre routine correspond au résultat du programme de test ou au résultat de ce site Web, votre implémentation fonctionne et est compatible avec la plupart des autres implémentations.
Juste comme référence les fonctions polynomiales pour les calculs CRC les plus courants. N’oubliez pas que le terme d’ordre le plus élevé du polynôme (x16 ou x32) n’est pas présent dans la représentation des nombres binaires, mais impliqué par l’algorithme lui-même.,
| Littérature | ||
| 2002 | Réseaux Informatiques, décrivant en réseau des systèmes et de la théorie et algorithmes à l’origine de leur mise en œuvre. | Andrew S. Tanenbaum |
| divers | L’Art de la Programmation Informatique est la principale référence pour les semi-algorithmes numériques. Les calculs polynomiaux sont décrits en profondeur. Un certain niveau de mathématiques est nécessaire pour bien le comprendre. | Donald E. Knuth |
| – | DNP 3.,0, ou protocole de réseau distribué est un protocole de communication conçu pour être utilisé entre les ordinateurs de sous-station, les unités terminales distantes RTU, les appareils électroniques intelligents IED et les stations maîtresses pour l’industrie des services publics d’électricité. Il est maintenant également utilisé dans des industries familières comme le traitement des eaux usées, le transport et l’industrie pétrolière et gazière. | DNP Groupe d’Utilisateur |
Laisser un commentaire