CRC-Fehler-Erkennung

CRC-Fehler-Erkennung

CRC-Fehler-Erkennung : Mehreren tausend Tipps, um Ihr Leben einfacher machen.

EINE SCHMERZLOSE ANLEITUNG ZUR CRC ERROR DETECTION-ALGORITHMEN

===================================================================
Dieser Artikel wurde im Web von SPLat-Steuerelementen, Entscheidungsträger gelegt
die SPLat-Palette von MicroPLCs für OEM verwenden.
SPLat Welten ist den meisten kostengünstige MicroPLC.
Handelsübliche Produkte, die Sie speichern mehr als sie Kosten zu
individuelle Benutzer-programmierbare Steuerungen, SPLat ist eine verblüffende neu
Voraussetzung dafür, dass elektronische Steuerungen für Maschinen in Mengen von
1 zu 50.000 p.a.

Auschecken SPLat kopieren und fügen die folgende URL in Ihren browser
Ort oder Adresse-Fenster:
https://splatco.com
===================================================================
Artikel reproduziert mit Erlaubnis des copyright-Inhabers. Genießen Sie!
===================================================================

EINE SCHMERZLOSE ANLEITUNG ZUR CRC ERROR DETECTION-ALGORITHMEN
==================================================
'Everything you wanted to know about CRC Algorithmen, aber wagten
um zu Fragen, möglicherweise aus Angst, dass Störungen in Ihrem Verständnis erkannt.'

Version: 3.
Datum: 19. August 1993.
Autor: Ross N. Williams.
NET: [email protected].
FTP: ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
Firma: Rocksoft ^ tm Pty Ltd.
Schnecke: 16 Lerwick Avenue, Hazelwood Park 5066, Australien.
Fax: + 61 8 373-4911 (C/Internodium Systems Pty Ltd).
Telefon: + 61 8 379-9217 (10:00 bis 22:00 Adelaide Australien-Zeit).
Hinweis: 'Rocksoft' ist ein Warenzeichen von Rocksoft Pty Ltd, Australien.
Status: Copyright (C) Ross Williams, 1993. Allerdings ist die Berechtigung
gewährt damit und wortwörtliche Kopien davon verteilen
Dokument zur Verfügung gestellt, die diesem Informationsblock und copyright
Bekanntmachung ist enthalten. Auch C Code enthaltenen Module
in diesem Dokument sind voll Public Domain.
Vielen Dank: Dank (als [email protected]) Jean-Loup Gailly und Mark Adler
(als [email protected]), die beide Beweis dieses Dokument lesen
und nahm sich viel Nissen sowie einige große Dicke Fehler.

Inhaltsverzeichnis
-----------------
Abstrakt
1. Einleitung: Fehlererkennung
2. die Notwendigkeit der Komplexität
3. die Grundidee hinter CRC Algorithmen
4. Polynomical-Arithmetik
(5) binäre Arithmetik mit keine trägt
6. ein voll Berechnungsbeispiel
7. Wahl einer Poly
8. eine unkomplizierte CRC Implementierung
9. eine tabellengesteuerte Implementierung
10. eine leicht entstellte tabellengesteuerten Umsetzung
11. 'wider' tabellengesteuerten Implementierungen
12. 'umgekehrte' Polys
13. die Anfangs-und Endwert
14. Algorithmen absolut definieren.
15. eine parametrisierte Modell für CRC Algorithmen
16. ein Katalog der Parametersätze für Standards
17. eine Implementierung des Algorithmus Modell
18. eine eigene Implementierung tabellengesteuerten roll
19. eine Lookup-Tabelle generieren
20. Zusammenfassung
21. Korrekturen
A. Glossar
B. Referenzen
C. Verweise, die ich erkannt habe, aber haben nicht noch gesichtet

Abstrakt
--------
Dieses Dokument erklärt CRCs (zyklische Redundanz-Codes) und ihre
tabellengesteuerte Implementierungen im vollständigen, genauen Detail. Viel von der
Literatur von CRCs und insbesondere über ihre tabellengesteuerten
Implementierungen, ein wenig undurchsichtig ist (oder scheint so zumindest für mich).
Dieses Dokument ist ein Versuch, eine klare und einfache geradlinige bieten
Erklärung der CRCs und jedes Detail absolut festzunageln der
Betrieb ihrer High-Speed-Implementierungen. Darüber hinaus
Dieses Dokument präsentiert einen parametrisierte Model CRC-Algorithmus als die
'Rocksoft ^ tm Model CRC Algorithm'. Der Modell-Algorithmus kann sein
parametrisiert, um Verhalten wie die meisten der CRC-Implementierungen rund um,
und so dient als eine gute Referenz für die Beschreibung von bestimmter Algorithms.
Eine langsame Implementierung des Model CRC-Algorithmus wird in bereitgestellt.
die Programmiersprache C. Schließlich gibt es einen Abschnitt, geben zwei Formen
der High-Speed-Tabelle getrieben, Implementierungen, sowie zum Bereitstellen eines Programms
Das erzeugt CRC-Lookup-Tabellen.

