Zyklische Redundanzprüfung

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.^[1]

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           000011000

Das Ergebnis dieser Berechnung wird mit jedem Schritt kleiner. Hat das Ergebnis weniger relavante 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   0000110000

Das 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 Polynomdivision mit dem Rahmen 1101100101 und dem Prüfwert 110101 durch:

Rahmen             1101100101
Prüfwert           110101
Division                    /
Zwischenergebnis   0000110101
Prüfwert               110101
Division                    /
Ergebnis                    0

Das 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        10110

Der 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 $\mathrm {Basis} ^{\mathrm {Stellen} }=2^{8}=256$ 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.

Der 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. In beiden Fällen bleibt die Reihenfolge der CRC-Bits unverändert.

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 usw.) 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 erweiterte 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)$ .

Ein-Bit-Fehler

Wenn ein Ein-Bit-Fehler 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.

Zwei isolierte Ein-Bit-Fehler

Sind zwei isolierte Ein-Bit-Fehler 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. Da $G(x)$ nicht durch $x$ teilbar sein kann, reicht es zu fordern, dass $G(x)$ nicht $x^{k}+1$ teilt (für alle $k$ bis zum maximalen Wert von $(i-j)$ , das heißt 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 32767.

Ungerade Anzahl von Fehlern

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) ist die Geradheit oder Ungeradheit der Parität im Divisions-Rest gleich der des Dividenden, 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 stets $x$ oder $1$ als Rest bleiben, wenn $E(x)$ ungerade Parität hat. Damit ist $E(x)$ nicht durch $G(x)$ teilbar.

Bündelfehler

Alle Bündelfehler (eng. Burst) 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^{i}b(x)$ , wobei $i$ bestimmt, wie viele 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.

Da $G(x)$ immer den Term $x^{0}$ enthält, sind $G(x)$ und $x$ teilerfremd. Das heißt, 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 ( $\mathrm {deg} (b(x))=k-1$ ) als der Grad von $G(x)$ . Der Rest kann niemals 0 sein und der Bündelfehler wird erkannt.

Beispiel

Das Generatorpolynom $G(x)=x^{16}+x^{15}+x^{2}+1$ (IBM-CRC-16) lässt sich als $G(x)=(x^{15}+x+1)(x+1)$ faktorisieren. Wegen des Faktors $(x+1)$ ist dieser CRC in der Lage, alle Fehler ungerader Anzahl erkennen zu können. Weiterhin ist die kleinste positive ganze Zahl k, bei welcher das Generatorpolynom $G(x)$ das Polynom $x^{k}+1$ teilt, k=32767. Dies bedeutet, dass alle beliebig angeordneten, zweifachen Bitfehler sicher erkannt werden, wenn die Blocklänge kleiner als 32768 ist. Weiter werden alle Bündelfehler der Länge 16 oder kleiner sicher erkannt. Bündelfehler mit einer Länge von 17 sind mit einer Wahrscheinlichkeit von 0,99997 erkennbar. Alle Bündelfehler mit einer Länge von 18 und mehr sind mit einer Wahrscheinlichkeit von 0,99998 erkennbar.^[2]

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 Ein-Bit-Fehler 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 Ein-Bit-Fehler 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 unter Umständen Drei-Bit-Fehler die gleichen Reste, so dass in diesem Fall eine Korrektur das Ergebnis noch mehr verfälschen kann. Allerdings sind Ein- und Zwei-Bit-Fehler 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.

Berechnung einer CRC-Prüfsumme in C und Pascal bzw. Delphi

CRC-32-Implementierung in der Programmiersprache C

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

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* typedef unsigned __int32 uint32_t; => für MS-VS */

#define CRC32POLY   0x04C11DB7      /* CRC-32 Polynom */

const uint8_t   bitstream[] = { 1,0,0,0,1,1,0,0 };
const int       bitcount    = 8;
uint32_t        crc32       = 0;    /* Schieberegister */

int main ()
{
    for (int i = 0; i < bitcount; i++)
    {
        if ( ((crc32 >> 31) & 1) != bitstream[i])
            crc32 = (crc32 << 1) ^ CRC32POLY;
        else
            crc32 = (crc32 << 1);
    }
    printf ("0x%08X\n", crc32);
}

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

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 niedrigstwertige Bit zuerst verwendet.
Alle Bits im Ergebnis werden invertiert und die Bitreihenfolge wird gedreht, das heißt, das höchstwertige Bit erscheint zuerst.

Das folgende Programm berechnet einen solchen modifizierten CRC-Wert:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define CRC32MASKREV   0xEDB88320   /* CRC-32 Bitmaske, umgekehrte Bitfolge */

const uint8_t   bitstream[] = { 1,0,0,0,1,1,0,0 };  /* ASCII-"1", LSB zuerst */
const int       bitcount    = 8;
uint32_t        crc32_rev   = ~0;                   /* Schieberegister, Startwert (111...) */

