On-line CRC Berechnung und freie Bibliothek

• Introduction on CRC Berechnungen
• Free CRC berechnung routinen zum Download

Introduction on CRC berechnungen

Wenn digitale Daten gespeichert oder verbunden werden, kann es zu Datenbeschädigungen kommen. Seit Beginn der Informatik haben die Menschen über Möglichkeiten nachgedacht, mit dieser Art von Problem umzugehen., Für serielle Daten haben sie die Lösung gefunden, jedem gesendeten Byte ein Paritätsbit anzuhängen. Dieser einfache Erkennungsmechanismus funktioniert, wenn sich eine ungerade Anzahl von Bits in einem Byte ändert, aber eine gerade Anzahl von falschen Bits in einem Byte durch die Paritätsprüfung nicht erkannt wird. Um dieses Problem zu überwinden, haben die Menschen nach mathematischen Klangmechanismen gesucht, um mehrere falsche Bits zu erkennen. Die CRC-Berechnung oder zyklische Redundanzprüfung war das Ergebnis davon. Heutzutage werden CRC-Berechnungen in allen Arten von Kommunikation verwendet. Alle über eine Netzwerkverbindung gesendeten Pakete werden mit einem CRC überprüft., Außerdem ist jedem Datenblock auf Ihrer Festplatte ein CRC-Wert zugeordnet. Die moderne Computerwelt kann nicht ohne diese CRC-Berechnung auskommen. Mal sehen, warum sie so weit verbreitet sind. Die Antwort ist einfach, sie sind leistungsstark, erkennen viele Arten von Fehlern und sind extrem schnell zu berechnen, insbesondere wenn dedizierte Hardware-Chips verwendet werden.

Man könnte meinen, dass die Verwendung einer Prüfsumme richtige CRC-Berechnungen ersetzen kann. Es ist sicherlich einfacher, eine Prüfsumme zu berechnen, aber Prüfsummen finden nicht alle Fehler. Nehmen wir eine Beispielzeichenfolge und berechnen Sie eine Ein-Byte-Prüfsumme., Die Beispielzeichenfolge ist „Lammert“, die in die ASCII-Werte konvertiert wird . Die Ein-Byte-Prüfsumme dieses Arrays kann berechnet werden, indem alle Werte addiert werden, anstatt sie durch 256 zu dividieren und den Rest beizubehalten. Die resultierende Prüfsumme ist 210. Sie können den obigen Rechner verwenden, um dieses Ergebnis zu überprüfen.

In diesem Beispiel haben wir eine ein Byte lange Prüfsumme verwendet, die uns 256 verschiedene Werte gibt. Die Verwendung einer Zwei-Byte-Prüfsumme führt zu 65.536 möglichen unterschiedlichen Prüfsummenwerten, und wenn ein Vier-Byte-Wert verwendet wird, sind mehr als vier Milliarden mögliche Werte vorhanden., Wir könnten daraus schließen, dass bei einer Vier-Byte-Prüfsumme die Wahrscheinlichkeit, dass wir versehentlich keinen Fehler erkennen, weniger als 1 bis 4 Milliarden beträgt. Scheint ziemlich gut zu sein, aber das ist nur Theorie. In der Praxis ändern sich Bits während der Kommunikation nicht rein zufällig. Sie versagen oft bei Bursts oder aufgrund elektrischer Spitzen. Nehmen wir an, dass in unserem Beispielarray das niedrigstwertige Bit des Zeichens ‘L‘ gesetzt ist und das niedrigstwertige Bit des Zeichens ‘a‘ während der Kommunikation verloren geht. Der Empfänger sieht dann das Array, das die Zeichenfolge „M ‚ mmert“darstellt., Die Prüfsumme für diese neue Zeichenfolge ist immer noch 210, aber das Ergebnis ist offensichtlich falsch, erst nachdem zwei Bits geändert wurden. Selbst wenn wir eine vier Byte lange Prüfsumme verwendet hätten, hätten wir diesen Übertragungsfehler nicht erkannt. Die Berechnung einer Prüfsumme kann also eine einfache Methode zum Erkennen von Fehlern sein, bietet jedoch unabhängig von der Länge der Prüfsumme nicht viel mehr Schutz als das Paritätsbit.

Die Idee hinter einer Prüfwertberechnung ist einfach. Verwenden Sie eine Funktion F (bval,cval), die ein Datenbyte und einen Prüfwert eingibt und einen neu berechneten Prüfwert ausgibt., Tatsächlich können Prüfsummenberechnungen wie oben beschrieben auf diese Weise definiert werden. Unser Ein-Byte-Prüfsummenbeispiel hätte mit der folgenden Funktion (in C-Sprache) berechnet werden können, die wir für jedes Byte in der Eingabezeichenfolge wiederholt aufrufen. Der Anfangswert für cval ist 0.

int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}

