Codierungstheorie

CRC-Verfahren

 aufwärts

Bei der Speicherung und Übertragung von binär dar­gestellten Daten können durch Störungen einzelne Bits verfälscht werden. Um derartige Fehler zu erkennen, werden an die Daten Prüfbits angehängt.

Das einfachste Mittel zur Erkennung von Fehlern bei der Übertragung von Wörtern aus boolesche Werte+ ist das Anhängen eines Paritätsbits. Dies entspricht einer Codierung  c : boolesche Werte+ Pfeil nach rechts boolesche Werte+    mit

c(x)  =   geschweifte Klammer
x0       falls x eine gerade Anzahl von Einsen enthält
x1    falls x eine ungerade Anzahl von Einsen enthält

für alle x Element boolesche Werte+.

Nach dem Anhängen des zusätzlichen Bits haben alle Codewörter gerade Parität, d.h. eine gerade Anzahl von Einsen. Wird ein Wort mit ungerader Parität empfangen, so muss bei der Übertragung ein Fehler aufgetreten sein (z.B. eine Verfälschung eines einzelnen Bits). Dieser Fehler wird auf diese Weise erkannt.

Wird dagegen ein Wort mit gerader Parität empfangen, so sind zwei Fälle möglich: entweder es handelt sich um ein fehlerfrei übertragenes Codewort, oder es ist ein Fehler aufgetreten, der aber die Parität nicht verändert hat (z.B. durch Verfälschung von zwei Bits). Ein solcher Fehler wird nicht erkannt.

Unter der Annahme, dass Fehler mit einer geraden bzw. ungeraden Anzahl von verfälschten Bits gleich wahrscheinlich sind, werden im Mittel durch diese Art der Codierung 50% aller Fehler erkannt (nämlich diejenigen, in denen eine ungerade Anzahl von Bits verfälscht ist, denn hierdurch wird die Parität verändert), und 50% aller Fehler werden nicht erkannt.

 

Durch Anhängen von mehr als nur einem Prüfbit lässt sich die Fehler­erkennungsrate drastisch steigern. Das CRC-Verfahren stellt eine Methode dar, um diese Prüfbits zu erzeugen.1)

Algebraische Grundlagen

Auf der Menge boolesche Werte werden Ver­knüpfungen entweder oder und · definiert; hierbei entspricht die Verknüpfung entweder oder der Addition modulo 2 bzw. dem logischen Exklusiv-Oder, die Verknüpfung · entspricht der Multi­plikation bzw. dem logischen Und.

Definition:  Ver­knüpfungen  entweder oder  und  ·  in boolesche Werte

 

entweder oder01
001
110
 
  · 01
000
101

Die Menge boolesche Werte bildet mit diesen Operationen einen Körper, d.h. eine mathe­matische Struktur, in der man nach den gewohnten Rechenregeln addieren, subtrahieren, multi­plizieren und dividieren kann.

Im Folgenden betrachten wir Polynome über dem Körper (boolesche Werte, entweder oder, ·).

Die Menge boolesche Werte[x] aller Polynome über boolesche Werte ist ein Ring, d.h. eine Struktur, in der man addieren, subtrahieren und multi­plizieren kann (z.B. ist die Menge ganze Zahlen der ganzen Zahlen auch ein Ring). Die Rechen­operationen in boolesche Werte[x] gehen aus den Rechenregeln des Körpers boolesche Werte hervor.

Beispiel:  (Polynom-Addition in boolesche Werte[x])

f   =   x2 entweder oder x   =   0·x3 entweder oderx2 entweder oderx1 entweder oderx0
g   =   x3 entweder oder x   =   1·x3 entweder oderx2 entweder oderx1 entweder oderx0
 f entweder oder g   =   x3 entweder oder x2  =   1·x3 entweder oderx2 entweder oderx1 entweder oderx0

Beispiel:  (Polynom-Multi­plikation in boolesche Werte[x])

f   =   x3 entweder oder x
g   =   x2 entweder oder 1
   f · g   =   x5 entweder oder x3 entweder oder x3 entweder oder x   =   x5 entweder oder x

Anders als in einem Körper kann man aber in einem Ring nicht dividieren, sondern es gibt (wie in ganze Zahlen) nur eine Division mit Rest.

