Détection des erreurs (Crc

10/2/2018

2631

Détection des erreurs (Crc

UN GUIDE INDOLORE À l'ERREUR CRC ALGORITHMES de DÉTECTION

===================================================================
Cet article a été mis sur le web par SPLat les Contrôles, les décideurs
de la SPLat gamme de microPLCs pour l'utilisation OEM.
SPLat est les mondes & #39 plus rentable microPLC.
De hors-the-shelf produits qui vous feront gagner plus que ce qu'elles coûtent, à
l'utilisateur personnalisée-automates programmables, SPLat est un de surprenantes nouvelles
mode de prise de commandes électroniques pour les machines dans des quantités
1 à 50 000 p.un.

Pour vérifier SPLat copier et coller l'URL suivante dans votre navigateur
d'adresse ou d'emplacement de la fenêtre:
http://splatco.com
===================================================================
l'Article est reproduit avec la permission du propriétaire du droit d'auteur. Profitez-en!
===================================================================

UN GUIDE INDOLORE À l'ERREUR CRC ALGORITHMES de DÉTECTION
==================================================
'Tout ce que vous vouliez savoir sur CRC algorithmes, mais ont peur
pour demander, de peur que les erreurs de votre compréhension peut être détecté.'

Version : 3.
Date : 19 août 1993.
Auteur : Ross, N. Williams.
Net : [email protected].
FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
l'Entreprise : Rocksoft^tm Pty Ltd.
l'Escargot : 16 Lerwick Avenue, Hazelwood Parc 5066, en Australie.
Fax : 61 8 373-4911 (c/- entre-nœud Systems Pty Ltd).
Téléphone : 61 8 379-9217 (10h à 10h Adélaïde, en Australie du temps).
Note : 'Rocksoft' est une marque de commerce de Rocksoft Pty Ltd, Australie.
Statut : Copyright (C) Ross Williams, 1993. Toutefois, l'autorisation est
accordées à faire et distribuer des copies conformes de ce
document à condition que ce bloc d'informations et le droit d'auteur
avis est inclus. Aussi, les modules de code C inclus
dans ce document sont entièrement domaine public.
Merci : Merci à Jean-loup Gailly ([email protected]) et Mark Adler
([email protected]) qui à la fois la preuve de la lecture de ce document
et pris beaucoup de lentes ainsi que quelques gros bugs.

Table des Matières
& & & & & & & & -
Abrégé
1. Introduction: la Détection de l'Erreur
2. La Nécessité Pour la Complexité
3. L'Idée de Base Derrière CRC Algorithmes
4. Polynomical Arithmétique
5. Arithmétique binaire avec Pas de Porte
6. Entièrement Travaillé par Exemple
7. Le choix d'Un Poly
8. Un Simple CRC mise en Œuvre
9. Une Table-Driven mise en Œuvre
10. Une légère Déformation de la Table-Driven mise en Œuvre
11. 'Réfléchie' Table-Driven Implémentations
12. 'Inversé' Polys
13. Valeurs initiale et Finale
14. La définition d'Algorithmes Absolument
15. Un Modèle Paramétré Pour le CRC Algorithmes
16. Un Catalogue de Jeux de paramètres pour les Normes
17. Une Implémentation de l'Algorithme de Modèle
18. Rouler Votre Propre Table-Driven mise en Œuvre
19. Génération d'Une Table de Recherche
20. Résumé
21. Corrections
A. Glossaire
B. les Références
C. Références que j'Ai Détecté Mais n'avez & #39 t Encore Voyante

Résumé
& & & &
Ce document explique Crc (contrôle de Redondance Cyclique Codes) et leur
table-driven mises en œuvre dans le plein, la précision des détails. Une grande partie de la
littérature sur CRCs, et en particulier sur leur table-driven
implémentations, est un peu obscur (ou du moins semble donc, pour moi).
Ce document est une tentative pour donner une idée claire et simple no-nonsense
explication de la Cdc et de préciser tous les détails de la
fonctionnement de leur haute vitesse implémentations. En plus de cela,
ce document présente un modèle paramétré CRC algorithme appelé la
'Rocksoft^tm Modèle CRC Algorithme'. Le modèle de l'algorithme peut être
paramétrée à se comporter comme la plupart de la CRC applications,
et agit ainsi comme une bonne référence pour la description des algorithmes spéciaux.
à faible vitesse de mise en œuvre du modèle CRC algorithme est fourni dans
le langage de programmation C. Enfin il y a une section donnant deux formes
de haute vitesse de la table par les implémentations et fournir un programme
qui génère CRC tables de recherche.

1. Introduction: la Détection de l'Erreur
& & & & & & & & & & & & & & & &
Le but d'une erreur technique de détection est de permettre au récepteur d'un
message transmis par un bruyant (erreur-l'introduction) de canal
déterminer si le message a été endommagé. Pour ce faire, le
émetteur construit une valeur (appelée ' somme de contrôle) qui est une fonction
du message, et l'ajoute au message. Le récepteur peut alors
utiliser la même fonction pour calculer la somme de contrôle de la
message et de le comparer avec les joints en annexe de la somme de contrôle pour voir si le
le message a été correctement reçu. Par exemple, si nous avons choisi une somme de contrôle
fonction qui était tout simplement la somme des octets du message mod 256
(c'est à dire modulo 256), alors il peut aller quelque chose comme suit. Tous les numéros
sont en décimal.

Message : 6 23 4
Message avec la somme de contrôle : 6 23 4 33
Message après transmission : 6 27 4 33

ci-dessus, le deuxième octet du message a été endommagé du 23 au
27 par le canal de communication. Cependant, le récepteur peut détecter
cela en comparant la transmission de la somme de contrôle (33) avec l'ordinateur
somme de contrôle de 37 (6 27 4). Si la somme de contrôle est endommagé, un
correctement transmis le message peut être identifié à tort comme une
qui est corrompue. Toutefois, c'est sûr, à côté de l'échec. Un dangereux côté
défaillance se produit lorsque le message et/ou de la somme de contrôle est endommagé dans un
manière que les résultats d'une transmission qui est d'une cohérence interne.
Malheureusement, cette possibilité est totalement inévitable et le meilleur,
qui peut être fait est de réduire sa probabilité par l'augmentation de la
quantité d'informations dans la somme de contrôle (par exemple, l'élargissement de la somme de contrôle
un octet deux octets).

Autre erreur de détection il existe des techniques qui impliquent l'exécution complexe
des transformations sur le message pour l'injecter avec redondant
informations. Cependant, ce document ne traite que de la CRC algorithmes,
qui entrent dans la classe des algorithmes de détection d'erreur qui sortent de l'
données intact, et ajouter une somme de contrôle sur la fin. c'est à dire:

2. La Nécessité Pour la Complexité
& & & & & & & & & & & & &
Dans l'exemple de la somme de contrôle dans la section précédente, nous avons vu comment un
message endommagé a été détectée à l'aide d'un algorithme de checksum simplement
sommes les octets du message mod 256:

Message : 6 23 4
Message avec la somme de contrôle : 6 23 4 33
Message après transmission : 6 27 4 33

Un problème avec cet algorithme est qu'il est trop simple. Si un certain nombre de
au hasard, des altérations se produisent, il y a 1 à 256 chance qu'ils
ne pas être détecté. Par exemple:

Message : 6 23 4
Message avec la somme de contrôle : 6 23 4 33
Message après transmission : 8 20 5 33

Pour renforcer la somme de contrôle, nous pourrions changer d'un 8-bit registre de
un registre 16 bits (c'est à dire la somme des octets d'un mod 65536 au mod 256) donc,
comme, apparemment à réduire la probabilité de défaillance de 1/256
1/65536. Alors que fondamentalement une bonne idée, il échoue dans ce cas, parce que
la formule utilisée n'est pas assez 'aléatoire' avec une simple sommation
formule, chaque octets entrants touche environ d'un seul octet de la
sommation de s'inscrire n'importe comment, il est. Par exemple, dans la seconde
l'exemple ci-dessus, la synthèse registre pourrait être un Mégaoctet de large, et l'
l'erreur serait encore passer inaperçus. Ce problème ne peut être résolu que par des
remplacement de la simple sommation formule avec une version plus sophistiquée de la formule
que provoque chaque octets entrants ont un effet sur l'ensemble de la
somme de contrôle de registre.

Ainsi, nous voyons qu'au moins deux aspects sont nécessaires pour former un solide
somme de contrôle de la fonction:

LARGEUR: la largeur de registre assez large pour fournir un faible a priori
probabilité de défaillance (par exemple, 32-bits donne un 1/2^32 chance
de panne).

le CHAOS: UNE formule qui donne à chacune d'octets d'entrée le potentiel de changement
n'importe quel nombre de bits dans le registre.

Note: Le terme 'somme de contrôle' a été probablement utilisé pour décrire début
en additionnant les formules, mais il a pris un sens plus général
englobant des algorithmes plus sophistiqués tels que la CDE. L'
CRC algorithmes décrits satisfaire à la deuxième condition, très bien,
et peut être configuré pour fonctionner avec une variété de somme de contrôle largeurs.

3. L'Idée de Base Derrière CRC Algorithmes
& & & & & & & & & & & & & & & & & & & -
Où pourrions-nous aller dans notre recherche d'une fonction plus complexe
sommation? Toutes sortes de régimes viennent à l'esprit. Nous avons pu construire
tables à l'aide des chiffres de pi, ou de hachage de chaque octets entrants avec tous les
octets dans le registre. On pourrait même tenir un grand livre de téléphone
sur la ligne, et utiliser chaque octets entrants combiné avec le registre octets
pour indexer un nouveau numéro de téléphone qui serait la prochaine valeur de registre.
Les possibilités sont infinies.

Cependant, nous n'avons pas besoin d'aller si loin la prochaine arithmétique étape
suffit. Tandis que l'addition est clairement pas assez forte pour former un
efficace de la somme de contrôle, il s'avère que la division est, aussi longtemps que le
diviseur est à peu près aussi large que la somme de contrôle de registre.

L'idée de base de la convention des algorithmes est de simplement traiter le message comme un
énorme nombre binaire, de la diviser par un autre fixe nombre binaire,
et pour faire le reste de cette division de la somme de contrôle. Lors de la
la réception du message, le récepteur peut effectuer la même division, et
comparer le reste avec le 'checksum' (transmis reste).

Exemple: Supposons que le message se composait de deux octets (6,23)
dans l'exemple précédent. Ceux-ci peuvent être considérés comme les hexadécimal
numéro de 0617 qui peut être considéré comme le nombre binaire
0000-0110-0001-0111. Supposons que nous avons d'utiliser un registre de total de contrôle d'un octet
large et utiliser une constante diviseur de 1001, alors la somme de contrôle est la
reste après 0000-0110-0001-0111 est divisé par 1001. Alors que dans ce
cas, ce calcul ne peut évidemment être effectuées à l'aide de commun
jardin divers registres 32 bits, dans le cas général, c'est salissant. Donc,
au lieu de cela, nous & #39 ll faire la division à l'aide de bonnes & -#39 ol division longue qui vous
appris à l'école (vous vous souvenez?). Sauf que cette fois, c' & #39 s en binaire:

...0000010101101 = 00AD = 173 = QUOTIENT
& _ & & & & &
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDENDE
DIVISEUR 0000.,,....,.,,,
& & .,,....,.,,,
0000,,....,.,,,
0000,,....,.,,,
& & ,,....,.,,,
0001,....,.,,,
0000,....,.,,,
& & ,....,.,,,
0011....,.,,,
0000....,.,,,
& & ....,.,,,
0110...,.,,,
0000...,.,,,
& & ...,.,,,
1100..,.,,,
1001..,.,,,
====..,.,,,
0110.,.,,,
0000.,.,,,
& & .,.,,,
1100,.,,,
1001,.,,,
====,.,,,
0111.,,,
0000.,,,
& & .,,,
1110,,,
1001,,,
====,,,
1011,,
1001,,
====,,
0101,
0000,
& &
1011
1001
====
0010 = 02 = 2 = RESTE

En décimal, c'est '1559 divisé par 9 est de 173 avec un reste de 2'.

Bien que l'effet de chaque bit du message d'entrée sur le quotient
n'est pas importante, le reste sur 4 bits reçoit des coups de pied sur le
beaucoup de choses au cours du calcul, et si plus d'octets ont été ajouté à
le message (dividende) & #39 s valeur pourrait changer radicalement nouveau très
rapidement. C'est pourquoi la division des œuvres où plus n' & #39 t.

Dans le cas où vous & #39 re vous demandez-vous, à l'aide de ce 4 bits de somme de contrôle de la transmission de la
message devrait ressembler à ceci (en hexadécimal): 06172 (où le 0617
est le message et le 2 est la somme de contrôle). Le récepteur serait diviser
0617 de 9 et de voir si le reste était de 2.

4. Polynomical Arithmétique
& & & & & & & & & & & & -
Alors que la division de l'opération décrite dans la section précédente est très
très similaires à la somme de contrôle les systèmes appelés CRC régimes, la CRC
les régimes sont en fait un peu plus étrange, et nous avons besoin de plonger dans les
nombre étrange systèmes à comprendre.

Le mot que vous entendrez tout le temps lorsque vous traitez avec des CRC algorithmes
c'est le mot 'polynôme'. Un algorithme CRC sera dit
l'utilisation d'un polynôme, et CRC algorithmes en général on dit
d'exploitation à l'aide de polynômes de l'arithmétique. Qu'est-ce que cela signifie?

au Lieu de le diviseur, dividende (message), le quotient et le reste
(comme décrit dans la section précédente) être considéré comme positif
entiers, ils sont considérés comme des polynômes à coefficients binaires.
Ceci est fait par le traitement de chaque numéro de bit-chaîne dont les bits sont
les coefficients d'un polynôme. Par exemple, l'ordinaire numéro 23
(décimal) est de 17 (hex), et 10111 binaire et donc, il correspond à la
polynôme:

1*x^4 0*x^3 1*x^2 1*x^1 1*x^0

ou, plus simplement:

x^4 x^2 x^1 x^0

en Utilisant cette technique, le message, et le diviseur peut être représenté
comme les polynômes et nous pouvons faire de notre arithmétique, comme auparavant, à l'exception de
que maintenant c' & #39 s tous les gorgé de Xs. Par exemple, supposons que nous voulions
pour multiplier 1101 par 1011. On peut le faire simplement en multipliant le
polynômes:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0) = x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

À ce moment, d'obtenir la bonne réponse, nous avons à faire semblant que x est 2
et de propager binaire porte de la 3*x^3 rendement

x^7 x^3 x^2 x^1 x^0

& #39 s tout comme l'arithmétique ordinaire, sauf que la base est transparente
et est introduite dans tous les calculs explicitement à la place de
il y implicitement. Donc, ce que & #39 s the point?

Le point est que SI nous prétendons que nous N' & #39 T savoir ce que x est, nous POUVONS & #39 T
effectuer la porte. Nous n' & #39 t savoir que 3*x^3 est le même que x^4 x^3
parce que nous n' & #39 t savoir que x est 2. Dans cette véritable polynôme arithmétique
la relation entre tous les coefficients est inconnue et donc l'
les coefficients de chaque bloc de devenir effectivement fortement typé
les coefficients de x^2 sont effectivement d'un type différent de
les coefficients de x^3.

Avec les coefficients de chaque puissance, bien isolé, les mathématiciens
est venu avec toutes sortes de différents types de polynôme arithmétique
simplement en modifiant les règles sur la façon dont les coefficients de travail. De ces
les régimes, en particulier, est pertinente ici, et qui est un polynôme
arithmétique où les coefficients sont calculés MOD 2 et il n'y a pas de
porter tous les coefficients, doit être 0 ou 1 et les pas de porte sont
calculés. Ceci est appelé le 'polynôme arithmétique mod 2'. Ainsi,
pour revenir à l'exemple précédent:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0)
= x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

en Vertu de l'autre l'arithmétique, de la 3*x^3 terme a été propagés à l'aide de la
porter le mécanisme à l'aide de la connaissance que x=2. En vertu de 'polynôme
arithmétique mod 2', nous n' & #39 t savoir ce qu'est x, il y a pas de porte, et
tous les coefficients sont calculés au mod 2. Ainsi, le résultat
devient:

= x^6 x^5 x^4 x^3 x^2 x^1 x^0

Comme Knuth [Knuth81] dit (p.400):

'Le lecteur doit noter la similitude entre polynôme
l'arithmétique et de multiples précision arithmétique (Section 4.3.1), où
la base b est remplacé par x. La différence principale est que le
coefficient u_k de x^k dans le polynôme arithmétique porte peu ou pas
rapport à ses voisins les coefficients de x^{k-1} [x^{k 1}],
l'idée de la 'réalisation' d'un endroit à un autre est absent. En fait,
polynôme arithmétique modulo b est essentiellement identique à plusieurs
précision de l'arithmétique avec radix b, sauf que tous les porte sont
supprimé.'

Donc polynomical arithmétique mod 2 est juste arithmétique binaire mod 2
pas de porte. Alors que les polynômes de fournir des informations utiles machinerie mathématique dans
plus d'approches analytiques de la CRC et de l'erreur-correction des algorithmes, pour
l'application de l'exposition, ils ne donnent pas extra aperçu et quelques
de la charge et ont été jetés dans le reste de ce document
en faveur de la manipulation directe de l'arithmétique système
ils sont isomorphe: arithmétique binaire sans retenue.

5. Arithmétique binaire avec Pas de Porte
& & & & & & & & & & & & & & & & & &
Avoir rendu avec des polynômes, nous pouvons nous concentrer sur l'arithmétique réelle
le problème, qui est que tous les calculs arithmétiques effectuées au cours de la CRC
les calculs effectués en binaire avec pas de porte. Souvent c'est
appelé polynôme de l'arithmétique, mais comme je l'ai déclaré le reste de ce
document un polynôme zone libre, nous & #39 ll appeler ça du CRC arithmétique
à la place. Comme cette arithmétique est une partie essentielle de la CRC calculs, nous & #39 d
mieux de vous y habituer. Nous y voilà:

l'Ajout de deux nombres CRC arithmétique est la même que l'ajout de numéros
d'ordinaire arithmétique binaire sauf il n'y a pas de report. Cela signifie que
chaque paire de bits correspondants de déterminer le correspondant de bits de sortie
sans référence à tous les autres positions de bits. Par exemple:

10011011
11001010
& & & &
01010001
& & & &

Il y a seulement quatre cas, pour chaque position de bit:

0 0=0
0 1=1
1 0=1
1 1=0 (pas de report)

la Soustraction est identique:

10011011
-11001010
& & & &
01010001
& & & &

0-0=0
0-1=1 (enveloppant)
1-0=1
1-1=0

En fait, à la fois l'addition et la soustraction dans la convention de l'arithmétique est l'équivalent de
pour l'opération XOR, et l'opération XOR est son propre inverse. Ce
réduit efficacement les opérations de premier niveau de puissance
(addition, soustraction) pour une opération unique qui est son propre inverse.
C'est un très pratique de la propriété de l'arithmétique.

Par l'effondrement de l'addition et de la soustraction, l'arithmétique élimine toute
notion de grandeur au-delà de la puissance de son plus haut un peu. Alors qu'il
semble clair que 1010 est plus grand que 10, il n'est plus le cas
1010 peut être considéré comme supérieur à 1001. Pour voir cela, remarque
que vous pouvez obtenir à partir de 1010 1001 par ajout et soustraction de la
quantité:

1010 = 1010 0011
1010 = 1010 - 0011

Cela fait de l'absurdité de la notion d'ordre.

après Avoir défini plus, nous pouvons nous déplacer pour la multiplication et la division.
la Multiplication est absolument simple, soit la somme de la
le premier numéro, changé en conformité avec le deuxième nombre.

1101
x 1011
& &
1101
1101.
0000..
1101...
& & & -
1111111 Remarque: La somme des utilisations CRC plus
& & & -

la Division est un peu messier comme nous avons besoin de savoir quand 'un certain nombre va
dans un autre numéro. Pour ce faire, nous invoquons la faiblesse de la définition de
magnitude telle que définie plus haut: que X est supérieur ou égal à Y iff
la position de plus de 1 bit de X est supérieure ou égale à celle de la
position de plus de 1 bit de Y. Ici & #39 s entièrement travaillé à la division
(entaillé de [Tanenbaum81]).

1100001010
& & & & &
10011 ) 11010110110000
10011,,.,,....
& & -,,.,,....
10011,.,,....
10011,.,,....
& & -,.,,....
00001.,,....
00000.,,....
& & -.,,....
00010,,....
00000,,....
& & -,,....
00101,....
00000,....
& & -,....
01011....
00000....
& & -....
10110...
10011...
& & -...
01010..
00000..
& & -..
10100.
10011.
& & -.
01110
00000
& & -
1110 = Solde

& #39 s vraiment. Avant d'aller plus loin, cependant, il & #39 s digne de notre
tout en jouant avec cette arithmétique un peu pour s'y habituer.

- Nous & #39 ai déjà joué avec l'addition et la soustraction, en remarquant qu'ils
sont la même chose. Ici, cependant, nous devons noter que dans ce
l'arithmétique A 0=A et A-0=A. Cette évidente de la propriété est très utile
plus tard.

Dans le traitement avec le CRC de multiplication et de division, il & #39 s la peine d'obtenir un
impression pour les concepts de MULTIPLES et DIVISIBLE.

Si un nombre A est un multiple de B alors ce que cela signifie dans la CRC
l'arithmétique, c'est qu'il est possible de construire Un à partir de zéro par XORing
dans les différents quarts de B. Par exemple, si Un a été 0111010110 et B était de 11,
nous avons pu construire Un à partir de B, comme suit:

0111010110
= .......11.
....11....
...11.....
.11.......

Cependant, si A est 0111010111, il n'est pas possible de construire de
différents quarts de B (voyez-vous pourquoi? - voir plus loin), alors on dit que c'est
pas divisible par B dans la convention de l'arithmétique.

Ainsi, nous voyons que la CRC arithmétique est principalement sur les XORing particulier
les valeurs à différents décalage de décalages.

6. Entièrement Travaillé par Exemple
& & & & & & & & & & & & -
après Avoir défini CRC arithmétique, nous pouvons à présent cadre d'un calcul de CRC
tout simplement une division, parce que & #39 s tous il est! Cette section se remplit dans le
détails et donne un exemple.

Pour effectuer un calcul de CRC, nous avons besoin de choisir un diviseur. En maths
le marketing de parler le diviseur est appelé le 'polynôme générateur' ou
tout simplement le 'polynôme', et est un paramètre clé de toute CRC algorithme.
Il serait sans doute plus agréable à utiliser pour appeler le diviseur autre chose,
mais le poly parler est si profondément enracinée dans le domaine qu'il
désormais être source de confusion pour l'éviter. Comme compromis, nous nous référerons à la
CRC polynôme de la 'poly'. Il suffit de penser de ce nombre comme une sorte de
parrot. 'Bonjour poly!'

Vous pouvez choisir n'importe quelle poly et de venir avec un algorithme CRC. Cependant,
quelques polys sont mieux que d'autres, et donc il est sage de garder à l'
j'ai essayé un testées. Une autre section traite de cette question.

La largeur (position de plus de 1 bit) de la poly est très
important, car il domine l'ensemble du calcul. Généralement, la largeur de
16 ou 32 sont choisies de manière à simplifier la mise en oeuvre moderne
ordinateurs. La largeur d'un poly est le nombre de bit de position de la
bit plus élevé. Par exemple, la largeur de 10011 est 4, pas 5. Pour le
titre d'exemple, nous avons choisi un poly de 10011 (de la largeur W de 4).

après Avoir choisi un poly, nous pouvons procéder au calcul. C'est
tout simplement une division (CRC arithmétique) du message par le poly. L'
le seul truc, c'est que W zéro les bits sont ajoutés au message d'avant
CRC est calculé. Ainsi, nous avons:

message Original : 1101011011
Poly : 10011
Message après l'ajout W zéros : 11010110110000

Maintenant, nous avons simplement diviser l'augmentation du message par le poly à l'aide de la CRC
l'arithmétique. C'est la même division que avant:

1100001010 = Quotient (personne ne se soucie de le quotient)
& & & & &
10011 ) 11010110110000 = Augmentée message (1101011011 0000)
=Poly 10011,,.,,....
& & -,,.,,....
10011,.,,....
10011,.,,....
& & -,.,,....
00001.,,....
00000.,,....
& & -.,,....
00010,,....
00000,,....
& & -,,....
00101,....
00000,....
& & -,....
01011....
00000....
& & -....
10110...
10011...
& & -...
01010..
00000..
& & -..
10100.
10011.
& & -.
01110
00000
& & -
1110 = Reste = CHECKSUM!!!!

La division donne un quotient, qui nous jette à la poubelle, et le reste,
qui est le checksum calculé. Ceci termine le calcul.

Habituellement, la somme de contrôle est ensuite ajouté au message et le résultat
transmis. Dans ce cas, la transmission serait: 11010110111110.

À l'autre bout, le récepteur peut faire une de deux choses:

un. Séparer le message et la somme de contrôle. Calculer la somme de contrôle
le message (après l'ajout W zéros), et comparer les deux
les sommes de contrôle.

b. Somme de contrôle de l'ensemble du lot (sans ajout de zéros) et voir si il
en tant que zéro!

Ces deux options sont équivalentes. Toutefois, dans la prochaine section, nous
sera en supposant que l'option b, car il est légèrement mathématiquement
plus propre.

Un résumé de l'opération de la classe de CRC algorithmes:

1. Choisissez une largeur W, et un poly G (de largeur W).
2. Ajouter W à zéro les bits du message. Appelez cela M & #39 .
3. Diviser M & #39 par G à l'aide de la CRC de l'arithmétique. Le reste est la somme de contrôle.

& #39 s il y a tout pour elle.

7. Le choix d'Un Poly
& & & & & & & & &
le Choix d'un poly est un peu un art noir et le lecteur est renvoyé
[Tanenbaum81] (p.130-132), qui a très clairement la discussion de ce
question. Cette section vise simplement à mettre la peur de la mort en personne
qui tant que des jouets avec l'idée de faire leur propre poly. Si vous
& #39 t care about pourquoi un poly peut-être mieux que l'autre et juste
vous voulez savoir sur la haute-vitesse implémentations, choisissez l'une des
arithmétiquement son polys énumérés à la fin de cette section et passez
à la section suivante.

d'Abord noter que le message transmis T est un multiple de la poly.
Pour voir cela, notons que: 1) le dernier W bits de T est le reste après
en divisant l'augmentation (par des zéros en souviens plus) message du poly, et 2)
l'addition est la même que la soustraction afin d'ajouter le reste pousse le
valeur jusqu'à la prochaine plusieurs. Maintenant, notez que si la transmission de la
le message est corrompu dans la transmission que nous recevrons T E où E
est un vecteur d'erreur (et de CRC plus (c'est à dire XOR)). Lors de la réception de
ce message, le récepteur divise T E par G. T mod G est 0, (T, E)
mod G = E mod G. Ainsi, la capacité de la poly-nous choisir de catch
certains types d'erreurs sera déterminé par le jeu de multiples
de G, pour toute la corruption qui est un multiple de G ne soit pas détectée.
Notre tâche est alors de trouver des classes de G dont les multiples regardez aussi peu
comme le genre de bruit de ligne (qui sera de créer la corruptions)
possible. Alors laissez - & #39 s d'étudier les types de bruit sur la ligne, nous pouvons nous attendre.

