Polynomkodierung

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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 die 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. SHA zum Einsatz kommen.

Inhaltsverzeichnis

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

Verfahren

CRC beruht auf Polynomdivision: Die Folge der zu übertragenden Bits wird als dyadisches Polynom betrachtet. Beispiel: Die Bitfolge 10011101 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) 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 (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 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.

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 geringerwertig wäre als das Generatorpolynom)
 10011
 -----
  000010110
      10011 
      -----
       010100
        10011
        -----
          1110 (Rest)

An den Rahmen ohne Anhang wird nun der Rest angehängt:

ü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 das Fehlerpolynom ein vielfaches des Generatorpolynoms ist)
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)

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.

Pseudocode 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
  nächstes Bit im String
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.

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

Ein weiteres Problem ist das Nullproblem. Das Nullproblem gibt es in zweierlei Ausführung:

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, und 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 Generatorpolymon 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, 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 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)$ .

Einbitfehler

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.

Zwei isolierte Einbitfehler

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)$ , d.h. 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.

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) 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 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^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.

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)$ nicht $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. Weiters 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 ^[1].

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.

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 = 0; /* Schieberegister */
/*__int32 crc32 = 0; => für MS VS  */
 
int main(void)
{   int i;
    for (i=0; i<databits; ++i)
        if (((crc32 & 0x80000000) ? 1 : 0) != datastream[i]) 
             crc32=(crc32<<1) ^ CRC32POLY;
        else 
             crc32<<=1;
    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=0xffffffff; /* Schieberegister, Startwert (111...) */
 
int main(void)
{   int i;
    for (i=0; i<databits; ++i)
        if ((crc32_rev & 1) != datastream[i])
             crc32_rev=(crc32_rev>>1) ^ CRC32POLYREV; 
        else 
             crc32_rev=crc32_rev>>1;
    printf("0x%08X\n",crc32_rev ^ 0xffffffff); /* inverses Ergebnis, MSB zuerst */
    return EXIT_SUCCESS;
}

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

Polynome und Typen

CRC-CCITT (CRC-4)	$x 4 + x + 1$
CRC-CCITT (CRC-8)	$x 8 + x 5 + x 4 + 1$
CRC-CCITT (CRC-16)	$x 16 + x 12 + x 5 + 1$
CRC-XModem (CRC-XModem)	$x 16 + x 15 + x 10 + x 3$
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.

Einzelnachweise

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

Siehe auch

Weblinks

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Academic dictionaries and encyclopedias

Polynomkodierung

Inhaltsverzeichnis

Verfahren

Beispiel

Implementierung

Andere Startwerte

Nullproblem und Nachbearbeitung

Erkannte Fehler

Einbitfehler

Zwei isolierte Einbitfehler

Ungerade Anzahl von Fehlern

Bündelfehler

Beispiel

Erkannte Fehler (nach der Bitfiltertheorie)

Berechnung einer CRC-32-Prüfsumme in C

Polynome und Typen

Einzelnachweise

Siehe auch

Weblinks

Share the article and excerpts

Academic dictionaries and encyclopedias

Deutsch Wikipedia

Polynomkodierung

Inhaltsverzeichnis

Verfahren

Beispiel

Implementierung

Andere Startwerte

Nullproblem und Nachbearbeitung

Erkannte Fehler

Einbitfehler

Zwei isolierte Einbitfehler

Ungerade Anzahl von Fehlern

Bündelfehler

Beispiel

Erkannte Fehler (nach der Bitfiltertheorie)

Berechnung einer CRC-32-Prüfsumme in C

Polynome und Typen

Einzelnachweise

Siehe auch

Weblinks

Share the article and excerpts

Direct link