Zyklische Redundanzprüfung

Die zyklische Redundanzprüfung (ZRP) (englisch Cyclic redundancy check, daher häufig CRC) ist ein Verfahren (bzw. eine bestimmte Klasse von Verfahren) aus der Informationstechnik zur Bestimmung eines Prüfwerts für Daten (z. B. Netzwerkverkehr oder eine Datei), um Fehler bei der Übertragung oder Duplizierung von Daten erkennen zu können.

Vor Beginn der Übertragung bzw. Kopie eines Blocks der Daten wird ein ZRP-Wert berechnet. Nach Abschluss der Transaktion wird der ZRP-Wert erneut berechnet. Anschließend werden diese beiden Prüfwerte verglichen. ZRP sind so ausgelegt, dass Fehler bei der Übertragung der Daten, wie sie beispielsweise durch Rauschen auf der Leitung verursacht werden könnten, fast immer entdeckt werden.

ZRPs können jedoch nicht die Integrität der Daten bestätigen. D. h., es ist verhältnismäßig leicht, durch beabsichtigte Modifikation einen Datenstrom zu erzeugen, der den gleichen ZRP-Wert wie eine gegebene Nachricht hat. Wenn eine solche Sicherheit gefordert ist, müssen kryptografische Hash-Funktionen wie z. B. MD5 zum Einsatz kommen.

Verfahren

ZRP beruht auf Polynomdivision: Die Folge der zu übertragenden Bits wird als dyadisches Polynom betrachtet. Beispiel: Die Bitfolge 10011101 entspricht dem Polynom

$1x^{7}+0x^{6}+0x^{5}+1x^{4}+1x^{3}+1x^{2}+0x^{1}+1x^{0}=x^{7}+x^{4}+x^{3}+x^{2}+1$

Die Bitfolge der Coderepräsentation der Daten wird durch ein vorher festzulegendes Generatorpolynom (das ZRP-Polynom) mod 2 dividiert, wobei ein Rest bleibt. Dieser Rest ist der ZRP-Wert. Bei der Übertragung des Datenblocks hängt man den ZRP-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 ZRP-Wert als Binärfolge interpretiert, erneut durch das ZRP-Polynom mod 2 geteilt und der Rest ermittelt. Wenn kein Rest bleibt, ist entweder kein Fehler aufgetreten oder es ist ein Fehler aufgetreten, der in Polynomdarstellung das ZRP-Polynom als Faktor hat.

Die Datenübertragung erfordert bestimmte unerlässliche Übereinkommen. Zum einen muss dem Empfänger bewusst sein, daß überhaupt eine gesicherte Übertragung der Ursprungsdaten stattfinden soll. An der Art des eintreffenden Datenstromes allein ist dies nicht zu erkennen. Des weiteren muss der Empfänger das selbe ZRP-Polynom und Rechenverfahren benutzen wie der Sender. Und schliesslich muss der Empfänger die Information besitzen, wo sich die zusätzlich zu den Daten übertragene Prüfsumme befindet.

Erkannte Fehler

Ist das ZRP-Polynom gut gewählt, können mit dem oben beschriebenen Verfahren alle Einbit- und Zweibitfehler, jede ungerade Anzahl von verfälschten Bits sowie alle Bündelfehler der Länge $\leq r$ erkannt werden, wobei $r$ der Grad des ZRP-Polynoms ist. Warum dass so ist bzw. wie das ZRP-Polynom zu wählen ist, folgt aus den kommenden Überlegungen.

Sei $G(x)$ das ZRP-Polynom (Generatorpolynom) und $T(x)$ die Polynomdarstellung der um den ZRP-Wert erweiterten zu übertragenden Bitfolge. Wenn ein Fehler bei der Übertragung auftritt, kommt (in Polynomdarstellung) beim Empfänger nicht $T(x)$ , sondern $T(x)+E(x)$ an. Die zu $E(x)$ gehörende Bitfolge hat an jeder Bitposition, die bei der zu übertragenden Bitfolge invertiert bzw. verfälscht wurde, eine 1. Wenn der Empfänger die um den ZRP-Wert erweiterten Bitfolge erhält, berechnet er $(T(x)+E(x))/G(x)$ . Da $T(x)/G(x)=0$ (per Definition von $T(x)$ ), ist das Ergebnis $E(x)/G(x)$ .

Wenn ein Einbitfehler aufgetreten ist, gilt $E(x)=x^{i}$ , wobei $i$ bestimmt welches Bit invertiert ist. Wenn nun $G(x)$ zwei oder mehr Terme enthält, wird $G(x)$ niemals $E(x)$ teilen.