1. Einleitung: Fehlererkennung
--------------------------------
Eine Fehler-Erkennung-Technik soll den Empfänger ermöglichen eine
Nachricht über einen laut (Fehler-Einführung) Kanal zu übertragen
bestimmen Sie, ob die Nachricht beschädigt wurde. Dazu die
Sender erzeugt einen Wert (eine Prüfsumme genannt), der eine Funktion ist
der Nachricht und an die Nachricht angehängt. Der Empfänger kann dann
Verwenden Sie die gleiche Funktion, um die Berechnung der Prüfsumme der empfangenen
Nachricht und vergleichen Sie es mit der angefügten Prüfsumme zu sehen, ob die
Nachricht wurde korrekt empfangen. Zum Beispiel, wenn wir wählten eine Prüfsumme
Funktion, das war einfach die Summe der Bytes in der Nachricht mod 256
(d.h. modulo 256) könnte es etwas wie folgt fahren. Alle Zahlen
sind im Dezimalformat.

Meldung: 6-23-4
Nachricht mit Prüfsumme: 6 23 4 33
Meldung nach der Übertragung: 6 27 4 33

In den oben genannten war das zweite Byte der Nachricht von 23 bis beschädigt.
27 von des Kommunikationskanals. Jedoch kann der Empfänger erkennen
dies durch den Vergleich der übertragenen Prüfsumme (33) mit dem computer
Prüfsumme von 37 (6 + 27 + 4). Wenn die Prüfsumme selbst beschädigt ist, eine
korrekt übertragenen Nachricht könnte fälschlicherweise als eine
beschädigt ein. Dies ist jedoch ein Tresor-Seite-Fehler. Eine gefährliche Seite
Fehler auftritt, wo die Nachricht und/oder Prüfsumme ist beschädigt, einer
Weise, die Ergebnisse in einer Übertragung, die intern konsistent ist.
Leider ist diese Möglichkeit nicht völlig zu vermeiden und die besten
gemacht werden kann ist seine Wahrscheinlichkeit minimieren durch eine Erhöhung der
Menge an Informationen in die Prüfsumme (z. B. Erweiterung der Prüfsumme aus
ein Byte auf zwei Byte).

Andere Fehler Erkennungstechniken vorhanden sind, bei denen komplexe durchführen
Transformationen auf die Nachricht, um es mit redundanten injizieren
Informationen. Dieses Dokument behandelt jedoch nur CRC Algorithmen,
die fallen in die Klasse der Fehler Algorithmen, die lassen die
Daten erhalten und eine Prüfsumme am Ende anfügen. d.h.:

2. die Notwendigkeit der Komplexität
--------------------------
Im Beispiel im vorherigen Abschnitt Prüfsumme, sahen wir wie ein
beschädigte Nachricht wurde anhand eines Prüfsummenalgorithmus erkannt, die einfach
Summen die Bytes in der Nachricht mod 256:

Meldung: 6-23-4
Nachricht mit Prüfsumme: 6 23 4 33
Meldung nach der Übertragung: 6 27 4 33

Ein Problem mit diesem Algorithmus ist, dass es zu einfach ist. Wenn eine Reihe von
zufällige Beschädigungen auftreten, besteht die Möglichkeit, die sie werden 1 in 256
nicht erkannt werden. Zum Beispiel:

Meldung: 6-23-4
Nachricht mit Prüfsumme: 6 23 4 33
Meldung nach der Übertragung: 8-20-5-33

Um die Prüfsumme zu stärken, konnten wir aus einer 8-Bit-Register zu ändern.
eine 16-Bit-register (d.h. die Summe der Byte-mod 65536 statt mod 256) also
wie anscheinend die Wahrscheinlichkeit für den Ausfall von 1/256 zu reduzieren
1/65536. Während im Grunde eine gute Idee schlägt fehl, es in diesem Fall da
die Formel ist nicht ausreichend 'zufällig'; mit einer einfachen Zusammenfassung
Formel, jedes ankommende Byte betrifft etwa nur ein Byte von der
summieren Register egal wie groß es ist. Zum Beispiel in der zweiten
Beispiel oben, die Zusammenfassung Register könnte ein Megabyte breit, und die
Fehler würden noch unentdeckt. Dieses Problem kann nur gelöst werden
die einfache Zusammenfassung Formel ersetzen durch eine kompliziertere Formel
Das verursacht jedes ankommende Byte haben Auswirkungen auf die gesamte
Prüfsumme Register.

