Zyklische Redundanzprüfung

Dieser Artikel wurde im Projekt Kryptologie zur Verbesserung eingetragen. Hilf mit, ihn zu bearbeiten, und beteilige dich an der Diskussion!

Folgende Verbesserungen wären gut: Hallo. Der vorliegende WP-Artikel ist für "nicht allgemeinverständlich" befunden worden. Es wäre daher eine Hilfe, wenn jemand mit Sachverstand sich dieser Thematik mal annehmen könnte. Grüße --A.Abdel-Rahim (Diskussion) 19:35, 2. Sep. 2023 (CEST)

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.

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 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\cdot x^{7}+0\cdot x^{6}+0\cdot x^{5}+1\cdot x^{4}+1\cdot x^{3}+1\cdot x^{2}+0\cdot x^{1}+1\cdot 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(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 übertragene Prüfsumme befindet.

Beispiel

Es folgt ein Beispiel, in dem für einen Binärcode von 5 Bit der CRC berechnet und überprüft werden soll. Das Generatorpolynom (CRC-Polynom) lautet 110101 ( $1x^{5}+1x^{4}+0x^{3}+1x^{2}+0x^{1}+1x^{0}$ ) und ist somit 5. Grades. Der zu übertragenden Bitfolge, welche auch als Rahmen (engl. frame) bezeichnet wird, werden $n$ Nullen angehängt (Rahmen mit Anhang), wobei $n$ dem Grad des Generatorpolynoms entspricht (bzw. der Anzahl der Bits des Generatorpolynoms minus eins).

Generatorpolynom:	`110101` (zuvor festgelegt)
Rahmen:	`11011` (Nutzdaten)
Rahmen mit Anhang:	`1101100000` (das Generatorpolynom hat $r$ Stellen, also werden $r-1=n$ Nullen ergänzt; hier ist $n=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 dies im ersten Schritt anwendet, wird aus 110110 XOR 110101 die Zahl 000011 (wobei gilt: 1 XOR 1 = 0; 1 XOR 0 = 1; 0 XOR 1 = 1; 0 XOR 0 = 0). Es folgt das vollständige Beispiel:

↓ immer mit der ersten gemeinsamen 1 anfangen

1101100000
110101
------
0000110000
    110101
    ------
     00101 (Rest)

An den Rahmen ohne Anhang wird nun der Rest angehängt. Dieser muss ebenfalls aus $n$ Bit bestehen. Damit hängen wir nun 00101 an den Rahmen an.

Übertragener Rahmen: 1101100101

Diese Nachricht kann jetzt beispielsweise über ein Netzwerk übertragen werden. Wenn die Nachricht beim Empfänger eintrifft, kann dieser überprüfen, ob sie korrekt angekommen ist.

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

Korrekte Übertragung der Nachricht:	`1101100101`
Das Generatorpolynom (wie oben):	`110101`

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

Fehlerhaft übertragene Nachricht (Beispiel):	`1001100101`
Das Generatorpolynom (wie oben):	`110101`

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 wird ein

Schieberegister mit n Bits, dabei ist n der Grad des Erzeugerpolynoms (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 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 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.
ITU-T Recommendation X.25. International Telecommunication Union, Oktober 1996, S. 9, 145, abgerufen am 9. März 2011.
IEEE Std 802.3-2015 Section 1. IEEE Computer Society, 9. September 2015, S. 112, abgerufen am 4. Mai 2018.
ECMA-182

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

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

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

[7] ECMA-182