Satz:  Seien f und g Polynome, g ≠ 0. Dann gibt es eine eindeutige Darstellung

 f  =  q · g + r   mit   grad(r) < grad(g),

d.h. das Polynom r ist der Rest bei Division von f durch g, das Polynom q ist der Quotient.

Beispiel:  (Division mit Rest in boolesche Werte[x])

 f   =   x5
g   =   x2 entweder oder 1
f   =   q · g entweder oder r   =   (x3 entweder oder x) · (x2 entweder oder 1)  entweder oder  x

Definition:  Sei boolesche Werten[xenthalten in boolesche Werte[x] die Menge der Polynome p mit grad(p) < n. Dann entspricht jedem Polynom p Element boolesche Werten[x] in natürlicher Weise ein Wort w Element boolesche Werten, bestehend aus den Koeffizienten von p:

p  =  an-1xn-1 entweder oder . . . entweder oder a0x0

w  =  an-1 . . . a0

Wir identifizieren daher Polynome aus boolesche Werten[x] und Wörter aus boolesche Werten miteinander.

Beispiel:  Sei  p  =  x3 entweder oder x Element boolesche Werte6[x]. Dann ist

w  =  0 0 1 0 1 0

das ent­sprechende Wort aus boolesche Werte6.

Definition:  Sei g ein Polynom aus boolesche Werten[x]. Der von g erzeugte Code C enthalten in boolesche Werten ist die Menge aller Wörter, die Vielfachen von g in boolesche Werten[x] entsprechen. Das Polynom g heißt Generator­polynom von C.

Beispiel:  Sei  g = x entweder oder 1  und n = 4. Die folgende Tabelle zeigt alle Vielfachen von g in boolesche Werte4[x] sowie die ent­sprechenden Codewörter aus boolesche Werte4.

(x entweder oder 1) · 0 =   0 0 0 0 0
(x entweder oder 1) · 1 =   x entweder oder 1 0 0 1 1
(x entweder oder 1) · x =   x2 entweder oder x 0 1 1 0
(x entweder oder 1) · (x entweder oder 1) =   x2 entweder oder 1 0 1 0 1
(x entweder oder 1) · x2 =   x3 entweder oder x2 1 1 0 0
(x entweder oder 1) · (x2 entweder oder 1) =   x3 entweder oder x2 entweder oder x entweder oder 1 1 1 1 1
(x entweder oder 1) · (x2 entweder oder x) =   x3 entweder oder x 1 0 1 0
(x entweder oder 1) · (x2 entweder oder x entweder oder 1) =   x3 entweder oder 1 1 0 0 1

Der erzeugte Code entspricht einem 3-Bit-Binärcode mit angehängtem Paritätsbit.

Der CRC-Algorithmus

Mithilfe des CRC-Algorithmus wird aus einer gegebenen Nachricht in systematischer Weise das zugehörige Codewort konstruiert. Zugrunde gelegt wird das Generator­polynom; das erzeugte Codewort entspricht einem Vielfachen des Generator­polynoms. Dies ist das Kriterium für die Fehlererkennung: alle Wörter, die nicht Vielfachen des Generator­polynoms entsprechen, werden als fehlerhaft zurück­gewiesen.

 

Algorithmus CRC
Eingabe:Nachricht der Länge k (entsprechend einem Polynom p vom Grad < k), Generatorpolynom g vom Grad m
Ausgabe:Codewort der Länge n = k + m (entsprechend einem Polynom h vom Grad < n)
Methode:
  1. multipliziere p mit xm (m Nullen an die Nachricht anhängen):
    1.  f  =  p·xm
  2. teile das Ergebnis f durch das Generatorpolynom g und bilde den Rest r:
    1.  f  =  q·g entweder oder r     mit grad(r) < grad(g)  =  m
  3. addiere r zu f:
    1.  h  =  f entweder oder r  =  q·g entweder oder r entweder oder r  =  q·g

 

Das Ergebnis h entspricht dem gesuchten Codewort; h ist durch g teilbar.

Durch die Addition von r in Schritt 3 findet nur innerhalb der letzten m Stellen eine Veränderung statt, da grad(r) < m ist. Das Codewort besteht also aus der ursprüng­lichen Nachricht mit angehängten m Prüfbits. Damit ist die Dekodierung eines Codewortes sehr einfach: Durch Weglassen der Prüfbits ergibt sich wieder die Nachricht.

Die Fehler­erkennung wird durchgeführt, indem das dem empfangenen Wort ent­sprechende Polynom durch das Generator­polynom geteilt wird. Ist der Rest ungleich Null, so ist ein Fehler aufgetreten.

Beispiel:  Gegeben sei das Generator­polynom g = x5 entweder oder x2 entweder oder x entweder oder 1, entsprechend dem Wort 1 0 0 1 1 1, sowie die Nachricht 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1.

  1. multi­pliziere das Polynom p, das der Nachricht entspricht, mit x5 (5 Nullen an die Nachricht anhängen)
  2. teile das Ergebnis f durch das Generator­polynom g und bilde den Rest r
    10010111001110100000
    100111
    0000101100
        100111
        00101111
          100111
          00100010
            100111
            000101100
               100111
               00101100
                 100111
                 0010110

    (das Wort 1 0 1 1 0 entspricht dem Rest r)

  3. addiere r zu f; das Ergebnis h entspricht dem gesuchten Codewort 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0

Implementierung in Hardware

Die Polynom­division lässt sich, nach dem im obigen Beispiel verwendeten normalen Divisions­verfahren, überraschend einfach in Hardware realisieren.

In Bild 1 dargestellt ist ein Schiebe­register, in das von rechts das zu dividierende Polynom h hinein geschoben wird. Wenn eine 1 in der vordersten Schiebe­register­zelle erscheint, wird das Generator­polynom (in Bild 1 das Polynom 1 0 0 1 1 1) mit dieser 1 multi­pliziert (Und-Gatter) und an der ent­sprechenden Position von dem zu dividierenden Polynom h subtrahiert (Xor-Gatter).2) Der verbleibende Rest zusammen mit der nächst­folgenden Stelle von h wird anschließend um eine Position nach links geschoben. Wenn in der vordersten Schiebe­register­zelle eine 0 erscheint, wird das 0-fache des Generator­polynoms subtrahiert, d.h. es geschieht nichts, außer dass der Schiebe­registerinhalt geschoben wird.