So sehen wir, dass mindestens zwei Aspekte bilden eine starke müssen
Prüfsummenfunktion:

Breite: Breite breit genug, um eine geringe a Priori bieten registrieren
Ausfallwahrscheinlichkeit (z.B. 32 Bits gibt eine 1/2 ^ 32 Chance
des Fehlers).

CHAOS: Eine Formel, die jeder Eingangsbyte das Potential gibt zu ändern
beliebige Anzahl von Bits im Register.

Hinweis: Der Begriff 'Prüfsumme' wurde vermutlich verwendet, um früh zu beschreiben
Zusammenfassung der Formeln, aber hat jetzt eine allgemeinere Bedeutung
komplexere Algorithmen wie CRC diejenigen umfasst. Die
CRC-Algorithmen beschrieben werden sehr gut die zweite Bedingung zu erfüllen,
und mit einer Vielzahl von Prüfsumme breiten Betrieb konfiguriert werden können.

3. die Grundidee hinter CRC Algorithmen
---------------------------------------
Wo könnten wir bei unserer Suche für eine komplexere Funktion als?
aufsummieren? Alle Arten von Vorhaben Frühling in den Sinn. Wir konstruieren könnte
Tabellen mit den Ziffern von Pi oder Hash jedes ankommende Byte mit all den
Byte in das Register. Wir könnten sogar einem großen Telefonbuch halten.
Online, und verwenden Sie jedes ankommende Byte, kombiniert mit dem Register Bytes
um ein neues Handy zu indizieren registrieren Nummer was wäre der nächste Wert.
Die Möglichkeiten sind grenzenlos.

Allerdings brauchen wir nicht so weit gehen; der nächste Schritt der arithmetische
genügt. Während Zusatz eindeutig nicht stark genug, um Form ist ein
effektive Prüfsumme herausstellt, Division, so lange als ist die
Divisor ist etwa so breit wie die Prüfsumme-Register.

Die Grundidee von CRC Algorithmen ist einfach, die Nachricht zu behandeln, als ein
enorme Binärzahl, es durch einen anderen festen Binärzahl zu teilen,
und dem Rest aus der Division die Prüfsumme zu machen. Es ist nicht klar, wie
Man geht über das tun dies (Ich habe nicht den reine Mathematik-Hintergrund),
aber Tanenbaum versichert uns, dass solche G existieren und zitiert G mit 1 Bit
(15,14,1) als Beispiel für einen G, die alles teilen wird nicht eingeschaltet
weniger als 1... 1 wo... ist 32767 Nullen.

Fehler mit einer UNGERADEN Anzahl von BITS: fangen wir alle Beschädigungen wo
E hat eine ungerade Anzahl von Bits durch die Wahl einer G vor, dass eine gerade Anzahl von
Bit. Um dies zu sehen, beachten Sie, dass 1) CRC Multiplikation ist einfach XORing ein
Konstanten Wert in einem Register an verschiedenen Offsets 2) XORing ist einfach
ein Bit-Flip-Betrieb, und 3) Wenn Sie XOR einen Wert mit einer geraden Anzahl von
Bits in einem Register, die Ungereimtheit der Anzahl der 1 Bits in den
Register bleibt invariant. Versuchen Sie Beispiel: Beginnend mit E = 111,
kippen Sie alle drei Bits auf NULL durch die wiederholte Anwendung der XORing in
11 an einem der beiden Offsets (d.h. 'E = E XOR 011' und 'E = E XOR 110')
Dies ist fast isomorph zur 'Glas Becher' Party Puzzlespiel wo
fordern Sie heraus, dass jemand drei Becher durch die wiederholte kippen
Anwendung des Betriebs von zwei spiegeln. Die meisten der populären
CRC-Polys enthalten eine gerade Anzahl an 1 gesetzten Bits. (Hinweis: Tanenbaum Staaten
mehr spezifisch, die alle Fehler mit einer ungeraden Anzahl von Bits werden können
von G machen ein Vielfaches von 11 gefangen).

BURST-Fehler: Einem Burstfehler sieht wie E = 000... 000111... 11110000... 00.
Besteht E Nullen mit Ausnahme einer Auflage von 1 s irgendwo
innen. Dies kann als E=(10000...00)(1111111...111) neu gefasst werden wo
Es gibt Z Nullen in den linken Teil und n sind im rechten Teil. An
Abfangen von Fehlern dieser Art, wir einfach das niedrigste Bit g auf 1 festgelegt.
Dadurch wird sichergestellt, dass Links kein Faktor von G. Dann, so lange
G ist breiter als rechts, wird der Fehler erkannt. Finden Sie unter Tanenbaum für eine
klarere Erläuterung dieses; Ich bin in dieser Sache ein wenig unscharf. Hinweis:
Tanenbaum macht geltend, dass die Wahrscheinlichkeit für ein Platzen der Länge größer
als W durchkommen (0,5) ist ^ W.