Die Idee hinter der CRC-Berechnung besteht darin, die Daten als eine große Binärzahl zu betrachten. Diese Zahl wird durch einen bestimmten Wert geteilt und der Rest der Berechnung wird CRC genannt., Die Division in der CRC-Berechnung scheint zunächst viel Rechenleistung zu kosten, kann jedoch sehr schnell durchgeführt werden, wenn wir eine ähnliche Methode wie in der Schule anwenden. Wir werden als Beispiel den Rest für das Zeichen ‘m‘—1101101 in binärer Notation-berechnen, indem wir es durch 19 oder 10011 dividieren. Bitte beachten Sie, dass 19 eine ungerade Zahl ist. Dies ist notwendig, wie wir weiter sehen werden. Bitte beachten Sie Ihre Schulbücher, da sich die binäre Berechnungsmethode hier nicht sehr von der Dezimalmethode unterscheidet, die Sie in jungen Jahren gelernt haben. Es könnte nur ein bisschen seltsam aussehen., Auch die Notationen unterscheiden sich zwischen den Ländern, aber die Methode ist ähnlich.

 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

Mit Dezimalberechnungen können Sie schnell überprüfen, ob 109 geteilt durch 19 einen Quotienten von 5 mit 14 als Rest ergibt. Was wir aber auch im Schema sehen, ist, dass jedes zusätzliche Bit zur Überprüfung nur einen binären Vergleich und in 50% der Fälle eine binäre Subtraktion kostet., Sie können die Anzahl der Bits der Testdatenkette leicht erhöhen—zum Beispiel auf 56 Bit, wenn wir unseren Beispielwert „Lammert“verwenden—und das Ergebnis kann mit 56 binären Vergleichen und durchschnittlich 28 binären Subtraktionen berechnet werden. Dies kann in Hardware direkt mit nur sehr wenigen Transistoren implementiert werden. Auch Softwarealgorithmen können sehr effizient sein.

Für CRC-Berechnungen wird keine normale Subtraktion verwendet, aber alle Berechnungen werden modulo 2 durchgeführt. In dieser Situation ignorieren Sie Carry-Bits und tatsächlich entspricht die Subtraktion einer exklusiven oder Operation., Dies sieht seltsam aus, der resultierende Rest hat einen anderen Wert, aber aus algebraischer Sicht ist die Funktionalität gleich. Eine Diskussion darüber würde universitäre Kenntnisse der algebraischen Feldtheorie erfordern, und ich denke, die meisten Leser interessieren sich nicht dafür. Bitte schauen Sie am Ende dieses Dokuments für Bücher, die dies im Detail diskutieren.

Jetzt haben wir eine CRC-Berechnungsmethode, die sowohl in Hardware als auch in Software implementiert werden kann und auch ein zufälligeres Gefühl hat als die Berechnung einer normalen Prüfsumme. Aber wie wird es in der Praxis funktionieren, wenn ein oder mehrere Bits falsch sind?, Wenn wir den Divisor—19 in unserem Beispiel—als ungerade Zahl auswählen, benötigen Sie keine hochgradige Mathematik, um zu sehen, dass jeder einzelne Bitfehler erkannt wird. Dies liegt daran, dass jeder einzelne Bitfehler die Dividende mit einer Potenz von 2 ändern lässt. Wenn sich zum Beispiel Bit n von 0 auf 1 ändert, erhöht sich der Wert der Dividende mit 2n. Wenn sich Bit n dagegen von 1 auf 0 ändert, verringert sich der Wert der Dividende mit 2n. Da Sie keine Zweierpotenz durch eine ungerade Zahl teilen können, ändert sich der Rest der CRC-Berechnung und der Fehler bleibt nicht unbemerkt.,

Die zweite Situation, die wir erkennen möchten, ist, wenn sich zwei einzelne Bits in den Daten ändern. Dies erfordert einige Mathematik, die in Tanenbaums unten erwähntem Buch gelesen werden kann. Sie müssen Ihren Divisor sehr sorgfältig auswählen, um sicherzustellen, dass Sie ihn unabhängig vom Abstand zwischen den beiden falschen Bits immer erkennen. Es ist bekannt, dass die häufig verwendeten Werte 0x8005 und 0x1021 der CRC16-und CRC-CCITT-Berechnungen bei diesem Problem sehr gut funktionieren., Bitte beachten Sie, dass andere Werte möglicherweise vorhanden sind oder nicht, und Sie können nicht einfach berechnen, welcher Divisorwert für die Erkennung von Zwei-Bit-Fehlern geeignet ist und welcher nicht. Verlassen Sie sich auf umfangreiche mathematische Untersuchungen zu diesem Thema, die vor einigen Jahrzehnten von hochqualifizierten Mathematikern durchgeführt wurden, und verwenden Sie die Werte, die diese Personen erhalten haben.

Darüber hinaus möchten wir mit unserer CRC-Berechnung alle Fehler erkennen, bei denen sich eine ungerade Anzahl von Bit ändert. Dies kann erreicht werden, indem ein Divisor mit einer geraden Anzahl gesetzter Bits verwendet wird. Mit Modulo 2 Mathematik können Sie zeigen, dass alle Fehler mit einer ungeraden Anzahl von Bits erkannt werden., Wie ich bereits sagte, wird in der Mathematik von Modulo 2 die Subtraktionsfunktion durch das exklusive or ersetzt. Es gibt vier mögliche XOR-Operationen.