Es ist leicht zu sehen, dass durch diese Hardware genau das o.a. Divisions­verfahren realisiert wird. Wenn das zu dividierende Polynom h zu Ende ist, d.h. keine Stellen mehr in das Schiebe­register eingegeben werden, steht im Schiebe­register der Divisions­rest.

Die Schaltung kann sowohl zur Codierung als auch zur Fehler­erkennung verwendet werden. Zur Fehler­erkennung wird durch eine Oder-Schaltung überprüft, ob der Divisions­rest gleich Null oder ungleich Null ist. Zur Codierung wird der Divisions­rest an die Nachricht angehängt. Vor Beginn einer Division muss das Schiebe­register gelöscht werden.

Bild 1: Schaltung zur Polynomdivision
Bild 1: Schaltung zur Polynomdivision

 

Bild 2: Vereinfachte Schaltung (Linear Feed-Back Shift Register – LFSR)
Bild 2: Vereinfachte Schaltung (Linear Feed-Back Shift Register – LFSR)

Die Schaltung von Bild 1 kann vereinfacht werden, wenn das Generator­polynom festliegt. Dann können alle Und-Gatter mit einer 1 am Eingang durch eine einfache Draht­verbindung ersetzt werden. Alle Und-Gatter mit einer 0 am Eingang liefern am Ausgang konstant 0 und können daher wegfallen; die ent­sprechenden Xor-Gatter mit dieser 0 am Eingang können durch Draht­verbindungen ersetzt werden. Das vorderste Xor-Gatter kann ebenfalls entfallen, da sein Ausgang nicht verwendet wird (er ist im übrigen immer 0).

Bild 2 zeigt die vereinfachte Schaltung, ein rückgekoppeltes Schieberegister (Linear Feed-Back Shift RegisterLFSR), für das Generator­polynom 1 0 0 1 1 1.

Erkennung von Fehlern

Bei Auftreten eines Fehlers werden in dem gesendeten Wort ein oder mehrere Bits invertiert. Wird das Wort als Polynom aufgefasst, entspricht das Invertieren eines Bits der Addition eines Fehler­polynoms, das eine 1 an dieser Position hat.

