CRC calculator

(die CRC-Berechnung befindet sich ganz unten auf dieser Seite)

Aufrufe: 2681

Die zyklische Redundanzprüfung (englisch cyclic redundancy check, daher meist CRC) ist ein Verfahren zur Bestimmung eines Prüfwerts für Daten, um Fehler bei der Übertragung oder Speicherung erkennen zu können. Im Idealfall kann das Verfahren sogar die empfangenen Daten selbständig korrigieren, um eine erneute Übertragung zu vermeiden.

Allgemeines

Vor der Datenspeicherung oder Übertragung wird für jeden Datenblock der Nutzdaten zusätzliche Redundanz in Form eines sogenannten CRC-Werts angefügt. Dieser ist ein nach einem bestimmten Verfahren berechneter Prüfwert, mit dessen Hilfe man während der Speicherung bzw. Übertragung eventuell aufgetretene Fehler erkennen kann. Zur Überprüfung der Daten wird dasselbe Berechnungsverfahren auf den Datenblock einschließlich des angefügten CRC-Werts angewandt. Ist das Ergebnis dann null, kann angenommen werden, dass der Datenblock unverfälscht ist. Verschiedene technische Anwendungen weichen allerdings von diesem Schema ab, indem sie beispielsweise die Berechnung mit einem bestimmten Wert initialisieren oder den CRC-Wert vor der Übermittlung invertieren.

CRC ist so ausgelegt, dass Fehler bei der Übertragung der Daten, wie sie beispielsweise durch Rauschen auf der Leitung verursacht werden könnten, mit hoher Wahrscheinlichkeit entdeckt werden. CRCs von seriellen Datenübertragungen können sehr einfach in Hardware realisiert werden. Zum Beispiel werden Datenübertragungen über Ethernet, sowie die meisten Festplatten-Übertragungen mit CRC-Verfahren geprüft.

Das CRC-Verfahren ist nur für die Erkennung von zufälligen Fehlern ausgelegt. Es ist nicht geeignet, die Integrität der Daten zu bestätigen. Das heißt, es ist verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom zu erzeugen, der den gleichen CRC-Wert wie eine gegebene Nachricht hat. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie beispielsweise SHA zum Einsatz kommen.

Der Name des Verfahrens beruht darauf, dass der angefügte Wert keinen Informationsgehalt besitzt, der nicht bereits in dem zugrunde liegenden Datenblock enthalten ist. Er ist deshalb redundant. CRCs beruhen auf zyklischen Codes. Das sind Block-Codes, die die Eigenschaft haben, dass jede zyklische Verschiebung der Bits eines gültigen Code-Worts ebenfalls ein gültiges Code-Wort ist.

Verfahren

Die Berechnung des CRC-Werts beruht auf Polynomdivision: Die Folge der zu übertragenden Bits wird als binäres Polynom betrachtet. Beispiel: Die Bitfolge 1,0,0,1,1,1,0,1 entspricht dem Polynom

1·x7 + 0·x6 + 0·x5 + 1·x4 + 1·x3 + 1·x2 + 0·x1 + 1

Die Bitfolge der Coderepräsentation der Daten wird durch ein vorher festzulegendes Generatorpolynom (das CRC-Polynom) Modulo mod(2) geteilt, wobei ein Rest bleibt. Dieser Rest ist der CRC-Wert. Bei der Übertragung des Datenblocks hängt man den CRC-Wert an den originalen Datenblock an und überträgt ihn mit.

Um zu verifizieren, dass die Daten keinen Fehler beinhalten, wird der empfangene Datenblock mit angehängtem CRC-Wert als Binärfolge interpretiert, erneut durch das CRC-Polynom Modulo geteilt und der Rest ermittelt. Wenn kein Rest bleibt, ist entweder kein Fehler aufgetreten oder es ist ein (sehr unwahrscheinlicher) Fehler aufgetreten, der in Polynomdarstellung das CRC-Polynom als Faktor hat.

Es ist darauf zu achten, dass es sich bei den Einsen und Nullen der Kommunikation mit CRC nicht um die Repräsentation einer Zahl, sondern um ein Polynom handelt. Das bedeutet, dass die Modulodivision mit Binärzahlen (oder Zahlen allgemein) beispielsweise mit dem Taschenrechner nicht auf das richtige Ergebnis führt.

Die Datenübertragung erfordert bestimmte unerlässliche Übereinkommen. Zum Einen muss dem Empfänger bewusst sein, dass überhaupt eine gesicherte Übertragung der Ursprungsdaten stattfinden soll. An der Art des eintreffenden Datenstromes allein ist dies nicht zu erkennen. Zum Anderen muss der Empfänger dasselbe CRC-Polynom und Rechenverfahren benutzen wie der Sender. Und schließlich muss der Empfänger die Information besitzen, wo sich im Datenstrom die zusätzlich zu den Daten

Quelle: Wikipedia

CRC berechnen