Die zyklische Redundanzprüfung (ZRP, 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.
Es wurde 1961 von W. Wesley Peterson entwickelt.W. W. Peterson: Cyclic Codes for Error Detection. In: Proceedings of the IRE, Vol. 49, No. 1, 1961, S. 228–235
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 oder Signatur-Funktionen wie beispielsweise RSA 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 dem Prinzip der Polynomdivision. Die zu übertragenden Bits werden als Faktoren eines Polynoms interpretiert, mit welchen Berechnungen angestellt werden können, die das nachfolgende Verfahren ermöglichen. Insbesondere entspricht die Polynomdivision einem bitweisen XOR (exklusiv-oder bzw. entweder-oder). Sind die Bits gleich, ist das Ergebnis 0. Sind sie verschieden, ist das Ergebnis 1.
Es wird ein Prüfwert der Länge n bestimmt (das CRC-Polynom) und die zu übertragende Bitfolge mit n-1 0en verlängert. Dies ergibt den sogenannte Rahmen. Anschließend wird der Rahmen wiederholt durch den Prüfwert geteilt, wobei die beiden Bitfolgen jeweils an der ersten Ziffer ausgerichtet werden, die 1 ist. Dieses Verfahren ist nicht mit normaler Division von Binärzahlen zu verwechseln, welche andere Ergebnisse liefert. Für den Rahmen bzw. das Zwischenergebnis 000110101 und den Prüfwert 01011, würden die Werte wie folgend ausgerichtet und verrechnet werden: Zwischenergebnis 000110100 Prüfwert 01011 Division / Ergebnis 000011000Das Ergebnis dieser Berechnung wird mit jedem Schritt kleiner. Hat das Ergebnis weniger relevante Stellen als der Prüfwert, werden die letzten n-1 Stellen als Rest übernommen, der sogenannte CRC-Wert. Dieser Rest wird an die zu übertragende Bitfolge angehängt und gemeinsam übertragen.
Um zu verifizieren, dass die Daten fehlerfrei übertragen wurden, wiederholt der Empfänger die Berechnung mit der übertragenen Bitfolge und dem CRC-Polynom. Da die Bitfolge um den ermittelten Rest ergänzt wurde, bleibt dieses Mal kein Rest übrig, wenn die Daten fehlerfrei übertragen wurden (oder wenn ein sehr seltener Fehler auftrat, der einem Vielfachen des CRC-Polynoms entsprach).
Das Verfahren setzt voraus, dass Sender und Empfänger wissen, dass gesicherte Daten übertragen werden und wie das CRC-Polynom lautet. Den Daten selbst ist beides nicht zu entnehmen.
Beispiel Für die Bitfolge 11011 und dem Prüfwert 110101 (Länge n = 6), ergibt sich der Rahmen 1101100000 (Bitfolge um n-1 = 5 0en verlängert). Anschließend wird der Rahmen durch das Generatorpolynom dividiert. Die beiden Zahlen werden jeweils an der ersten Ziffer ausgerichtet, da diese beide eine 1 sind.Rahmen 1101100000 Prüfwert 110101 Division / Zwischenergebnis 0000110000Das Zwischenergebnis hat sechs relevante Stellen (110000), der Prüfwert ebenfalls. Also wird erneut dividiert. Dieses Mal wird der Prüfwert an der fünften Stelle des Zwischenergebnisses ausgerichtet.Zwischenergebnis 0000110000 Prüfwert 110101 Division / Ergebnis 0000000101 Das Ergebnis hat nun nur noch drei relevante Stellen, also werden die letzten n-1 (=5) Stellen als CRC-Wert übernommen, in diesem Fall also 00101. Die Bitfolge 11011 und der Rest 00101 ergeben die zu übertragenden Daten 1101100101. Möchte der Empfänger die Korrektheit der Daten verifizieren, führt er die Polynomdivision mit dem Rahmen 1101100101 und dem Prüfwert 110101 durch:Rahmen 1101100101 Prüfwert 110101 Division / Zwischenergebnis 0000110101 Prüfwert 110101 Division / Ergebnis 0Das Ergebnis ist 0, also trat wahrscheinlich kein Fehler auf. Wurde stattdessen der fehlerhafte Rahmen 1001100101 empfangen, ergibt sich folgende Berechnung:Rahmen 1001100101 Prüfwert 110101 Division / Zwischenergebnis 0100110101 Prüfwert 110101 Division / Zwischenergebnis 10011101 Prüfwert 110101 Division / Zwischenergebnis 1001001 Prüfwert 110101 Division / Zwischenergebnis 100011 Prüfwert 110101 Division / Zwischenergebnis 10110Der Rest der Division (10110) ist ungleich null. Also ist ein Fehler aufgetreten.
Bei der Überprüfung auf Richtigkeit können folgende vier Fälle auftreten: Der Rest der Division ist null und die Nachricht ist richtig Der Rest der Division ist null und die Nachricht ist fehlerhaft (dieser Fall ist unwahrscheinlich, kann aber vorkommen, wenn das Fehlerpolynom ein Vielfaches des Generatorpolynoms ist oder wenn sich zwei Fehler in der gleichen Übertragung gegenseitig aufheben) Der Rest der Division ist ungleich null und die Nachricht ist fehlerhaft Der Rest der Division ist ungleich null und die Nachricht ist richtig (dieser Fall tritt ein, wenn lediglich der angehängte Rest fehlerhaft übertragen wird; dies ist jedoch ebenfalls unwahrscheinlich, da der übertragene Rest im Vergleich zur Gesamtlänge des Pakets kurz ist)
Umsetzung Das CRC-Verfahren lässt sich sowohl in einfachen Hardware-Bausteinen als auch in Software realisieren. Verwendet werden ein Schieberegister mit n Bits, dabei ist n die Länge des Prüfwerts (etwa ein 32-Bit-Schieberegister bei CRC-32) und ein Bit-Datenstrom beliebiger Länge gefolgt von n Null-Bits.
Pseudocode des Algorithmus, höchstwertiges Bit ganz links, Multiplikation mit 2 bedeutet ein Schieben um eine Stelle nach links: crc := 0000… (Startwert) für alle Bits b im Datenstrom: wenn das am weitesten links stehende Bit von crc 1 ist: crc := (crc * 2 + b) xor CRC-Polynom sonst: crc := crc * 2 + b crc enthält das Ergebnis.
Durch Verwendung einer Tabelle, die beim Verfahren CRC-8 beispielsweise für jedes der 256 möglichen Bytes den zugehörigen CRC-Wert enthält, lässt sich obiger Algorithmus um den Faktor 8 beschleunigen. Das resultiert daraus, dass ein Tabelleneintrag 8 Bits = 1 Byte enthält und verschiedene Tabelleneinträge existieren. Die Geschwindigkeitssteigerung wird durch den direkten Zugriff auf die Tabelle mithilfe der zu berechnenden Bitfolge realisiert, indem die gesuchte CRC-8-Berechnung an der Stelle in der Tabelle steht, welche den binären Wert der zu berechnenden Bitfolge als Index hat.
Die Operationen Linksschieben und Exklusiv-Oder machen die CRC hervorragend geeignet zur Verwendung in Logikschaltungen. Die CRC eines Datenstroms kann bitweise (oder auch Byte-weise usf.) berechnet und vom Sender an die Daten angehängt werden. Der Empfänger des Datenstroms kann den CRC genauso wie der Sender berechnen, jedoch unter Einbeziehung des CRC. Das Ergebnis inklusive des CRC muss dann gleich null sein, sonst enthält der Strom Bitfehler.
CRC-Typen werden oft anhand des als Divisor verwendeten Polynoms unterschieden (im Hexadezimal-Format). Eines der meistverwendeten CRCs (u. a. von Ethernet, FDDI, ZIP und PNG benutzt) ist das Polynom 0x04C11DB7, bekannt als CRC-32. Es stellte sich heraus, dass einige Polynome besser „schützen“ als andere. Für CRC häufig verwendete Polynome sind das Ergebnis umfangreicher mathematischer und empirischer Analysen und keine Zufallszahlen, auch wenn sie so aussehen.
Andere Startwerte Die Implementierung führt eine Polynomdivision aus, wenn als Startwert 0000… verwendet wird. Oft findet man andere Startwerte, etwa 1111…. Dies entspricht einer Polynomdivision, wenn die ersten n Bits des Datenstroms invertiert werden.
Ein Startwert ungleich 0000… ist vorzuziehen, da fehlende Bits innerhalb führender Nullen im Datenstrom sonst nicht erkannt werden (ebenso wie bei einer gewöhnlichen Division zählen bei einer Polynomdivision führende Nullen nicht).
Nullproblem und Nachbearbeitung Eine weitere Problematik stellt das Nullproblem dar, das in zweierlei Form auftritt:
Produziert ein Datenstrom zufällig einen CRC gleich null, so ist der CRC auch dann null, wenn dem Datenstrom zusätzliche Nullen angehängt werden, oder – falls der Datenstrom mit einer oder mehreren Nullen endet – einige dieser letzten Nullen entfernt werden. Ist dem Ende des Datenstroms der CRC angehängt (so wie es ein Sender eben verschickt) und bei der Übertragung werden (nach dem gesendeten CRC) noch zusätzliche Nullen angefügt, so können diese zusätzlichen Nullen am Ende nicht erkannt werden.
Das Nullproblem in beiden Ausführungen ist unabhängig davon, ob Startwerte gleich null oder ungleich null verwendet werden.
Das Nullproblem in beiden Ausführungen wird vermieden, indem die Bits des CRC-Ergebnisses invertiert werden. Erfolgt im Empfänger die CRC-Prüfung derart, dass der Empfänger einen CRC aus dem empfangenen Datenpaket berechnet, wobei das Datenpaket aus Datenstrom und angehängtem CRC besteht, so ist im Falle eines unveränderten (nichtinvertierten) CRC des Senders der berechnete CRC im Empfänger stets null. Im Falle eines invertierten CRC des Senders ist der berechnete CRC im Empfänger immer der gleiche Wert, dieser wird auch als Magic Number bezeichnet.
Das Nullproblem der zweiten Ausführung kann auch vermieden werden, indem die Reihenfolge der CRC-Bits umgekehrt wird. Unerkannt bleibt jedoch der Fall, wo der CRC gleich null ist, was das Nullproblem der ersten Art darstellt.
Das bisher beschriebene Nullproblem bezieht sich also auf die Problematik, am Ende des Datenstroms zusätzlich hinzugefügte oder verlorengegangene Nullen zu erkennen. Dies ist jedoch nur dann nötig, wenn aufgrund vorherrschender Randbedingungen nicht sichergestellt werden kann, dass die Größe der Daten unverändert bleibt.
Von einem Nullproblem spricht man jedoch bisweilen auch dann, wenn es problematisch ist, wenn ein Datenstrom aus lauter Nullen auch einen CRC gleich Null erzeugt. Ein CRC gleich null aus Null-Daten entsteht unabhängig vom Generatorpolynom grundsätzlich, wenn der CRC-Startwert gleich null ist und die Bits des resultierenden CRC nicht invertiert werden. Dieses Problem kann somit vermieden werden, indem ein Startwert ungleich null festgelegt wird oder aber auch die resultierenden CRC-Bits invertiert werden.