SEUL les ERREURS sur les BITS: UN bit d'erreur signifie que E=1000...0000. Nous pouvons
assurez-vous que cette classe d'erreur est toujours détecté par faire en sorte que
G a au moins deux bits mis à 1. Tout multiple de G sera
construit à l'aide déplaçant et en ajoutant et il est impossible de
construire une valeur avec un seul bit par déplacement d'un ajout d'un
valeur avec plus d'un ensemble de bits, comme la fin de deux bits sera toujours
persist.

DEUX ERREURS sur les BITS: Pour détecter toutes les erreurs de forme 100...000100 000...
(c'est à dire E contient deux bits à 1) choisir un G qui n'ont pas de multiples
qui sont 11, 101, 1001, 10001, 100001, etc. Il n'est pas clair pour moi comment
on va le faire (je n' & #39 t avoir la pure mathématiques arrière-plan),
mais Tanenbaum nous assure que ces G n'existe pas, et la cites G avec 1 bits
(15,14,1) comme un exemple d'une G qui a remporté & #39 t fracture rien
moins de 1...1 ... est 32767 les zéros.

les ERREURS AVEC UN NOMBRE IMPAIR DE BITS: On peut attraper toutes les corruptions, où
E a un nombre impair de bits par le choix d'un G qui a un nombre pair de
bits. Pour voir cela, notons que 1) CRC multiplication est tout simplement XORing un
la valeur de la constante dans un registre à différents décalages, 2) XORing est tout simplement
un bit-flip fonctionnement, et 3) si vous XOR une valeur avec un même nombre de
bits dans un registre, l'étrangeté du nombre de bits à 1 dans le
inscrivez-vous reste invariant. Exemple: en Commençant par E=111, tentative de
retourner tous les trois bits à zéro par l'application répétée de l'XORing
11 à l'un des deux décalages (c'est à dire 'E=E XOR 011' et 'E=E XOR 110')
C'est près de isomorphe à la 'verre gobelets' partie de puzzle où
vous défiez quelqu'un flip trois gobelets par la répétition de l'
application de l'opération de retournement toutes les deux. Les plus populaires,
CRC polys contenir un nombre pair de bits à 1. (Note: Tanenbaum unis
plus précisément que toutes les erreurs avec un nombre impair de bits peut être
pris en rendant G un multiple de 11).

RAFALE d'ERREURS: UNE rafale d'erreur ressemble à E=000...000111...11110000...00.
C'est E se compose de tous les zéros, sauf pour une course de 1s quelque part
à l'intérieur. Cela peut être reformulée comme E=(10000...00)(1111111...111) où
il y a des z zéros dans la partie GAUCHE et n dans la partie DROITE. Pour
capture des erreurs de ce genre, il nous suffit de définir le bit le plus bas de G à 1.
de ce Fait, la GAUCHE ne peut pas être un facteur de G. Alors, tant que
G est plus large que le DROIT, l'erreur sera détectée. Voir Tanenbaum pour un
explication plus claire de ce que je & #39 m un peu floue sur ce point. Remarque:
Tanenbaum affirme que la probabilité d'un éclat de longueur supérieure
que W arriver par l'est (0.5)^W.

Cette conclut la section sur l'art de la sélection de polygones.

Certains populaire polys sont:
16 bits: (16,12,5,0) [X25 standard]
(16,15,2,0) [CRC-16']
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]

8. Un Simple CRC mise en Œuvre
& & & & & & & & & & & & & & & & & & & -
& #39 s la fin de la théorie, maintenant nous nous tournons vers les implémentations. Pour commencer
avec, nous examinons absolument droit-vers le bas-du-milieu ennuyeux
simple à faible vitesse de mise en œuvre qui n' & #39 t utiliser n'importe quelle vitesse
astuces en tout. Nous & #39 ll puis de les transformer en programme progessively jusqu'à ce que nous
jusqu'à la fin avec le compact de table-driven