Beispiel:  Durch Addition des Fehler­polynoms 1 0 1 0 0 werden zwei Bits verfälscht.

 1011000110001
entweder oder        10100
 1011000100101

Das gesendete Polynom h ist durch das Generator­polynom g teilbar. Somit ist das empfangene Polynom h' = hentweder odere genau dann durch das Generator­polynom teilbar, wenn das Fehler­polynom e durch das Generator­polynom teilbar ist.

Wenn also das Fehler­polynom ungleich Null ist und durch das Generator­polynom teilbar ist, wird der Fehler nicht erkannt. Umgekehrt wird der Fehler erkannt, wenn das Fehler­polynom nicht durch das Generator­polynom teilbar ist.

Satz:  Ist xentweder oder1 Teiler des Generator­polynoms g, so wird jede ungerade Anzahl von Fehlern erkannt.

Beweis:  Eine ungerade Anzahl von Fehlern entspricht einem Fehler­polynom e mit einer ungeraden Anzahl von Einsen. Polynome mit einer ungeraden Anzahl von Einsen sind nicht durch xentweder oder1 teilbar. Dies kann man sich leicht anhand des Divisions­verfahrens klarmachen. Damit ist e nicht durch xentweder oder1 teilbar, also erst recht nicht durch g, d.h. der Fehler wird erkannt.

Eine wichtige Eigenschaft des CRC-Verfahrens ist die Fähigkeit, Mehrfach­fehler zu erkennen, bei denen die verfälschten Bits innerhalb eines begrenzten Bereiches auftreten.

Definition:  Ein Fehlerbündel der Länge b ist ein Fehler, bei dem die Position des ersten und des letzten falschen Bits den Abstand b-1 haben. Das einem Fehlerbündel der Länge b ent­sprechende Fehler­polynom lässt sich schreiben als

e  =   e1 · xi   mit grad(e1) = b-1.

Beispiel:  

Nachricht: h = 1 1 0 1 0 0 1 0 1 0 1 0
Fehlerbündel der Länge 5: e = 1 0 0 1 1 0 0 0
verfälschte Nachricht: h entweder oder e = 1 1 0 1 1 0 1 1 0 0 1 0

Es ist   e  =  x7 entweder oder x4 entweder oder x3  =  (x4 entweder oder x entweder oder 1) · x3  =  e1 · x3.

Satz:  Ist x kein Teiler des Generator­polynoms g, so wird jedes Fehlerbündel der Länge bkleiner gleichgrad(g) erkannt.

Beweis:  Es liege ein Fehlerbündel der Länge bkleiner gleichgrad(g) vor. Das ent­sprechende Fehler­polynom sei

e  =  e1 · xi   mit grad(e1) = b-1.

Angenommen, der Fehler wird nicht erkannt. Dann teilt das Generator­polynom g das Fehler­polynom e, d.h. es gilt

 g | e 
 folgt  g | xi · e1
 folgt  g | e1,    da x nicht Teiler von g
 folgt  grad(g)kleiner gleichgrad(e1) = b-1,
 im Widerspruch dazu, dass bkleiner gleichgrad(g) ist.

In der Praxis werden u.a. folgende Generator­polynome verwendet:

CRC-16 (Magnetband) x16 entweder oder x15 entweder oder x2 entweder oder 1
CRC-CCITT (Disketten) x16 entweder oder x12 entweder oder x5 entweder oder 1
CRC-Ethernet x32 entweder oder x26 entweder oder x23 entweder oder x22 entweder oder x16 entweder oder x12 entweder oder x11 entweder oder x10 entweder oder x8 entweder oder x7 entweder oder x5 entweder oder x4 entweder oder x2 entweder oder x entweder oder 1

Literatur

[RF 89]T.R.N. Rao, E. Fujiwara: Error-Control Coding for Computer Systems. Prentice Hall (1989)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das CRC-Verfahren finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

1)  CRC steht für cyclic redundancy check.

2)  Anstelle der DIN-Schalt­symbole sind hier die alten Schalt­symbole verwendet, aus denen die Signal­fluss­richtung (Eingänge/Ausgänge) deutlicher hervorgeht.

 

Weiter mit:   [Huffman-Code]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 10.03.1997   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik