Zyklische Redundanzprüfung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die zyklische Redundanzprüfung (engl. cyclic redundancy check, daher meist CRC) ist ein Verfahren (bzw. eine bestimmte Klasse von Verfahren) aus der Informationstechnik zur Bestimmung eines Prüfwerts für Daten (z. B. Datenübertragung in Rechnernetzen 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 CRC-Wert berechnet. Nach Abschluss der Transaktion wird der CRC-Wert erneut berechnet. Anschließend werden diese beiden Prüfwerte verglichen. CRC ist 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. Zum Beispiel werden bei den meisten Festplatten Übertragungen und Schreib-/Leseoperationen mit CRC-Verfahren geprüft.

CRC-Werte können jedoch nicht die Integrität der Daten 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 z. B. MD5 zum Einsatz kommen.

Inhaltsverzeichnis

1 Verfahren
2 Beispiel
3 Implementierung
- 3.1 Andere Startwerte
- 3.2 Nachbearbeitung
4 Erkannte Fehler
5 Erkannte Fehler (nach der Bitfiltertheorie)
6 Berechnung einer CRC-32-Prüfsumme in C
7 Polynome und Typen
8 Siehe auch
9 Weblinks

[Bearbeiten] Verfahren

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

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

Die Bitfolge der Coderepräsentation der Daten wird durch ein vorher festzulegendes Generatorpolynom (das CRC-Polynom) Modulo (mod) dividiert, 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 Fehler aufgetreten, der in Polynomdarstellung das CRC-Polynom als Faktor hat.

Es ist darauf zu achten, dass es sich bei den Einsen und Nullen nicht um die Repräsentation einer Zahl, sondern um ein Polynom handelt. Das bedeutet, dass die Modulodivision mit Binärzahlen (oder Zahlen allgemein) z. B. 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. Des Weiteren muss der Empfänger dasselbe CRC-Polynom und Rechenverfahren benutzen wie der Sender. Und schließlich muss der Empfänger die Information besitzen, wo im Datenstrom sich die zusätzlich zu den Daten übertragene Prüfsumme befindet.

[Bearbeiten] Beispiel

Es folgt ein Beispiel mit einem Code 9. Grades. Das Generatorpolynom (CRC-Polynom) lautet 10011 ( $1 x 4 + 0 x 3 + 0 x 2 + 1 x 1 + 1 x 0$ ) und ist somit 4. Grades. Der zu übertragenden Bitfolge, Rahmen (engl. frame) genannt, wird eine Kette aus Nullen entsprechend dem Grade des Generatorpolynoms angehängt (Rahmen mit Anhang).

Generatorpolynom:	10011
Rahmen:	1101011011 (Nutzdaten)
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 aus 11010 durch 10011 die Zahl 01001 (0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0). Es folgt das vollständige Beispiel:

11010110110000
10011 <- immer mit der ersten gemeinsamen 1 anfangen
-----     (auch wenn der Rahmen z.B. mit 01000 beginnen würde
 10011     und somit geringwertiger wäre als das Generatorpolynom)
 10011
 -----
  000010110
      10011 
      -----
       010100
        10011
        -----
          1110 (Rest)

Die vorher 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 eintrifft, kann dieser überprüfen, ob sie korrekt angekommen ist.

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

Korrekte Übertragung der Nachricht:	11010110111110
Das Generatorpolynom (wie oben):	10011

11010110111110
10011
-----
 10011
 10011
 -----
  000010111
      10011
      -----
       010011
        10011
        -----
         00000

Der Rest der Division ist gleich Null. Es ist also kein Fehler aufgetreten.

Fehlerhaft übertragene Nachricht (Beispiel):	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:

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 die Nachricht an mehreren Stellen verfälscht wurde)
Der Rest der Division ist ungleich Null und die Nachricht ist fehlerhaft

[Bearbeiten] Implementierung

Das CRC-Verfahren lässt sich sowohl in einfachen Hardware-Bausteinen als auch in Software realisieren. Verwendet wird ein

Schieberegister mit n Bits (etwa ein 32 Bit Schieberegister bei CRC-32) und ein
Bit-Datenstrom (String) beliebiger Länge.

Pseudo-Code des Algorithmus, höchstwertiges Bit ganz links:

Schieberegister := 0000... (Startwert)
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 etwa bei einer CRC-8 für jedes der 256 möglichen Bytes den zugehörigen CRC-Wert enthält, lässt sich obiger Algorithmus auf das achtfache beschleunigen.

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.

[Bearbeiten] 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).

[Bearbeiten] Nachbearbeitung

Ein weiteres Problem ist das Nullproblem. Wird der Datenstrom (einschließlich der CRC) aus irgendeinem Grund gleich Null, so werden Fehler im Empfänger im Standardalgorithmus nicht mehr erkannt, auch wenn Startwerte ungleich Null verwendet werden. Eine Nullfolge ergibt bei der Polynomdivison stets den Wert Null. Wird das CRC-Ergebnis invertiert, kann man das Nullproblem effektiv vermeiden, da eine Folge von Nullen dann das Ergebnis 1111... erzeugt.

Die bekannte CRC-32 verwendet sowohl 1111... als Startwert als auch ein inverses Ergebnis. Bei CRC-16 wird ebenfalls meist 1111.. verwendet, das Ergebnis jedoch nicht invertiert.

[Bearbeiten] Erkannte Fehler

Ist das CRC-Polynom gut gewählt, können mit dem oben beschriebenen Verfahren alle Einbitfehler, jede ungerade Anzahl von verfälschten Bits, sowie alle Bündelfehler der Länge $\leq r$ erkannt werden, wobei $r$ der Grad des CRC-Polynoms ist. Zusätzlich werden alle Fehler (also auch unabhängige Vierbit-, Sechsbit-, Achtbitfehler, u.s.w.) erkannt, deren Polynomdarstellung einen kleineren Grad als das CRC-Polynom hat. Zweibitfehler werden entgegen der landläufigen Meinung nicht grundsätzlich erkannt. Warum das so ist bzw. wie das CRC-Polynom zu wählen ist, folgt aus den kommenden Überlegungen.

Sei $G (x)$ das CRC-Polynom (Generatorpolynom) und $T (x)$ die Polynomdarstellung der um den CRC-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 CRC-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 Einbitfehler 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 $(i - j)$ , 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 15 + x 14 + 1$ den Term $x k + 1$ nicht für jedes $k$ kleiner 32768.

Ist eine ungerade Anzahl von Bits verfälscht, enthält $E (x)$ eine ungerade Anzahl von Termen (z.B. $x 7 + x 2 + 1$ , aber nicht z.B. $x 2 + 1$ ). Wählt man das CRC-Polynom so, dass es $(x + 1)$ als Faktor hat, werden alle Fehler mit einer ungeraden Anzahl von verfälschten Bits erkannt. Beweis: Bei der Division durch ein Polynom mit gerader Parität (= Anzahl der Terme in dem Polynom, also Anzahl der Einsen in der Bitfolge) bleibt die Geradheit oder Ungeradheit der Parität des Divisors erhalten, denn aus 00 wird 11 und umgekehrt und aus 01 wird 10 und umgekehrt. $(x + 1)$ ist das kleinste Polynom mit gerader Parität. Bei $E (x) / G (x)$ wird also stehts $x$ oder $1$ als Rest bleiben, wenn $E (x)$ ungerade Parität hat. Damit ist $E (x)$ nicht durch $G (x)$ teilbar.

Alle Bündelfehler der Länge $k \leq r$ , wobei $r$ der Grad des CRC-Polynoms ist, werden erkannt. Ein Bündelfehler der Länge $k$ lässt sich schreiben als $x^i(x^{k-1}+\cdots+1)=x^ib(x)$ , wobei $i$ bestimmt, wieviele Bitpositionen von der rechten Seite der empfangenen Bitfolge (bzw. des empfangenen Rahmens) der Bündelfehler entfernt ist. Wenn der Fehler erkannt werden soll, muss die Division von $E (x) = x i b (x)$ durch $G (x)$ einen Rest ergeben. Wenn $G (x)$ einen $x 0$ Term enthält, so hat $G (x)$ $x i$ sicher nicht als Faktor. D.h., wenn $G (x) | x i b (x)$ , dann muss $G (x) | b (x)$ . Dies ist jedoch nicht möglich, da per Annahme der Grad von $b (x)$ kleiner ist ( $d e g (b (x)) = k - 1$ ) als der Grad von $G (x)$ . Der Rest kann niemals 0 sein und der Bündelfehler wird erkannt.

[Bearbeiten] Erkannte Fehler (nach der Bitfiltertheorie)

Der Vollständigkeit halber sei hier folgendes ergänzt:

Ein beliebiges Generatorpolynom erkennt sämtliche Bündelfehler, die nicht länger als das Generatorpolynom sind - bis auf eines, nämlich jenes, welches das gleiche Bitmuster hat wie das Generatorpolynom. Das beinhaltet natürlich auch 1-Bitfehler als Bündelfehler der Länge 1.
Ein Generatorpolynom mit gerader Anzahl von Termen erkennt jede ungerade Anzahl von Bitfehlern.
Mit der Bitfiltertheorie lässt sich zeigen, dass nur solche Zweibitfehler nicht erkannt werden, deren Abstand ein Vielfaches des Zyklus der Periode des längsten Bitfilters ist. Bei optimal gewählten Generatorpolynomen vom Grad $n$ mit gerader Anzahl von Termen ist dieser Abstand $2 n - 1 - 1$ , also beispielsweise bei $n = 16$ beträgt diese Periode immerhin 32767, also mehr als 4000 Bytes!
Es lässt sich ähnlich zeigen, dass alle Einbitfehler korrigiert werden können, wenn der Datenblock nicht länger als die eben erwähnte Periode ist. Das folgt daraus, dass die Reste nach Division durch das Generatorpolynom alle verschieden sind - so weit man verschiedene Reste, von denen es höchstens $2 n$ gibt, haben kann. Allerdings lassen u.U. 3-Bitfehler die gleichen Reste, so dass in diesem Fall eine Korrektur das Ergebnis noch mehr verfälschen kann. Allerdings sind 1- und 2-Bitfehler immer mit Sicherheit zu unterscheiden.

Genaueres entnehme man der Referenz Analyse des CRC-Verfahrens mit Bitfiltern. Dort findet sich auch eine Liste optimaler Generatorpolynome verschiedener Grade.

[Bearbeiten] Berechnung einer CRC-32-Prüfsumme in C

Das folgende C-Programm berechnet die CRC-32 des 8 Bits langen Datenstroms 10001100:

   #include <stdio.h>
   #include <stdlib.h>
   #include <inttypes.h>
   #define CRC32POLY 0x04C11DB7 /* CRC-32 Polynom */
   
   int datastream[]={1,0,0,0,1,1,0,0};
   int databits=8;
   
   uint32_t crc32; /* Shiftregister */
   void calc_crc32(int bit)
   {    int hbit;
           hbit=(crc32 & 0x80000000) ? 1 : 0;
        if (hbit != bit)
                crc32=(crc32<<1) ^ CRC32POLY;
        else
                crc32=crc32<<1;
   }
   int main(void)
   {    int i;
   
        crc32=0; 
        for (i=0; i<databits; ++i)  
                calc_crc32(datastream[i]);
        printf("0x%08X\n",crc32);
       return EXIT_SUCCESS; 
   }

CRC-32 Implementierung in der Programmiersprache C

Standards wie Ethernet modifizieren den Algorithmus:

Als Startwert wird 111....111 verwendet (dies entspricht einer Invertierung der ersten 32 Bits im Datenstrom)
Besteht der Datenstrom aus Bytes, wird das niederwertigste Bit zuerst verwendet
Alle Bits im Ergebnis werden invertiert und die Bitreihenfolge wird gedreht, d. h. das höchstwertige Bit erscheint zuerst

Das folgende Programm berechnet eine solche modifizierte CRC:

   #include <stdio.h>
   #include <stdlib.h>
   #include <inttypes.h>
   #define CRC32POLYREV 0xEDB88320 /* CRC-32 Polynom, umgekehrte Bitfolge */
   
   int datastream[]={1,0,0,0,1,1,0,0}; /* ASCII-"1", LSB zuerst */
   int databits=8;
   
   uint32_t crc32_rev; /* Shiftregister */
   void calc_crc32_rev(int bit)
   {    int lbit;
       lbit=crc32_rev & 1;
        if (lbit != bit)
                crc32_rev=(crc32_rev>>1) ^ CRC32POLYREV;
        else
                crc32_rev=crc32_rev>>1;
   }
   int main(void)
   {    int i;
   
        crc32_rev=0xffffffff; /* Startwert (111...) */
        for (i=0; i<databits; ++i)  
                calc_crc32_rev(datastream[i]);
        printf("0x%08X\n",crc32_rev ^ 0xffffffff); /* inverses Ergebnis, MSB zuerst */
       return EXIT_SUCCESS;
   }

Modifizierte CRC32: Startwert 111..., invertiertes Ergebnis mit umgekehrter Bitfolge

[Bearbeiten] 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-24 (IETF RFC2440)	$x 24 + x 23 + x 18 + x 17 + x 14 + x 11 + x 10 + x 7 + x 6 + x 5 + x 4 + x 3 + x + 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$
CRC-64 (ISO 3309)	$x 64 + x 4 + x 3 + 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$

CRCs 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, die 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.

Die Prüfpolynome wurden aus einer Vielzahl von möglichen Polynomen so ausgewählt, dass sich für den damit erzeugten Code "günstige" Eigenschaften ergeben. Beispiel: Wenn ein Polynom eine gerade Anzahl von Termen in x aufweist (CRC16-CCITT:4 und CRC16-IBM:4, nicht aber CRC-4:3), ist das Binom (x + 1) als Faktor darin enthalten. Dieses Binom bewirkt eine "Paritätsprüfung", wodurch im entstehenden Code alle Fehler mit einer ungeraden Anzahl von Fehlerstellen in jedem Fall erkennbar sind.