Abschnitt auf die hohe Kunst der Auswahl Polys ist geschlossen.

Einige beliebte Polys sind:
16 Bits: (16,12,5,0) [X 25 Norm]
(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. eine unkomplizierte CRC Implementierung
---------------------------------------
Das ist das Ende der Theorie; Jetzt wenden wir uns an Implementierungen. Um zu starten
mit prüfen wir eine absolut gerade-Down-the-Middle-langweilig
unkompliziert-Lowspeed-Implementierung, die jeder Geschwindigkeit nicht verwendet
überhaupt betrügt. Wir werden dann dieses Programm Ausgehobelt bis wir verwandeln.
am Ende mit dem kompakten tabellengesteuerten Code, wir alle kennen und lieben, und
die einige von uns möchte verstehen.

Um einen CRC-Algorithmus implementieren alles, was wir tun müssen ist CRC Implementierung
Geschäftsbereich. Es gibt zwei Gründe, warum wir nicht einfach die Kluft verwenden
Anleitung von welcher Maschine, die wir sind. Die erste ist, dass wir
die Kluft im CRC-Arithmetik zu tun. Das zweite ist, dass die Dividende
möglicherweise lange zehn Megabyte, und die heutige Prozessoren haben keinen
Register, dass große.

Also um CRC-Abteilung zu implementieren, wir die Nachricht über feed müssen ein
Abteilung Register. An dieser Stelle müssen wir absolut präzise sein
über den Message-Daten. In den folgenden Beispielen wird die Meldung
einen Stream von Bytes (je 8 Bits) mit wenig 7 betrachtet
jedes Byte, das höchstwertige Bit (MSB) werden. Die
Bitstrom aus diese Bytes gebildet werden den Bitstrom mit dem MSB
(bit 7) des ersten Bytes zuerst gehen bis auf Bit 0 des ersten
Byte und dann das MSB der zweiten Byte und So weiter.

Mit diesem Hintergrund können wir eine Implementierung der CRC skizzieren.
Geschäftsbereich. Für das Beispiel, betrachten eine Poly mit W = 4 und
die Poly = 10111. Dann müssen wir das Durchführen der Division, eine 4-Bit verwenden
registrieren:

3 2 1 0-Bits
+---+---+---+---+
Pop! <-- | | | | | <---Augmented Nachricht
+---+---+---+---+

1 0 1 1 1 = der Poly

(Erinnerung: die erweiterte Nachricht ist die Nachricht gefolgt von W Nullbits.)

Führen Sie folgendermaßen die Division:

Laden Sie das Register mit NULL-Bits.
Ergänzen die Nachricht durch Anhängen W 0 Bits zu Ende.
Während (mehr Nachricht Bits)
BEGIN
Register zu, um ein Bit verlassen, lesen das nächste Bit der Verschiebung der
Erweiterte Nachricht in Register Bitposition 0.
Wenn (ein 1-Bit aus dem Register in Schritt 3 geholt)
Registrieren = Register XOR Poly.
Ende
Das Register enthält nun den Rest.

(Hinweis: In der Praxis kann die IF-Bedingung testen oben getestet werden
Bit des R vor dem Ausführen der UMSCHALTTASTE.)

Wir nennen dieses Algorithmus 'Einfach'.

Dies könnte ein bisschen chaotisch aussehen, aber alles, was wir wirklich tun ist
'Subtrahieren' verschiedene Kräfte (d.h. Verschiebungen) des Poly aus der
Meldung bis gibt es nichts mehr, aber der Rest. Studie der
manuelle Beispiele für Long-Division, wenn Sie dies nicht verstehen.

Es sollte klar sein, dass der obige Algorithmus für jede Breite W. funktioniert

9. eine tabellengesteuerte Implementierung
--------------------------------
Der oben genannten einfache Algorithmus ist ein guter Ausgangspunkt, da es
entspricht der Theorie dargestellt, so weit, und weil es
so einfach ist. Jedoch da es auf Bitebene tätig ist, ist es eher
Code (auch in C) umständlich und ineffizient ausführen (es muss
Schleife einmal für jedes Bit). Um zu beschleunigen, müssen wir einen Weg finden
Aktivieren des Algorithmus zum Verarbeiten der Nachricht in Einheiten größer als eins
bisschen. Kandidaten sind Nibbles (4 Bits), Byte (8 Bit), Wörter
(16 Bits) und Long (32 Bit) und höher, wenn wir es erreichen können. Der
Diese 4 Bits wird am besten vermieden, weil es kein Byte entspricht
Grenze. Am allerwenigsten sollte jede Beschleunigung bei operieren ermöglichen
Byte-Grenzen, und in der Tat die meisten der Tabelle getrieben Algorithmen
betreiben Sie ein Byte zu einem Zeitpunkt.

Für die Zwecke der Diskussion, lassen Sie uns von einer 4-Bit-Poly zu wechseln einer
32-Bit ein. Unsere Register sieht viel gleich, außer die Boxen
repräsentieren Bytes anstelle von Bits und der Poly ist 33 Bits (eine implizite
1 Bit an der Spitze und 'aktiv' 32-Bit) (W = 32).

3 2 1 0 Bytes
+----+----+----+----+
Pop! <-- | | | | | <---Augmented Nachricht
+----+----+----+----+

1 <---32 Bit--->

Der einfache Algorithmus ist noch anwendbar. Lassen Sie uns untersuchen Sie, was es tut.
Vorstellen, dass der einfache Algorithmus in vollem Gange ist und betrachten die
die Top 8 Bits des Registers 32-Bit (3 Byte), die Werte haben:

T7 t6 t5 t4 t3 t2 t1 t0

In der nächsten Iteration der einfachen t7 wird bestimmen, ob der Poly
werden in das gesamte Register XORed. Wenn t7 = 1, dies geschieht,
sonst wird es nicht. Angenommen Sie, die oberen 8 Bits des Poly g7 sind
G6... G0, werden dann nach der nächsten Iteration das oberste Byte:

T6 t5 t4 t3 t2 t1 t0??
+ t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Erinnerung: + ist XOR]