Detection des erreurs (Crc

Detection des erreurs (Crc : Plusieurs milliers de conseils pour vous faciliter la vie.

UN GUIDE INDOLORE A l'ERREUR CRC ALGORITHMES de DETECTION

===================================================================
Cet article a ete mis sur le web par SPLat les Controles, les decideurs
de la SPLat gamme de microPLCs pour l'utilisation OEM.
SPLat est les mondes & #39 plus rentable microPLC.
De hors-the-shelf produits qui vous feront gagner plus que ce qu'elles coûtent, a
l'utilisateur personnalisee-automates programmables, SPLat est un de surprenantes nouvelles
mode de prise de commandes electroniques pour les machines dans des quantites
1 a 50 000 p.un.

Pour verifier SPLat copier et coller l'URL suivante dans votre navigateur
d'adresse ou d'emplacement de la fenetre:
http://splatco.com
===================================================================
l'Article est reproduit avec la permission du proprietaire du droit d'auteur. Profitez-en!
===================================================================

UN GUIDE INDOLORE A l'ERREUR CRC ALGORITHMES de DETECTION
==================================================
'Tout ce que vous vouliez savoir sur CRC algorithmes, mais ont peur
pour demander, de peur que les erreurs de votre comprehension peut etre detecte.'

Version : 3.
Date : 19 août 1993.
Auteur : Ross, N. Williams.
Net : [email protected].
FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
l'Entreprise : Rocksoft^tm Pty Ltd.
l'Escargot : 16 Lerwick Avenue, Hazelwood Parc 5066, en Australie.
Fax : 61 8 373-4911 (c/- entre-nœud Systems Pty Ltd).
Telephone : 61 8 379-9217 (10h a 10h Adelaïde, en Australie du temps).
Note : 'Rocksoft' est une marque de commerce de Rocksoft Pty Ltd, Australie.
Statut : Copyright (C) Ross Williams, 1993. Toutefois, l'autorisation est
accordees a faire et distribuer des copies conformes de ce
document a condition que ce bloc d'informations et le droit d'auteur
avis est inclus. Aussi, les modules de code C inclus
dans ce document sont entierement domaine public.
Merci : Merci a Jean-loup Gailly ([email protected]) et Mark Adler
([email protected]) qui a la fois la preuve de la lecture de ce document
et pris beaucoup de lentes ainsi que quelques gros bugs.

Table des Matieres
& & & & & & & & -
Abrege
1. Introduction: la Detection de l'Erreur
2. La Necessite Pour la Complexite
3. L'Idee de Base Derriere CRC Algorithmes
4. Polynomical Arithmetique
5. Arithmetique binaire avec Pas de Porte
6. Entierement Travaille par Exemple
7. Le choix d'Un Poly
8. Un Simple CRC mise en Œuvre
9. Une Table-Driven mise en Œuvre
10. Une legere Deformation de la Table-Driven mise en Œuvre
11. 'Reflechie' Table-Driven Implementations
12. 'Inverse' Polys
13. Valeurs initiale et Finale
14. La definition d'Algorithmes Absolument
15. Un Modele Parametre Pour le CRC Algorithmes
16. Un Catalogue de Jeux de parametres pour les Normes
17. Une Implementation de l'Algorithme de Modele
18. Rouler Votre Propre Table-Driven mise en Œuvre
19. Generation d'Une Table de Recherche
20. Resume
21. Corrections
A. Glossaire
B. les References
C. References que j'Ai Detecte Mais n'avez & #39 t Encore Voyante

Resume
& & & &
Ce document explique Crc (controle de Redondance Cyclique Codes) et leur
table-driven mises en œuvre dans le plein, la precision des details. Une grande partie de la
litterature sur CRCs, et en particulier sur leur table-driven
implementations, est un peu obscur (ou du moins semble donc, pour moi).
Ce document est une tentative pour donner une idee claire et simple no-nonsense
explication de la Cdc et de preciser tous les details de la
fonctionnement de leur haute vitesse implementations. En plus de cela,
ce document presente un modele parametre CRC algorithme appele la
'Rocksoft^tm Modele CRC Algorithme'. Le modele de l'algorithme peut etre
parametree a se comporter comme la plupart de la CRC applications,
et agit ainsi comme une bonne reference pour la description des algorithmes speciaux.
a faible vitesse de mise en œuvre du modele CRC algorithme est fourni dans
le langage de programmation C. Enfin il y a une section donnant deux formes
de haute vitesse de la table par les implementations et fournir un programme
qui genere CRC tables de recherche.

1. Introduction: la Detection de l'Erreur
& & & & & & & & & & & & & & & &
Le but d'une erreur technique de detection est de permettre au recepteur d'un
message transmis par un bruyant (erreur-l'introduction) de canal
determiner si le message a ete endommage. Pour ce faire, le
emetteur construit une valeur (appelee ' somme de controle) qui est une fonction
du message, et l'ajoute au message. Le recepteur peut alors
utiliser la meme fonction pour calculer la somme de controle de la
message et de le comparer avec les joints en annexe de la somme de controle pour voir si le
le message a ete correctement reçu. Par exemple, si nous avons choisi une somme de controle
fonction qui etait tout simplement la somme des octets du message mod 256
(c'est a dire modulo 256), alors il peut aller quelque chose comme suit. Tous les numeros
sont en decimal.

Message : 6 23 4
Message avec la somme de controle : 6 23 4 33
Message apres transmission : 6 27 4 33

ci-dessus, le deuxieme octet du message a ete endommage du 23 au
27 par le canal de communication. Cependant, le recepteur peut detecter
cela en comparant la transmission de la somme de controle (33) avec l'ordinateur
somme de controle de 37 (6 27 4). Si la somme de controle est endommage, un
correctement transmis le message peut etre identifie a tort comme une
qui est corrompue. Toutefois, c'est sûr, a cote de l'echec. Un dangereux cote
defaillance se produit lorsque le message et/ou de la somme de controle est endommage dans un
maniere que les resultats d'une transmission qui est d'une coherence interne.
Malheureusement, cette possibilite est totalement inevitable et le meilleur,
qui peut etre fait est de reduire sa probabilite par l'augmentation de la
quantite d'informations dans la somme de controle (par exemple, l'elargissement de la somme de controle
un octet deux octets).

Autre erreur de detection il existe des techniques qui impliquent l'execution complexe
des transformations sur le message pour l'injecter avec redondant
informations. Cependant, ce document ne traite que de la CRC algorithmes,
qui entrent dans la classe des algorithmes de detection d'erreur qui sortent de l'
donnees intact, et ajouter une somme de controle sur la fin. c'est a dire:

2. La Necessite Pour la Complexite
& & & & & & & & & & & & &
Dans l'exemple de la somme de controle dans la section precedente, nous avons vu comment un
message endommage a ete detectee a l'aide d'un algorithme de checksum simplement
sommes les octets du message mod 256:

Message : 6 23 4
Message avec la somme de controle : 6 23 4 33
Message apres transmission : 6 27 4 33

Un probleme avec cet algorithme est qu'il est trop simple. Si un certain nombre de
au hasard, des alterations se produisent, il y a 1 a 256 chance qu'ils
ne pas etre detecte. Par exemple:

Message : 6 23 4
Message avec la somme de controle : 6 23 4 33
Message apres transmission : 8 20 5 33

Pour renforcer la somme de controle, nous pourrions changer d'un 8-bit registre de
un registre 16 bits (c'est a dire la somme des octets d'un mod 65536 au mod 256) donc,
comme, apparemment a reduire la probabilite de defaillance de 1/256
1/65536. Alors que fondamentalement une bonne idee, il echoue dans ce cas, parce que
la formule utilisee n'est pas assez 'aleatoire' avec une simple sommation
formule, chaque octets entrants touche environ d'un seul octet de la
sommation de s'inscrire n'importe comment, il est. Par exemple, dans la seconde
l'exemple ci-dessus, la synthese registre pourrait etre un Megaoctet de large, et l'
l'erreur serait encore passer inaperçus. Ce probleme ne peut etre resolu que par des
remplacement de la simple sommation formule avec une version plus sophistiquee de la formule
que provoque chaque octets entrants ont un effet sur l'ensemble de la
somme de controle de registre.

Ainsi, nous voyons qu'au moins deux aspects sont necessaires pour former un solide
somme de controle de la fonction:

LARGEUR: la largeur de registre assez large pour fournir un faible a priori
probabilite de defaillance (par exemple, 32-bits donne un 1/2^32 chance
de panne).

le CHAOS: UNE formule qui donne a chacune d'octets d'entree le potentiel de changement
n'importe quel nombre de bits dans le registre.

Note: Le terme 'somme de controle' a ete probablement utilise pour decrire debut
en additionnant les formules, mais il a pris un sens plus general
englobant des algorithmes plus sophistiques tels que la CDE. L'
CRC algorithmes decrits satisfaire a la deuxieme condition, tres bien,
et peut etre configure pour fonctionner avec une variete de somme de controle largeurs.

3. L'Idee de Base Derriere CRC Algorithmes
& & & & & & & & & & & & & & & & & & & -
Ou pourrions-nous aller dans notre recherche d'une fonction plus complexe
sommation? Toutes sortes de regimes viennent a l'esprit. Nous avons pu construire
tables a l'aide des chiffres de pi, ou de hachage de chaque octets entrants avec tous les
octets dans le registre. On pourrait meme tenir un grand livre de telephone
sur la ligne, et utiliser chaque octets entrants combine avec le registre octets
pour indexer un nouveau numero de telephone qui serait la prochaine valeur de registre.
Les possibilites sont infinies.

Cependant, nous n'avons pas besoin d'aller si loin la prochaine arithmetique etape
suffit. Tandis que l'addition est clairement pas assez forte pour former un
efficace de la somme de controle, il s'avere que la division est, aussi longtemps que le
diviseur est a peu pres aussi large que la somme de controle de registre.

L'idee de base de la convention des algorithmes est de simplement traiter le message comme un
enorme nombre binaire, de la diviser par un autre fixe nombre binaire,
et pour faire le reste de cette division de la somme de controle. Lors de la
la reception du message, le recepteur peut effectuer la meme division, et
comparer le reste avec le 'checksum' (transmis reste).

Exemple: Supposons que le message se composait de deux octets (6,23)
dans l'exemple precedent. Ceux-ci peuvent etre consideres comme les hexadecimal
numero de 0617 qui peut etre considere comme le nombre binaire
0000-0110-0001-0111. Supposons que nous avons d'utiliser un registre de total de controle d'un octet
large et utiliser une constante diviseur de 1001, alors la somme de controle est la
reste apres 0000-0110-0001-0111 est divise par 1001. Alors que dans ce
cas, ce calcul ne peut evidemment etre effectuees a l'aide de commun
jardin divers registres 32 bits, dans le cas general, c'est salissant. Donc,
au lieu de cela, nous & #39 ll faire la division a l'aide de bonnes & -#39 ol division longue qui vous
appris a l'ecole (vous vous souvenez?). Sauf que cette fois, c' & #39 s en binaire:

En decimal, c'est '1559 divise par 9 est de 173 avec un reste de 2'.

Bien que l'effet de chaque bit du message d'entree sur le quotient
n'est pas importante, le reste sur 4 bits reçoit des coups de pied sur le
beaucoup de choses au cours du calcul, et si plus d'octets ont ete ajoute a
le message (dividende) & #39 s valeur pourrait changer radicalement nouveau tres
rapidement. C'est pourquoi la division des œuvres ou plus n' & #39 t.

Dans le cas ou vous & #39 re vous demandez-vous, a l'aide de ce 4 bits de somme de controle de la transmission de la
message devrait ressembler a ceci (en hexadecimal): 06172 (ou le 0617
est le message et le 2 est la somme de controle). Le recepteur serait diviser
0617 de 9 et de voir si le reste etait de 2.

4. Polynomical Arithmetique
& & & & & & & & & & & & -
Alors que la division de l'operation decrite dans la section precedente est tres
tres similaires a la somme de controle les systemes appeles CRC regimes, la CRC
les regimes sont en fait un peu plus etrange, et nous avons besoin de plonger dans les
nombre etrange systemes a comprendre.

Le mot que vous entendrez tout le temps lorsque vous traitez avec des CRC algorithmes
c'est le mot 'polynome'. Un algorithme CRC sera dit
l'utilisation d'un polynome, et CRC algorithmes en general on dit
d'exploitation a l'aide de polynomes de l'arithmetique. Qu'est-ce que cela signifie?

au Lieu de le diviseur, dividende (message), le quotient et le reste
(comme decrit dans la section precedente) etre considere comme positif
entiers, ils sont consideres comme des polynomes a coefficients binaires.
Ceci est fait par le traitement de chaque numero de bit-chaîne dont les bits sont
les coefficients d'un polynome. Par exemple, l'ordinaire numero 23
(decimal) est de 17 (hex), et 10111 binaire et donc, il correspond a la
polynome:

1*x^4 0*x^3 1*x^2 1*x^1 1*x^0

ou, plus simplement:

x^4 x^2 x^1 x^0

en Utilisant cette technique, le message, et le diviseur peut etre represente
comme les polynomes et nous pouvons faire de notre arithmetique, comme auparavant, a l'exception de
que maintenant c' & #39 s tous les gorge de Xs. Par exemple, supposons que nous voulions
pour multiplier 1101 par 1011. On peut le faire simplement en multipliant le
polynomes:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0) = x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

A ce moment, d'obtenir la bonne reponse, nous avons a faire semblant que x est 2
et de propager binaire porte de la 3*x^3 rendement

x^7 x^3 x^2 x^1 x^0

& #39 s tout comme l'arithmetique ordinaire, sauf que la base est transparente
et est introduite dans tous les calculs explicitement a la place de
il y implicitement. Donc, ce que & #39 s the point?

Le point est que SI nous pretendons que nous N' & #39 T savoir ce que x est, nous POUVONS & #39 T
effectuer la porte. Nous n' & #39 t savoir que 3*x^3 est le meme que x^4 x^3
parce que nous n' & #39 t savoir que x est 2. Dans cette veritable polynome arithmetique
la relation entre tous les coefficients est inconnue et donc l'
les coefficients de chaque bloc de devenir effectivement fortement type
les coefficients de x^2 sont effectivement d'un type different de
les coefficients de x^3.

Avec les coefficients de chaque puissance, bien isole, les mathematiciens
est venu avec toutes sortes de differents types de polynome arithmetique
simplement en modifiant les regles sur la façon dont les coefficients de travail. De ces
les regimes, en particulier, est pertinente ici, et qui est un polynome
arithmetique ou les coefficients sont calcules MOD 2 et il n'y a pas de
porter tous les coefficients, doit etre 0 ou 1 et les pas de porte sont
calcules. Ceci est appele le 'polynome arithmetique mod 2'. Ainsi,
pour revenir a l'exemple precedent:

(x^3 x^2 x^0)(x^3 x^1 x^0)
= (x^6 x^4 x^3
x^5 x^3 x^2
x^3 x^1 x^0)
= x^6 x^5 x^4 3*x^3 x^2 x^1 x^0

en Vertu de l'autre l'arithmetique, de la 3*x^3 terme a ete propages a l'aide de la
porter le mecanisme a l'aide de la connaissance que x=2. En vertu de 'polynome
arithmetique mod 2', nous n' & #39 t savoir ce qu'est x, il y a pas de porte, et
tous les coefficients sont calcules au mod 2. Ainsi, le resultat
devient:

= x^6 x^5 x^4 x^3 x^2 x^1 x^0

Comme Knuth [Knuth81] dit (p.400):

'Le lecteur doit noter la similitude entre polynome
l'arithmetique et de multiples precision arithmetique (Section 4.3.1), ou
la base b est remplace par x. La difference principale est que le
coefficient u_k de x^k dans le polynome arithmetique porte peu ou pas
rapport a ses voisins les coefficients de x^{k-1} [x^{k 1}],
l'idee de la 'realisation' d'un endroit a un autre est absent. En fait,
polynome arithmetique modulo b est essentiellement identique a plusieurs
precision de l'arithmetique avec radix b, sauf que tous les porte sont
supprime.'

Donc polynomical arithmetique mod 2 est juste arithmetique binaire mod 2
pas de porte. Alors que les polynomes de fournir des informations utiles machinerie mathematique dans
plus d'approches analytiques de la CRC et de l'erreur-correction des algorithmes, pour
l'application de l'exposition, ils ne donnent pas extra aperçu et quelques
de la charge et ont ete jetes dans le reste de ce document
en faveur de la manipulation directe de l'arithmetique systeme
ils sont isomorphe: arithmetique binaire sans retenue.

5. Arithmetique binaire avec Pas de Porte
& & & & & & & & & & & & & & & & & &
Avoir rendu avec des polynomes, nous pouvons nous concentrer sur l'arithmetique reelle
le probleme, qui est que tous les calculs arithmetiques effectuees au cours de la CRC
les calculs effectues en binaire avec pas de porte. Souvent c'est
appele polynome de l'arithmetique, mais comme je l'ai declare le reste de ce
document un polynome zone libre, nous & #39 ll appeler ça du CRC arithmetique
a la place. Comme cette arithmetique est une partie essentielle de la CRC calculs, nous & #39 d
mieux de vous y habituer. Nous y voila:

l'Ajout de deux nombres CRC arithmetique est la meme que l'ajout de numeros
d'ordinaire arithmetique binaire sauf il n'y a pas de report. Cela signifie que
chaque paire de bits correspondants de determiner le correspondant de bits de sortie
sans reference a tous les autres positions de bits. Par exemple:

10011011
11001010
& & & &
01010001
& & & &

Il y a seulement quatre cas, pour chaque position de bit:

0 0=0
0 1=1
1 0=1
1 1=0 (pas de report)

la Soustraction est identique:

10011011
-11001010
& & & &
01010001
& & & &

0-0=0
0-1=1 (enveloppant)
1-0=1
1-1=0

En fait, a la fois l'addition et la soustraction dans la convention de l'arithmetique est l'equivalent de
pour l'operation XOR, et l'operation XOR est son propre inverse. Ce
reduit efficacement les operations de premier niveau de puissance
(addition, soustraction) pour une operation unique qui est son propre inverse.
C'est un tres pratique de la propriete de l'arithmetique.

Par l'effondrement de l'addition et de la soustraction, l'arithmetique elimine toute
notion de grandeur au-dela de la puissance de son plus haut un peu. Alors qu'il
semble clair que 1010 est plus grand que 10, il n'est plus le cas
1010 peut etre considere comme superieur a 1001. Pour voir cela, remarque
que vous pouvez obtenir a partir de 1010 1001 par ajout et soustraction de la
quantite:

1010 = 1010 0011
1010 = 1010 - 0011

Cela fait de l'absurdite de la notion d'ordre.

apres Avoir defini plus, nous pouvons nous deplacer pour la multiplication et la division.
la Multiplication est absolument simple, soit la somme de la
le premier numero, change en conformite avec le deuxieme nombre.

1101
x 1011
& &
1101
1101.
0000..
1101...
& & & -
1111111 Remarque: La somme des utilisations CRC plus
& & & -

la Division est un peu messier comme nous avons besoin de savoir quand 'un certain nombre va
dans un autre numero. Pour ce faire, nous invoquons la faiblesse de la definition de
magnitude telle que definie plus haut: que X est superieur ou egal a Y iff
la position de plus de 1 bit de X est superieure ou egale a celle de la
position de plus de 1 bit de Y. Ici & #39 s entierement travaille a la division
(entaille de [Tanenbaum81]).

& #39 s vraiment. Avant d'aller plus loin, cependant, il & #39 s digne de notre
tout en jouant avec cette arithmetique un peu pour s'y habituer.

- Nous & #39 ai deja joue avec l'addition et la soustraction, en remarquant qu'ils
sont la meme chose. Ici, cependant, nous devons noter que dans ce
l'arithmetique A 0=A et A-0=A. Cette evidente de la propriete est tres utile
plus tard.

Dans le traitement avec le CRC de multiplication et de division, il & #39 s la peine d'obtenir un
impression pour les concepts de MULTIPLES et DIVISIBLE.

Si un nombre A est un multiple de B alors ce que cela signifie dans la CRC
l'arithmetique, c'est qu'il est possible de construire Un a partir de zero par XORing
dans les differents quarts de B. Par exemple, si Un a ete 0111010110 et B etait de 11,
nous avons pu construire Un a partir de B, comme suit:

0111010110
= .......11.
....11....
...11.....
.11.......

Cependant, si A est 0111010111, il n'est pas possible de construire de
differents quarts de B (voyez-vous pourquoi? - voir plus loin), alors on dit que c'est
pas divisible par B dans la convention de l'arithmetique.

Ainsi, nous voyons que la CRC arithmetique est principalement sur les XORing particulier
les valeurs a differents decalage de decalages.

6. Entierement Travaille par Exemple
& & & & & & & & & & & & -
apres Avoir defini CRC arithmetique, nous pouvons a present cadre d'un calcul de CRC
tout simplement une division, parce que & #39 s tous il est! Cette section se remplit dans le
details et donne un exemple.

Pour effectuer un calcul de CRC, nous avons besoin de choisir un diviseur. En maths
le marketing de parler le diviseur est appele le 'polynome generateur' ou
tout simplement le 'polynome', et est un parametre cle de toute CRC algorithme.
Il serait sans doute plus agreable a utiliser pour appeler le diviseur autre chose,
mais le poly parler est si profondement enracinee dans le domaine qu'il
desormais etre source de confusion pour l'eviter. Comme compromis, nous nous refererons a la
CRC polynome de la 'poly'. Il suffit de penser de ce nombre comme une sorte de
parrot. 'Bonjour poly!'

Vous pouvez choisir n'importe quelle poly et de venir avec un algorithme CRC. Cependant,
quelques polys sont mieux que d'autres, et donc il est sage de garder a l'
j'ai essaye un testees. Une autre section traite de cette question.

La largeur (position de plus de 1 bit) de la poly est tres
important, car il domine l'ensemble du calcul. Generalement, la largeur de
16 ou 32 sont choisies de maniere a simplifier la mise en oeuvre moderne
ordinateurs. La largeur d'un poly est le nombre de bit de position de la
bit plus eleve. Par exemple, la largeur de 10011 est 4, pas 5. Pour le
titre d'exemple, nous avons choisi un poly de 10011 (de la largeur W de 4).

apres Avoir choisi un poly, nous pouvons proceder au calcul. C'est
tout simplement une division (CRC arithmetique) du message par le poly. L'
le seul truc, c'est que W zero les bits sont ajoutes au message d'avant
CRC est calcule. Ainsi, nous avons:

message Original : 1101011011
Poly : 10011
Message apres l'ajout W zeros : 11010110110000

Maintenant, nous avons simplement diviser l'augmentation du message par le poly a l'aide de la CRC
l'arithmetique. C'est la meme division que avant:

1100001010 = Quotient (personne ne se soucie de le quotient)
& & & & &
10011 ) 11010110110000 = Augmentee message (1101011011 0000)
=Poly 10011,,.,,....
& & -,,.,,....
10011,.,,....
10011,.,,....
& & -,.,,....
00001.,,....
00000.,,....
& & -.,,....
00010,,....
00000,,....
& & -,,....
00101,....
00000,....
& & -,....
01011....
00000....
& & -....
10110...
10011...
& & -...
01010..
00000..
& & -..
10100.
10011.
& & -.
01110
00000
& & -
1110 = Reste = CHECKSUM!!!!

La division donne un quotient, qui nous jette a la poubelle, et le reste,
qui est le checksum calcule. Ceci termine le calcul.

Habituellement, la somme de controle est ensuite ajoute au message et le resultat
transmis. Dans ce cas, la transmission serait: 11010110111110.

A l'autre bout, le recepteur peut faire une de deux choses:

un. Separer le message et la somme de controle. Calculer la somme de controle
le message (apres l'ajout W zeros), et comparer les deux
les sommes de controle.

b. Somme de controle de l'ensemble du lot (sans ajout de zeros) et voir si il
en tant que zero!

Ces deux options sont equivalentes. Toutefois, dans la prochaine section, nous
sera en supposant que l'option b, car il est legerement mathematiquement
plus propre.

Un resume de l'operation de la classe de CRC algorithmes:

1. Choisissez une largeur W, et un poly G (de largeur W).
2. Ajouter W a zero les bits du message. Appelez cela M & #39 .
3. Diviser M & #39 par G a l'aide de la CRC de l'arithmetique. Le reste est la somme de controle.

& #39 s il y a tout pour elle.

7. Le choix d'Un Poly
& & & & & & & & &
le Choix d'un poly est un peu un art noir et le lecteur est renvoye
[Tanenbaum81] (p.130-132), qui a tres clairement la discussion de ce
question. Cette section vise simplement a mettre la peur de la mort en personne
qui tant que des jouets avec l'idee de faire leur propre poly. Si vous
& #39 t care about pourquoi un poly peut-etre mieux que l'autre et juste
vous voulez savoir sur la haute-vitesse implementations, choisissez l'une des
arithmetiquement son polys enumeres a la fin de cette section et passez
a la section suivante.

d'Abord noter que le message transmis T est un multiple de la poly.
Pour voir cela, notons que: 1) le dernier W bits de T est le reste apres
en divisant l'augmentation (par des zeros en souviens plus) message du poly, et 2)
l'addition est la meme que la soustraction afin d'ajouter le reste pousse le
valeur jusqu'a la prochaine plusieurs. Maintenant, notez que si la transmission de la
le message est corrompu dans la transmission que nous recevrons T E ou E
est un vecteur d'erreur (et de CRC plus (c'est a dire XOR)). Lors de la reception de
ce message, le recepteur divise T E par G. T mod G est 0, (T, E)
mod G = E mod G. Ainsi, la capacite de la poly-nous choisir de catch
certains types d'erreurs sera determine par le jeu de multiples
de G, pour toute la corruption qui est un multiple de G ne soit pas detectee.
Notre tache est alors de trouver des classes de G dont les multiples regardez aussi peu
comme le genre de bruit de ligne (qui sera de creer la corruptions)
possible. Alors laissez - & #39 s d'etudier les types de bruit sur la ligne, nous pouvons nous attendre.