0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even

Wir sehen, dass für alle Kombinationen von Bitwerten die Kuriosität des Ausdrucks gleich bleibt. Bei der Auswahl eines Divisors mit einer geraden Anzahl gesetzter Bits entspricht die Kuriosität des Rests der Kuriosität der Dividende. Wenn sich daher die Seltsamkeit der Dividende ändert, weil sich eine ungerade Anzahl von Bits ändert, ändert sich auch der Rest., Alle Fehler, die eine ungerade Anzahl von Bits ändern, werden also durch eine CRC-Berechnung erkannt, die mit einem solchen Divisor durchgeführt wird. Sie haben vielleicht gesehen, dass die häufig verwendeten Divisorwerte 0x8005 und 0x1021 tatsächlich eine ungerade Anzahl von Bits haben und nicht einmal wie hier angegeben. Dies liegt daran, dass sich innerhalb des Algorithmus ein „verstecktes“ zusätzliches Bit 216 befindet, das den tatsächlich verwendeten Divisorwert 0x18005 und 0x11021 innerhalb des Algorithmus macht.,

Last but not least wollen wir mit unserer CRC-Berechnung alle Burst-Fehler mit einer maximal zu erkennenden Länge und alle längeren Burst-Fehler mit hoher Wahrscheinlichkeit erkennen. Ein Burst-Fehler ist in der Kommunikation ziemlich häufig. Es ist die Art von Fehler, der durch Blitzschlag, Relaisumschaltung usw. auftritt. wobei während eines kleinen Zeitraums alle Bits auf eins gesetzt sind., Um dies wirklich zu verstehen, müssen Sie auch einige Kenntnisse der Modulo-2-Algebra haben, also akzeptieren Sie bitte, dass Sie mit einem 16-Bit-Divisor alle Bursts mit einer maximalen Länge von 16 Bit und alle längeren Bursts mit mindestens 99.997% Sicherheit erkennen können.

In einem reinen mathematischen Ansatz wird die CRC-Berechnung als Polynomberechnung niedergeschrieben. Der Divisorwert wird meistens nicht als Binärzahl, sondern als Polynom bestimmter Ordnung beschrieben. Im normalen Leben werden einige Polynome häufiger verwendet als andere., Die drei in der on-line CRC Berechnung auf dieser Seite verwendeten sind die 16 Bit breite CRC16 und CRC-CCITT und die 32 Bit breite CRC32. Letzteres wird wahrscheinlich am häufigsten verwendet, da es unter anderem der CRC-Generator für die Überprüfung und Validierung des gesamten Netzwerkverkehrs ist.

Für alle drei Arten von CRC-Berechnungen habe ich eine freie Software-Bibliothek zur Verfügung. Das Testprogramm kann direkt zum Testen von Dateien oder Strings verwendet werden. Sie können sich auch die Quellcodes ansehen und diese CRC-Routinen in Ihr eigenes Programm integrieren., Bitte beachten Sie die Initialisierungswerte der CRC-Berechnung und mögliche notwendige Nachbearbeitung wie Flipping-Bits. Wenn Sie dies nicht tun, erhalten Sie möglicherweise andere Ergebnisse als andere CRC-Implementierungen. All diese Vor-und Nachbearbeitung erfolgt im Beispielprogramm, so dass es nicht zu schwierig sein sollte, Ihre eigene Implementierung zum Laufen zu bringen. Ein häufig verwendeter Test besteht darin, den CRC-Wert für die ASCII-Zeichenfolge „123456789“zu berechnen., Wenn das Ergebnis Ihrer Routine mit dem Ergebnis des Testprogramms oder dem Ergebnis auf dieser Website übereinstimmt, funktioniert Ihre Implementierung und ist mit den meisten anderen Implementierungen kompatibel.

Nur als Referenz die Polynomfunktionen für die gängigsten CRC-Berechnungen. Bitte denken Sie daran, dass der Term höchster Ordnung des Polynoms (x16 oder x32) in der Binärzahlendarstellung nicht vorhanden ist, sondern vom Algorithmus selbst impliziert wird.,

Literatur
2002	Computer-Netzwerke, beschreibt die gemeinsamen Netzwerk-Systeme und die Theorie und die algorithmen, die hinter Ihrer Umsetzung.	Andrew S. Tanenbaum
verschiedene	Die Kunst der Computerprogrammierung ist die Hauptreferenz für semi-numerische Algorithmen. Polynomberechnungen werden ausführlich beschrieben. Ein gewisses Maß an Mathematik ist jedoch notwendig, um es vollständig zu verstehen.	Donald E. Knuth
–	DNP 3.,0, oder verteiltes Netzwerkprotokoll ist ein Kommunikationsprotokoll, das für den Einsatz zwischen Umspannwerkscomputern, RTUs-Fernterminaleinheiten, intelligenten IEDs-elektronischen Geräten und Master-Stationen für die Stromversorgungsindustrie entwickelt wurde. Es wird jetzt auch in bekannten Branchen wie Abwasserbehandlung, Transport und der Öl-und Gasindustrie eingesetzt.	DNP Benutzer Gruppe