Zyklische Blockprüfung

Cyclic Redundancy Checksum (CRC) ist ein Fehlererkennungsverfahren, bei dem auf der Basis von Binärzahlen Prüfzeichen durch die Summenbildung der Datengruppen vor ihrer Übertragung gebildet werden.


Die zyklische Blockprüfung basiert auf der Division von Polynomen. Bei diesem Verfahren werden die n Bits eines Datenblocks als Koeffizienten eines Polynoms U(x) vom Grad n-1 interpretiert. Das erzeugte Polynom G(x) ist abhängig vom Grad k. Ein Polynom mit k = 16, wie es die internationale Fernmeldeunion (ITU) vorsieht, sieht folgendermaßen aus: x exp16 + x exp12 + x exp5 + 1.

Das Prinzip der zyklischen Blockprüfung

Verschiedene Generatorpolynome der zyklischen Blockprüfung (CRC)

Verschiedene Generatorpolynome der zyklischen Blockprüfung (CRC)

Vom Prinzip her werden bei der zyklischen Blockprüfung die zu überwachenden Bits nacheinander in ein rückgekoppeltes Schieberegister geschoben. Die Länge wie auch die Anzahl und Lage der Rückkoppelungsanzapfungen sind je nach Verfahren angegeben; so nennt man ein Prüfsummenverfahren mit vierstelligem Register CRC-4. Das Prüfsummenverfahren erkennt Einzelfehler zuverlässig, mehrere Fehler mit großer Wahrscheinlichkeit. Der Empfänger prüft den CRC-Wert eines jeden empfangenen Datenpaketes und entfernt die Prüffunktion vor der Freigabe des Datenpaketes an die Empfangsstation. Für jedes zu übertragende Bitmuster werden entweder 16 oder 32, manchmal auch 64 Prüfbits berechnet und hinter dem Informationsteil im FCS-Feld übertragen.

Die Blockprüfung und das Generatorpolynom

Die Code-ungebundene Fehlersicherung (CRC) erfolgt mittels eines geeigneten Generatorpolynoms, z.B. x exp16 + x exp12 + x exp5 + 1, wobei die Binärzeichen des zu sichernden Datenblocks als Koeffizient des Polynoms verwendet und durch das genannte Polynom Modulo 2 dividiert werden. Der nach der Division verbleibende Rest stellt die Blockprüfzeichenfolge dar und wird mit dem zu übertragenden Datenblock ausgesendet. In der Empfangsstation werden Übertragungsfehler bei Anwendung der obigen Regel mit sehr hoher Wahrscheinlichkeit entdeckt, weil bei der Modulo-2-Division der festgelegten Folge der Binärzeichen durch das Generatorpolynom ein konstanter Rest entstehen sollte und eine Abweichung durch einen Übertragungsfehler sofort in eine andere Restklasse führt.

Die Sicherheit des Verfahrens basiert auf einer möglichst »günstigen« Restklassenzerlegung, die ihrerseits vom gewählten Generatorpolynom abhängt. Je mehr unterschiedliche Restklassen erzeugt werden, desto geringer ist die Wahrscheinlichkeit, dass eine originale Bitfolge und eine verfälschte Bitfolge nach der Operation in die gleiche Restklasse fallen. Die Anzahl der Restklassen wird allerdings auch durch die Anzahl der im Datenpaket für die Darstellung des Restes verfügbaren Bits beschränkt.

Informationen zum Artikel
Deutsch: Zyklische Blockprüfung
Englisch: cyclic redundancy checksum - CRC
Veröffentlicht: 14.11.2013
Wörter: 390
Tags: #Codierung
Links: BCS (block check sequence), Bit (binary digit), Datenblock, Datenpaket, Empfänger