int main ()
{
    for (int i = 0; i < bitcount; i++)
    {
        if ((crc32_rev & 1) != bitstream[i])
            crc32_rev = (crc32_rev >> 1) ^ CRC32MASKREV;
        else
            crc32_rev = (crc32_rev >> 1);
    }
    printf("0x%08X\n", ~crc32_rev);          /* inverses Ergebnis, MSB zuerst */
}

IBM-CRC-16 Implementierung in der Programmiersprache Pascal/Delphi

Das folgende Pascal Programm berechnet einen IBM-CRC-16-Wert mit Startwert 111... und umgekehrter Bitfolge über ein Array of Byte und gibt diese aus:

const
  Polynom: Word = $A001;
  Initial: Word = $FFFF;
var
  CRC: Word;
  N, I: Integer;
  B: Byte;

begin
  CRC := Initial;
  for I := Low(Buffer) to High(Buffer) do
  begin
    B := Buffer[I];
    CRC := CRC xor B;
    for N := 1 to 8 do
      if (CRC and 1) > 0 then
        CRC := (CRC shr 1) xor Polynom
      else
        CRC := (CRC shr 1);
  end;
  Showmessage(IntToHex(CRC, 4)); (* Ausgabe *)
end;

CRC-CCITT Implementierung in der Programmiersprache Pascal/Delphi

Das folgende Pascal Programm berechnet einen CRC-CITT-Wert mit Startwert 0 über ein Array of Byte und gibt diese aus:

const
  Polynom: Word = $1021;
  Initial: Word = 0;
var
  CRC: Word;
  N, I: Integer;
  B: Word;

begin
  CRC := Initial;
  for I := Low(Buffer) to High(Buffer) do
  begin
    B := Buffer[I];
    CRC := CRC xor (B shl 8);
    for N := 1 to 8 do
      if (CRC and $8000) <> 0 then
        CRC := (CRC shl 1) xor Polynom
      else
        CRC := CRC shl 1;
  end;
  CRC := CRC and $FFFF;
  Showmessage(IntToHex(CRC, 4)); (* Ausgabe *)
end;

Polynome und Typen

Die Faktorisierungen der nachfolgenden binären Generatorpolynome sind modulo 2 zu betrachten.

Name	Polynom	Länge	MHD	Anmerkungen
CRC-CCITT (CRC-4)	$x^{4}+x+1$	15	3	Identisch mit dem (15,11)-Hamming-Code
USB (CRC-5)	$x^{5}+x^{2}+1$	31	3	Identisch mit dem (31,26)-Hamming-Code
Bluetooth	$x^{5}+x^{4}+x^{2}+1=(x+1)(x^{4}+x+1)$	15		Verkürzter (15,10)-Hamming-Code.
SD/MMC-Card (CRC-7)	$x^{7}+x^{3}+1$	127	3	Identisch mit dem (127,120)-Hamming-Code
CRC-8 (Dallas/Maxim 1-Wire Bus)	$x^{8}+x^{5}+x^{4}+1=(x+1)(x^{7}+x^{6}+x^{5}+x^{3}+x^{2}+x+1)$	127	4	Beschrieben bei Dallas/Maxim^[3]
CRC-8 (ITU-T)	$x^{8}+x^{2}+x+1=(x+1)(x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1)$	127	4	ISDN Header Error Control^[4] (Kap. 7.3.2.2)
CRC-8 (SAE-J1850)	$x^{8}+x^{4}+x^{3}+x^{2}+1$	255	3	Verwendet bei AES/EBU
CRC-12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1=(x+1)(x^{11}+x^{2}+1)$
CAN-CRC	$x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1=(x+1)(x^{7}+x^{3}+1)(x^{7}+x^{3}+x^{2}+x+1)$	127	6
CRC-CCITT (CRC-16)	$x^{16}+x^{12}+x^{5}+1=(x+1)(x^{15}+x^{14}+x^{13}+x^{12}+x^{4}+x^{3}+x^{2}+x+1)$	32767	4	Verwendet bei XMODEM CRC, HDLC, X.25^[5] (Kap. 2.2.7.4, Anhang I)
IBM-CRC-16	$x^{16}+x^{15}+x^{2}+1=(x+1)(x^{15}+x+1)$	32767	4
CRC-DNP (CRC-16)	$x^{16}+x^{13}+x^{12}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{2}+1=$ $(x+1)(x^{15}+x^{14}+x^{13}+x^{11}+x^{8}+x^{5}+x+1)$
CRC-16 VÖV 04.05.1	$x^{16}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x+1=$ $(x^{8}+x^{4}+x^{3}+x^{2}+x+1)(x^{8}+x^{6}+x^{5}+x^{4}+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=$ $(x+1)(x^{23}+x^{17}+x^{13}+x^{12}+x^{11}+x^{9}+x^{8}+x^{7}+x^{5}+x^{3}+1)$
CRC-24 (Mode-S)	$x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{10}+x^{3}+1=$ $(x+1)(x^{6}+x^{5}+x^{4}+x^{2}+1)(x^{17}+x^{16}+x^{15}+x^{13}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{3}+x+1)$			Bei Framelänge bis 112 Bits fehlerkorrigierend bis 5 Bit
CRC-32 (IEEE 802.3)	$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$	$2^{32}-1$	3	Verwendet bei Ethernet^[6]
CRC-64 (ISO 3309)	$x^{64}+x^{4}+x^{3}+x+1$
CRC-64 (ECMA-182^[7])	$x^{64}+x^{62}+x^{57}+x^{55}+x^{54}+x^{53}+x^{52}+x^{47}+x^{46}+x^{45}+x^{40}+x^{39}+x^{38}+x^{37}+x^{35}+x^{33}+$ $x^{32}+x^{31}+x^{29}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21}+x^{19}+x^{17}+x^{13}+x^{12}+x^{10}+x^{9}+x^{7}+x^{4}+x+1=$ $(x+1)^{2}(x^{15}+x+1)(x^{15}+x^{10}+x^{5}+x+1)(x^{15}+x^{12}+x^{3}+x+1)(x^{17}+x^{14}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{5}+x^{4}+x^{3}+1)$			Verwendet bei XZ Utils