SEUL les ERREURS sur les BITS: UN bit d'erreur signifie que E=1000...0000. Nous pouvons
assurez-vous que cette classe d'erreur est toujours detecte par faire en sorte que
G a au moins deux bits mis a 1. Tout multiple de G sera
construit a l'aide deplaçant et en ajoutant et il est impossible de
construire une valeur avec un seul bit par deplacement d'un ajout d'un
valeur avec plus d'un ensemble de bits, comme la fin de deux bits sera toujours
persist.

DEUX ERREURS sur les BITS: Pour detecter toutes les erreurs de forme 100...000100 000...
(c'est a dire E contient deux bits a 1) choisir un G qui n'ont pas de multiples
qui sont 11, 101, 1001, 10001, 100001, etc. Il n'est pas clair pour moi comment
on va le faire (je n' & #39 t avoir la pure mathematiques arriere-plan),
mais Tanenbaum nous assure que ces G n'existe pas, et la cites G avec 1 bits
(15,14,1) comme un exemple d'une G qui a remporte & #39 t fracture rien
moins de 1...1 ... est 32767 les zeros.

les ERREURS AVEC UN NOMBRE IMPAIR DE BITS: On peut attraper toutes les corruptions, ou
E a un nombre impair de bits par le choix d'un G qui a un nombre pair de
bits. Pour voir cela, notons que 1) CRC multiplication est tout simplement XORing un
la valeur de la constante dans un registre a differents decalages, 2) XORing est tout simplement
un bit-flip fonctionnement, et 3) si vous XOR une valeur avec un meme nombre de
bits dans un registre, l'etrangete du nombre de bits a 1 dans le
inscrivez-vous reste invariant. Exemple: en Commençant par E=111, tentative de
retourner tous les trois bits a zero par l'application repetee de l'XORing
11 a l'un des deux decalages (c'est a dire 'E=E XOR 011' et 'E=E XOR 110')
C'est pres de isomorphe a la 'verre gobelets' partie de puzzle ou
vous defiez quelqu'un flip trois gobelets par la repetition de l'
application de l'operation de retournement toutes les deux. Les plus populaires,
CRC polys contenir un nombre pair de bits a 1. (Note: Tanenbaum unis
plus precisement que toutes les erreurs avec un nombre impair de bits peut etre
pris en rendant G un multiple de 11).

RAFALE d'ERREURS: UNE rafale d'erreur ressemble a E=000...000111...11110000...00.
C'est E se compose de tous les zeros, sauf pour une course de 1s quelque part
a l'interieur. Cela peut etre reformulee comme E=(10000...00)(1111111...111) ou
il y a des z zeros dans la partie GAUCHE et n dans la partie DROITE. Pour
capture des erreurs de ce genre, il nous suffit de definir le bit le plus bas de G a 1.
de ce Fait, la GAUCHE ne peut pas etre un facteur de G. Alors, tant que
G est plus large que le DROIT, l'erreur sera detectee. Voir Tanenbaum pour un
explication plus claire de ce que je & #39 m un peu floue sur ce point. Remarque:
Tanenbaum affirme que la probabilite d'un eclat de longueur superieure
que W arriver par l'est (0.5)^W.

Cette conclut la section sur l'art de la selection de polygones.

Certains populaire polys sont:
16 bits: (16,12,5,0) [X25 standard]
(16,15,2,0) [CRC-16']
32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]

8. Un Simple CRC mise en Œuvre
& & & & & & & & & & & & & & & & & & & -
& #39 s la fin de la theorie, maintenant nous nous tournons vers les implementations. Pour commencer
avec, nous examinons absolument droit-vers le bas-du-milieu ennuyeux
simple a faible vitesse de mise en œuvre qui n' & #39 t utiliser n'importe quelle vitesse
astuces en tout. Nous & #39 ll puis de les transformer en programme progessively jusqu'a ce que nous
jusqu'a la fin avec le compact de table-driven