Die neue Top etwas (das kontrollieren wird, was passiert in der nächsten Iteration)
jetzt hat der Wert t6 + t7 * g7. Die wichtige Sache zu beachten ist hier
die aus informativen Sicht alle erforderlichen Angaben
Berechnen Sie das neue Top wenig war in den beiden obersten Bits des vorhanden die
ursprüngliche oberste Byte. Ebenso kann das nächste obere Bit in berechnet werden
werden Sie ausschließlich von der obersten drei Bits t7, t6 und t5. In der Tat in
Allgemein, können der Wert des oberen Bits des Registers k Iterationen
aus den oberen k Bits des Registers berechnet werden. Nehmen Sie wir dies
für einen Augenblick gewährt.

Betrachten Sie für einen Moment, dem wir oben 8 Bits des Registers zu verwenden
Berechnen Sie den Wert des oberen Bits des Registers während der nächsten 8
Iterationen. Angenommen, wir fahren die nächsten 8 Iterationen mit den
berechneten Werte (die wir vielleicht in ein einzelnes Byte speichern kann
Registrieren Sie und verlagern Sie sich auf ab jedes Bit auszuwählen). Dann stellen wir drei
Dinge:

* Das oberste Byte des Registers jetzt spielt keine Rolle. Egal, wie
viele Male und auf was die Poly auszugleichen ist XORed zu den Top 8
Bit, sie werden alle von der rechten Seite während verschoben werden die
Nächste 8 Iterationen sowieso.

* Die restlichen Bits werden Links eine Position verlagert werden und die
am weitesten rechts stehende Byte des Registers wird in das nächste Byte verlagert

UND

* Während all dies vor sich geht, wird das Register unterworfen werden, um eine
Reihe von XOR gemäß die Bits von der vorberechneten
Steuern Sie Byte.

Betrachten wir nun die Wirkung von XORing in einen konstanten Wert an verschiedenen
ein Register-Offsets. Zum Beispiel:

0100010 register
... XOR 0110 dies
.. 0110. XOR dies
0110... XOR dies
-------
0011000
-------

Der Punkt von diesem ist, dass man XOR Konstante Werte in ein register
zu deinem Herzen Freude und am Ende gibt es einen Wert
die bei XORed mit dem ursprünglichen Register haben die gleiche
Wirkung wie alle anderen XORs.

Vielleicht sehen Sie jetzt die Lösung. Es sieht alles falsch!

Hast du dies weit, Sie verstehen nicht nur die Theorie, die
Praxis, die optimierte Praxis, aber Sie verstehen auch die eigentliche
Code, den Sie stoßen dürften. Könnte jeder komplizierter? Ja
Es kann.