Sind zwei isolierte Zweibitfehler aufgetreten, gilt $E(x)=x^{i}+x^{j}$ , wobei $i>j$ . Klammert man $x^{j}$ aus, lässt sich dies auch als $E(x)=x^{j}(x^{i-j}+1)$ schreiben. Angenommen, $G(x)$ ist nicht durch $x$ teilbar (z.B. wenn $G(x)$ $x^{0}$ enthält), reicht es zu fordern, dass $G(x)$ nicht $x^{k}+1$ teilt (für alle $k$ bis zum maximalen Wert von $(j-i)$ , i.e. der maximalen Rahmenlänge). Einfache Polynome geringen Grades, die eine sichere Übertragung für lange Rahmen ermöglichen, sind bekannt. Zum Beispiel teilt $x^{1}5+x^{1}4+1$ $x^{k}+1$ nicht für jedes $k$ kleiner 32768.

Ist eine ungerade Anzahl von Bits verfälscht, enthät $E(x)$ eine ungerade Anzahl von Termen (z.B. $x^{7}+x^{2}+1$ , aber nicht $x^{2}+1$ ). Wählt man das ZRP-Polynom so, dass es $(x+1)$ als Faktor hat, werden alle Fehler mit einer ungeraden Anzahl von verfälschten Bits erkannt. Um zu sehen, warum das so ist, führen wir einen kurzen und einfachen Widerspruchsbeweis. Angenommen $E(x)$ hat eine ungerade Anzahl von Termen und ist durch $(x+1)$ teilbar. Dann lässt sich $E(x)$ nach einer Faktorisierung auch darstellen durch $E(x)=(x+1)Q(x)$ . Wenn jetzt für $x$ die Zahl $1$ eingesetzt wird, gilt $E(1)=(1+1)Q(1)=0*Q(1)=0$ , da in der Polynomarithmetik modulo 2 $1+1=0$ . Wenn nun aber $E(x)$ eine ungerade Anzahl von Termen hat, so müsste bei dem Einsetzen von $1$ für $x$ als Ergebnis die Zahl $1$ herauskommen. Widerspruch! Folglich ist kein Polynom mit einer ungeraden Anzahl von Termen durch $(x+1)$ teilbar.

Alle Bündelfehler der länge $\leq r$ , wobei $r$ der Grad des ZRP-Polynoms ist, werden erkannt. Ein Bündelfehler der Länge $k$ lässt sich schreiben als $x^{i}(x^{k-1}+\cdots +1)$ , wobei $i$ bestimmt, wieviele Bitpositionen von der rechten Seite der empfangenen Bitfolge (bzw. des empfangenen Rahmens) der Bündelfehler entfernt ist. Wenn $G(x)$ einen $x^{0}$ Term enthält, so hat $G(x)$ $x^{i}$ sicher nicht als Faktor. Wenn zusätzlich der Grad von $(x^{k-1}+\cdots +1)$ kleiner ist als der Grad von $G(x)$ , kann der Rest niemals 0 sein.

Beispiel

Es folgt ein Beispiel mit einem Code n-ten Grades, wobei n=9. Das Generatorpolynom lautet 10011 ( $1x^{4}+0x^{3}+0x^{2}+1x^{1}+1x^{0}$ ) und ist somit 4-ten Grades. Der zu übertragenden Bitfolge, Rahmen (engl. Frame) genannt, wird eine Kette aus Nullen entsprechend des Grades des Generatorpolynoms angehängt (siehe Rahmen mit Anhang).

Generatorpolynom:	10011
Rahmen:	1101011011
Rahmen mit Anhang:	11010110110000 (das Generatorpolynom hat r-Stellen, also werden r-1 Nullen ergänzt; hier ist r=5)

Nun wird der Rahmen mit Anhang von links her durch das Generatorpolynom dividiert. Dabei wird ausschließlich das exklusive OR (XOR) verwendet. Wenn man stellenweise dividiert wird also aus 11010 durch 10011: 01001 (0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0). Es folgt das vollständiges Beispiel

11010110110000
10011
-----
 10011
 10011
 -----
  000010110
      10011 <- bei der ersten 1 wieder anfangen!
      -----
       010100
        10011
        -----
         01110 (Rest)

Die früher angehängte Null-kette wird nun durch den Rest ersetzt:

übertragener Rahmen: 11010110111110

Diese Nachricht kann jetzt z.B. über ein Netzwerk übertragen werden. Wenn die Nachricht beim Empfänger ankommt, kann dieser überprüfen, ob die Nachricht korrekt bei ihm angekommen ist.

Durch Division durch das Generatorpolynom kann jetzt die fehlerhafte Übertragung erkannt werden:

Ein Beispiel für eine fehlerhafte Nachricht:	11110110111110
Das Generatorpolynom (wie oben):	10011

11110110111110
10011
-----
 11011
 10011
 -----
  10001
  10011
  -----
   0010011
     10011
     -----
      00001110

Der Rest der Division (1110) ist ungleich Null. Also ist ein Fehler aufgetreten. Bei der Überprüfung auf Richtigkeit können folgende Fälle auftreten:

1. Der Rest der Division ist Null und die Nachricht ist richtig.
2. Der Rest der Division ist Null und die Nachricht ist fehlerhaft (dieser Fall kann durchaus
   vorkommen, wenn die Nachricht an mehreren Stellen verfälscht wird).
3. Der Rest der Division ist ungleich Null und die Nachricht ist fehlerhaft.

Implementierung

Das ZRP-Verfahren lässt sich in einfachen Hardware-Bausteinen realisieren. Aber auch in Software ist ZRP leicht zu implementieren. Pseudo-Code des wesentlichen Teils des Algorithmus, höchstwertiges Bit ganz links:

Schieberegister := Startwert (meist 0000... oder 1111...)
solange Bits im String verbleiben:
  falls das am weitesten links stehende Bit vom Schieberegister 
        ungleich zum nächsten Bit aus dem String ist:
    Schieberegister := (Schieberegister linksschieben um 1, rechtes Bit 0) 
                      xor CRC-Polynom
  andernfalls:
    Schieberegister := Schieberegister linksschieben um 1, rechtes Bit 0
Schieberegister enthält das Ergebnis

Durch Verwendung einer Tabelle, die für jedes der 256 möglichen Bytes den zugehörigen ZRP-Wert enthält, lässt sich obiger Algorithmus auf das achtfache beschleunigen.

Die Operationen Linksschieben und Exklusiv-Oder machen die ZRP hervorragend geeignet zur Verwendung in Logikschaltungen. Die ZRP 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 die ZRP genauso wie der Sender berechnen, jedoch unter Einbeziehung der ZRP. Das Ergebnis inclusive der ZRP muss dann gleich Null sein, sonst enthält der Strom Bitfehler.

ZRP-Typen werden oft anhand des als Divisor verwendeten Polynoms unterschieden (im Hexadezimal-Format). Eines der meistverwendeten ZRPs (u. a. von Ethernet, FDDI, ZIP und PNG benutzt) ist das Polynom 0x04C11DB7, bekannt als CRC-32. Es stellte sich heraus, daß einige Polynome "besser" schützen als andere. Für ZRP häufig verwendete Polynome sind das Ergebnis umfangreicher mathematischer und empirischer Analysen und keine Zufallszahlen, auch wenn sie so aussehen.

Polynome und Typen

CRC-CCITT (CRC-4)	$x^{4}+x+1$
CRC-CCITT (CRC-16)	$x^{16}+x^{12}+x^{5}+1$
IBM-CRC-16	$x^{16}+x^{15}+x^{2}+1$
CRC-32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$
CAN-CRC	$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1$
Bluetooth	$x^{5}+x^{4}+x^{2}+1$

ZRPs werden häufig als Prüfsummen bezeichnet, obwohl die Berechnung der Kontrollbits nicht nur durch (gewöhnliche) Addition geschieht. Der Begriff Prüfsumme wurde zuerst im Zusammenhang mit Paritätsbits benutzt, welche sich als eine echte Summe über $\mathbb {Z} _{2}$ berechnen lassen. Dabei hat sich der Begriff so sehr eingebürgert, dass er als Bezeichnung für die Berechnung von allgemeinen Kontrollbits übernommen wurde.

Siehe auch: Hash-Funktion und die dort genannten Verfahren, DFÜ.

Weblinks

http://www.jonelo.de/java/jacksum/index_de.html
- Jacksum (Java Checksum) ist ein freies und plattformunabhängiges Programm, u. a. zur Berechnung und Verifizierung von Prüfsummen, CRCs und Message Digests (mit Java-Quelltext)
A Painless Guide to CRC Error Detection Algorithms
Understanding Cyclic Redundancy Check