Die Spalte MHD gibt die minimale Hamming-Distanz an, die zwei Bitfolgen mit gültigem CRC-Wert unterscheidet. Ein CRC-Algorithmus kann also jeden Fehler erkennen, der innerhalb der angegebenen maximalen Länge weniger als MHD Bit-Positionen betrifft. Wird die maximale Länge überschritten, gibt es bei jedem CRC-Algorithmus Zwei-Bit-Fehler, die nicht erkannt werden (z. B. zwei Fehler, die genau Länge Positionen auseinanderliegen).

CRC-Werte 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.

Siehe auch

Weblinks

CRC JavaScript Rechner und C-Code
Online CRC Rechner für die gängigsten CRCs mit CRC Berechnungsroutinen in C++ und ANSI C zum Download engl.
A Painless Guide to CRC Error Detection Algorithms (Memento vom 19. Mai 2019 im Internet Archive) engl.
The CRC++ Project engl Eine Implementierung von CRC in C++ mit Template-Klassen
Fehlererkennung mittels CRC
Analyse des CRC-Verfahrens mit Bitfiltern

Einzelnachweise

↑ W. W. Peterson: Cyclic Codes for Error Detection. In: Proceedings of the IRE, Vol. 49, No. 1, 1961, S. 228–235
↑ Todd K. Moon: Error Correction Coding. John Wiley & Sons, 2005, ISBN 0-471-64800-0, S. 149.
↑ Dallas/Maxim DS18S20, S. 6 (Memento vom 1. April 2010 im Internet Archive) (PDF; 250 kB) auf datasheets.maxim-ic.com
↑ ITU-T Recommendation I432.1. International Telecommunication Union, Februar 1999, S. 5–6, abgerufen am 9. März 2011 (englisch).
↑ ITU-T Recommendation X.25. International Telecommunication Union, Oktober 1996, S. 9, 145, abgerufen am 9. März 2011 (englisch).
↑ IEEE Std 802.3-2015 Section 1. IEEE Computer Society, 9. September 2015, S. 112, archiviert vom Original am 4. Mai 2018; abgerufen am 4. Mai 2018.
↑ ECMA-182

[1] W. W. Peterson: Cyclic Codes for Error Detection. In: Proceedings of the IRE, Vol. 49, No. 1, 1961, S. 228–235

[2] Todd K. Moon: Error Correction Coding. John Wiley & Sons, 2005, ISBN 0-471-64800-0, S. 149.

[3] Dallas/Maxim DS18S20, S. 6 (Memento vom 1. April 2010 im Internet Archive) (PDF; 250 kB) auf datasheets.maxim-ic.com

[4] ITU-T Recommendation I432.1. International Telecommunication Union, Februar 1999, S. 5–6, abgerufen am 9. März 2011 (englisch).

[5] ITU-T Recommendation X.25. International Telecommunication Union, Oktober 1996, S. 9, 145, abgerufen am 9. März 2011 (englisch).

[6] IEEE Std 802.3-2015 Section 1. IEEE Computer Society, 9. September 2015, S. 112, archiviert vom Original am 4. Mai 2018; abgerufen am 4. Mai 2018.

[7] ECMA-182

[1]

[2]

[3]

[4]

[5]

[6]

[7]