11. 'wider' tabellengesteuerten Implementierungen
--------------------------------------------
Trotz der Tatsache, der der obige Code als wahrscheinlich über optimiert ist
soviel wie es sein könnte, stoppen dies nicht einige unternehmungslustigen Personen
aus die Dinge noch komplizierter zu machen. Zu verstehen, wie diese
geschehen ist, müssen wir die Welt der Hardware geben.

DEFINITION: Ein Wert/Register spiegelt sich wenn es ist Bit getauscht wurden
um seinen Mittelpunkt. Zum Beispiel: 0101 ist die 4-Bit-Reflexion von 1010.
0011 ist die Reflexion von 1100.
0111-0101-1010-1111-0010-0101-1011-1100 ist die Reflexion der
0011-1101-1010-0100-1111-0101-1010-1110.

Es stellte sich heraus, dass UARTs (Diese handliche kleine Chips, die serielle IO ausführen)
sind in der Gewohnheit der Übertragung jedes Byte mit dem niederwertigsten
-Bit (Bit 0) erste und das höchstwertige Bit (Bit 7) Letzter (d.h.
wiedergegeben). Ein Effekt dieses Übereinkommens ist diese Hardware Ingenieure
Bau von Hardware-CRC-Rechner, die auf Bitebene betreiben
nahmen zur Berechnung CRCs Byte-Streams mit jedem bytes
in sich selbst reflektiert. Die Bytes werden in derselben Reihenfolge verarbeitet,
aber die Bits in jedem Byte sind vertauscht; -Bit 0 ist jetzt bit 7, Bit 1 ist
jetzt bit 6 und so weiter. Nun wäre dies viel wenn dieses Übereinkommen keine Rolle
auf Hardware-Land beschränkt war. Jedoch scheint es, dass irgendwann
Einige dieser CRC-Werte wurden auf der Software-Ebene präsentiert und
Jemand musste einige Code schreiben, der mit zusammenarbeiten würde die
Hardware-CRC-Berechnung.

In diesem Fall würde eine normale sane Software Engineer einfach
reflektieren Sie jedes Byte, bevor es verarbeitet. Jedoch scheint es, dass
normale sane Software-Ingenieure waren dünn auf dem Boden bei diesem frühen
Boden war gebrochen, weil statt reflektieren die Bytes
Wer verantwortlich war das Byte gedrückt und reflektiert die Welt,
zu den folgenden 'wider' Algorithmus führt die entspricht
das vorige, außer dass alles spiegelt sich außer der Eingabe
Byte.

Nachricht (nicht erweiterte) >---+
|
Byte 0 1 2 3 v
+----+----+----+----+ |
||||| >---XOR
+----+----+----+----+ |
^ |
| |
XOR |
| |
+----+----+----+----+0 |
+----+----+----+----+ v
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+<-----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+255

Hinweise:

* Die Tabelle ist identisch mit dem im vorherigen Algorithmus
Abgesehen davon, dass jeder Eintrag übernommen wurde.

* Der Anfangswert des Registers ist die gleiche wie in den vorherigen
Algorithmus, mit dem Unterschied, daß es reflektiert wurde.

* Die Bytes der Nachricht werden in der Reihenfolge verarbeitet.
vor (d.h. die Nachricht selbst wird nicht wiedergegeben).

* Die Nachrichtenbytes selbst müssen nicht explizit
reflektiert, weil alles andere wurde!

Am Ende der Ausführung, das Register enthält die Reflexion über die
CRC Endwert (Rest). Eigentlich bin ich ziemlich hart auf sein
Wer dies bis gekocht, weil es, dass Hardware scheint Implementierungen
der CRC verwendet Algorithmus, der reflektierten Prüfsummenwert und so
Herstellung einer reflektierten CRC war genau richtig. In der Tat reflektieren die Welt
war wohl eine gute Lösung - wenn eine verwirrende Technik.

Wir nennen dies den Algorithmus reflektiert.

Ob es Sinn zu der Zeit, den Effekt des Habens gemacht hat
reflektierte Algorithmen treten um FTP-Sites der Welt ist, die
etwa die Hälfte eines in läuft CRC-Implementierungen werden reflektiert und die
andere Hälfte nicht. Es ist wirklich furchtbar verwirrend. Insbesondere es
scheint mir, dass der beiläufigen Leser, in eine reflektierte läuft,
tabellengesteuerte Umsetzung mit den Bytes 'gefüttert in falschen Ende'
hätte Buckleys Chance jemals den Code mit dem Konzept zu verbinden
binäre mod 2 Division.

Erhalten es konnte keiner verwirrender, könnte es? Ja könnte es.

12. 'umgekehrte' Polys
--------------------
Als ob spiegelt sich Implementierungen waren nicht genug, gibt es eine andere
Konzept, treten um die Lage Bizaarly verwirrend macht.
Das Konzept wird umgekehrt Polys.

Es stellt sich heraus, dass die Reflexion des guten Polys sind tendenziell gute polys
auch! Das heißt, wenn G = 11101 ein gutes Poly-Wert ist, sein dann 10111 als
gut. Folglich scheint es, dass jedes Mal eine Organisation (z.B.
als CCITT) standardisiert auf eine besonders gute Poly ('Polynom'),
die in der realen Welt können nicht die Poly Reflexion allein lassen
entweder. Sie müssen nur, es zu benutzen. Dadurch wird die Gruppe von 'Standard'
Poly hat einen entsprechenden Satz von Überlegungen, die auch verwendet werden.
Um Verwechslungen zu vermeiden, werden wir diese 'umgekehrte' Polys nennen.

X 25 standard: 1-0001-0000-0010-0001
X 25 umgekehrt: 1-0000-1000-0001-0001

CRC16-Standard: 1-1000-0000-0000-0101
CRC16 umgekehrt: 1-0100-0000-0000-0011

Beachten Sie, dass hier ist es die gesamte Poly, reflektiert/rückgängig gemacht, die,
nicht nur die unteren W-Bits. Dies ist eine wichtige Unterscheidung. In der
reflektierte Algorithmus beschrieben im vorherigen Abschnitt, der Poly verwendet
im reflektierten Algorithmus war tatsächlich identisch mit derjenigen in der
nicht reflektierte Algorithmus; alles, was geschehen ist, dass die Bytes hatte
effektiv reflektiert. Als solcher, alle 16-Bit/32-Bit Zahlen in
der Algorithmus hatte wiedergegeben werden. Im Gegensatz dazu die gesamte poly
enthält die implizite ist ein bit an der Spitze und also umkehren einer poly
nicht das gleiche wie reflektieren seine unteren 16 oder 32-Bit.

Das Fazit von allem das ist, dass ein reflektierter Algorithmus nicht entspricht
der ursprüngliche Algorithmus mit der Poly widerspiegelt. Eigentlich ist dies
wahrscheinlich waren sie weniger verwirrend als wenn Wandler.

Wenn dir das alles ein wenig unklar erscheint, keine Sorge, denn wir sind
Sortieren sie alle raus 'real soon now'. Nur eine weitere Abschnitt vor
die.

13. die Anfangs-und Endwert
----------------------------
Neben der Komplexität bereits gesehen unterscheiden CRC Algorithmen
einander in zwei anderen Bezug:

* Der Anfangswert des Registers.

-Wert, XORed mit der abschließenden Register Wert zu sein.

Zum Beispiel Initialisiert der Algorithmus 'CRC32' sein Register zu
FFFFFFFF und XORs das letzte Register Wert FFFFFFFF.

Die meisten CRC Algorithmen initialisieren Sie ihre Register auf NULL. Jedoch einige
auf einen NULL-Wert zu initialisieren. In der Theorie (d. h. mit keine Annahmen
über die Nachricht) wirkt sich der anfängliche Wert nicht auf der Stärke der
der CRC-Algorithmus, der anfängliche Wert lediglich mit einem festen Start-
Punkt, von dem der Wert des Registers fortschreiten kann. Jedoch in
Praxis, einige Nachrichten sind eher als andere, und es ist klug
Initialisieren Sie das CRC-Algorithmus-Register auf einen Wert, die keine
'Blinde Flecken' werden, die voraussichtlich in der Praxis auftreten. Von 'blinden Fleck' ist
bedeutete eine Bytefolge Nachricht, die nicht im Register führen
seinen Wert ändert. Insbesondere initialisiert alle CRC-Algorithmus, der
sein Register auf NULL wird einen blinder Fleck von NULL haben, wenn es startet
und nicht in der Lage, 'einer der führenden zählen' Ausführen von 0 (null) Bytes. So ein
führende Null Bytes ist durchaus üblich in realen Nachrichten, ist es ratsam
Das Register Algorithmus auf einen NULL-Wert zu initialisieren.

14. Algorithmen absolut definieren.
----------------------------------
An dieser Stelle haben wir die verschiedenen Aspekte der abgedeckt.
tabellengesteuerte CRC Algorithmen. Denn es gibt so viele Variationen auf diesen
Algorithmen, lohnt es sich zu eine Nomenklatur für sie hergestellt.
Dieser Abschnitt versucht, dies zu tun.

Wir haben gesehen, dass CRC Algorithmen in variieren:

* Breite des Poly (Polynom).
-Wert des Poly.
* Anfangswert für das Register.
* Ob die Bits jedes Byte reflektiert werden, bevor Sie verarbeitet werden.
* Ob der Algorithmus Eingabebytes über das Register ernährt oder
Xors mit einem Byte von einem Ende und dann direkt in die Tabelle.
* Ob der abschließende Register Wert umgekehrt werden sollte (wie in reflektiert
-Versionen).
* Wert für XOR mit dem endgültigen Register Wert.

Um bestimmte CRC Algorithmen sprechen zu können, benötigen wir
zu in der Lage, diese genauer zu definieren als diese. Aus diesem Grund die
nächsten Abschnitt wird versucht, ein klar definiertes parametrisierte Modell bereitzustellen
für CRC Algorithmen. Um auf einen bestimmten Algorithmus verweisen, müssen wir dann
Geben Sie einfach den Algorithmus in Bezug auf die Parameter des Modells.

15. Ein parametrisierter Modell für CRC Algorithmen
--------------------------------------------
In diesem Abschnitt definieren wir einen genaue parametrisierte Modell CRC-Algorithmus
die, in Ermangelung eines besseren namens, wir nennen das 'Rocksoft ^ tm Modell
CRC-Algorithmus'(und warum nicht? Rocksoft ^ tm könnte mit einigen tun kostenlos
Werbung:-).

Der wichtigste Aspekt des Modell-Algorithmus ist, dass es fokussiert
ausschließlich auf Funktionalität ignorieren alle Implementierungsdetails. Die
Ziel der Übung ist, eine Weise des Beziehens auf genau zu konstruieren
bestimmten CRC Algorithmen, unabhängig davon, wie verwirrend Sie
implementiert. Zu diesem Zweck muß das Modell möglichst einfach und präzise wie
möglich ist, mit möglichst wenig Verwirrung wie möglich.

Die Rocksoft ^ tm Modell CRC-Algorithmus im Wesentlichen auf den direkten basiert
TABLE-Algorithmus angegeben haben. Allerdings muss der Algorithmus
weiter parametrisiert, um auf die gleiche Weise wie manche sich Verhalten können
der messier-Algorithmen in der realen Welt.

Aktivieren Sie den Algorithmus wie verhält sich wider Algorithmen, wir
Bereitstellen Sie eine boolesche Option entsprechend der Eingabebytes und einen booleschen Wert
Option, um anzugeben, ob den Prüfsumme Ausgabewert widerspiegeln. Von
Rahmung Reflexion als ein Eingabe/Ausgabe-Transformation, vermeiden wir die
Verwirrung mit geistig ordnen Sie die Parameter der reflektiert und
nicht reflektierte Algorithmen.

Ein zusätzlicher Parameter ermöglicht es, den Algorithmus Register initialisiert werden
auf einen bestimmten Wert. Ein weiterer Parameter ist XORed mit Finale
Wert, bevor er zurückgegeben wird.

Durch alle diese Stücke Zusammenstellung landen wir mit den Parametern der
der Algorithmus:

NAME: Dies ist ein Name für den Algorithmus. Ein String-Wert.

Breite: Dies ist die Breite des Algorithmus in Bit angegeben. Dies
ist eine kleiner als die Breite des Poly.

POLY: Dieser Parameter ist der Poly. Dies ist ein binärer Wert,
sollte als Hexadezimalzahl angegeben werden. Oben etwas von der
Poly sollte weggelassen werden. Beispielsweise, wenn die Poly 10110, ist Sie
sollten 06 angeben. Ein wichtiger Aspekt dieses Parameters ist, dass es
die unreflektierte Poly darstellt; das untere Bit dieses Parameters
ist immer die LSB des Divisors während der Division unabhängig von
ob spiegelt sich der Algorithmus modelliert wird.

INIT: Dieser Parameter gibt den Anfangswert des Registers
Wenn der Algorithmus startet. Dies ist der Wert, der zugewiesen werden soll
zu den Registern in der direkten Table-Algorithmus. In der Tabelle
Algorithmus, wir denken das Register immer beginnend mit der
Wert 0 (null), und dieser Wert wird von XORed in das Register nach dem
Bit und n-ten Iteration. Dieser Parameter sollte angegeben werden, als eine
Hexadezimalzahl.

REFIN: Dies ist ein boolean-Parameter. Wenn es falsch ist, sind Eingabebytes
mit Bit 7 als das wichtigste Bit verarbeitet
(MSB) und Bit 0 als das niederwertigste Bit behandelt werden. Wenn diese
der Parameter FALSE ist, spiegelt jedes Byte vor der Verarbeitung.

REFOUT: Dies ist ein boolean-Parameter. Wenn es auf FALSE festgelegt ist die
letzten Wert in das Register wird in der XOROUT-Bühne direkt eingespeist,
Wenn dieser Parameter auf true festgelegt ist,