Wie funktioniert CRC?

CRC - Der Cyclic Redundancy Code

Die CRC-Pruefsumme (== Cyclic Redundancy Code) basiert darauf, dass man Bitstring (also Folgen von 0 und 1) als Polynome mit den Koeffizienten 0 und 1 interpretiert. Bei k Bits hat man also k Terme, von x^(k-1) bis x^0.

Beispiel:

                         5   4   0
    110001      ->      x + x + x

So, mit diesen Polynomen kann man nun auch Arithmetik betreiben, und zwar modulo 2, d.h. bei Addition und Subtraktion _ohne_ Uebertraege. Beispiel:

Ebenso kann man solche Polynome durcheinander dividieren, wie man es mit sonstigen Binaerzahlen auch macht. Dabei wird die Subtraktion aber wieder modulo 2 ausgefuehrt. (Wird gleich an einem Beispiel hoffentlich klarer.)

Fuer die Berechnung einer CRC-Pruefsumme nun (darum geht's ja eigentlich) muessen Sender und Empfaenger ein Generator-Polynom definieren (das muss bestimmte Eigenschaften haben, s.u.). Dieses Generatorpolynom habe m Bits. Die Idee der CRC-Pruefsumme ist nun, einem gegebenen Rahmen von Datenbits durch m Bits so zu ergaenzen, dass das Polynom aus Datenbits und Pruefsumme durch das Generatorpolynom teilbar ist.

Der Algorithmus zur Berechnung der CRC-Pruefsumme ergibt sich daraus.

Bezeichnungen: G(x) Generatorpolynom, M(x) Polynom des zu uebertragenden Frames.

r sei der Grad der Generatorpolynoms G(x). An den zu uebertragenden Frame (m Bits) werden nun zunaechst r 0-Bits am Low-Order-Ende angehangen. Der erweiterte Frame hat jetzt also m+r Bits, entsprechend dem Polynom x^r * M(x).
Dividiere den Bitstring x^r * M(x) durch den Bitstring des Generatorpolynoms G(x) mit modulo-2-Division.
Subtrahiere den Divisionsrest (immer r oder weniger Bits) vom dem x^r * M(x) entsprechenden Bitstring (immer modulo 2), das Resultat ist der zu uebertragende Bitstring des Frames mit Pruefsumme. Das wollen wir mal T(x) nennen.

Alles verstanden? Nein? Dann mal ein Beispiel, dass das hoffentlich klar werden laesst:

Wir nehmen einen Datenframe 1101011011 und ein Generatorpolynom G(x) = x^4 + x + 1.

Frame:          1 1 0 1 0 1 1 0 1 1
Generator:      1 0 0 1 1
Frame 0-Bits:   1 1 0 1 0 1 1 0 1 1 0 0 0 0

Division:

    1 1 0 1 0 1 1 0 1 1 0 0 0 0  /  1 0 0 1 1  =  1 1 0 0 0 0 1 0 1 0
    1 0 0 1 1 ------------------------------------+ | |             |
    ---------                                       | |             |
      1 0 0 1 1                                     | |             |
      1 0 0 1 1 ------------------------------------+ |             |
      ---------                                       |             |
        0 0 0 0 1                                     |             |
        0 0 0 0 0 ------------------------------------+    . . .    |
        ---------                                                   |
          0 0 0 1 0                                                 |
          0 0 0 0 0                                                 |
          ---------                                                 |
            0 0 1 0 1                                               |
            0 0 0 0 0                                               |
            ---------                                               |
              0 1 0 1 1                                             |
              0 0 0 0 0                                             |
              ---------                                             |
                1 0 1 1 0                                           |
                1 0 0 1 1                                           |
                ---------                                           |
                  0 1 0 1 0                                         |
                  0 0 0 0 0                                         |
                  ---------                                         |
                    1 0 1 0 0                                       |
                    1 0 0 1 1                                       |
                    ---------                                       |
                      0 1 1 1 0                                     |
                      0 0 0 0 0 ------------------------------------+
                      ---------
                        1 1 1 0  =  Rest

Daraus ergibt sich der Frame mit Pruefsumme: 1 1 0 1 0 1 1 0 1 1 1 1 1 0

Der Empfaenger kann nun ueberpruefen, ob der Frame korrekt uebertragen wurde, in dem er T(x) durch G(x) dividiert, das Ergebnis muss 0 sein.

Wie sieht es denn nun aus, wenn die Uebertragung gestoert wird? Nehmen wir an, dass statt des erwarteten Frames T(X) der fehlerhafte Frame T(x) + E(x) ankommt. Jedes 1-Bit in E(x) entspricht einem Bitfehler. Ein einzelnes 1-Bit ist ein Singlebitfehler, ein Burst ist eine 1, gefolgt von 0 oder 1 und dann wieder einer 1, wobei alle anderen Bits in E(x) null sind.

Welche Bitfehler koennen nun erkannt werden?

Singlebitfehler: E(x) = x^i
G(x) muss mindestens 2 Terme haben, dann wird er erkannt
2 Singlebitfehler: E(x) = x^i + x^j i > j
G(x) darf nicht durch x^k + 1 teilbar sein, fuer k=1 ... Framelaenge
Ungerade Anzahl von Bitfehlern:
G(x) muss den Faktor x + 1 enthalten, dann werden diese erkannt (merkwuerdig)
Bursts:
Am wichtigsten: Ein Polynom des Grads r erkennt alle Burstfehler einer Laenge <= r, dazu muss G(x) einen x^0-Term enthalten. Bursts der Laenge r + 1 werden mit einer Wahrscheinlichkeit von 0.5^(r-1) nicht erkannt.

Die Gesamtwahrscheinlichkeit, dass ein gestoerter Frame durchkommt, ist 0.5^r, unter der Voraussetzungen, dass alle Bitmuster gleichmaessig verteilt sind.

Standard-Polynome:

CRC-12 x^12 + x^11 + x^3 + x^2 + x^1 + 1
CRC-16 x^16 + x^15 + x^2 + 1
CRC-CCITT x^16 + x^12 + x^5 + 1

So, das war die graue Theorie. In der Praxis lassen sich die CRC-Pruefsummen gluecklicherweise einfach mit Schiebe- und XOR-Operationen berechnen, man kann auch eine Tabelle zu Hilfe nehmen, die das ganze stark beschleunigt.

Quelle: u.a.

Andrew S. Tanenbaum, Computer Networks, Prentice Hall (bei Amazon bestellen)
bzw. auf deutsch
Andrew S. Tanenbaum, Computernetzwerke, Pearson Studium (bei Amazon bestellen)

Anhang:
Am 19.09.2002 erreichte mich eine Mail von Uwe Hahn, der mich auf ein paar Ungereimtheiten hinwies. Er gab mir freundlicherweise die Erlaubnis, diese Mail hier anzufügen, um damit diese Hinweise an Euch weiterzugeben.

Hallo Jan,
vor längerer Zeit hast du mal eine kurze Erläuterung des CRC-Verfahrens ins Internet gestellt. Bei der Erkennung von einer ungeraden Anzahl von Bitfehlern hast du die Regel mit einem "merkwürdig" gekennzeichnet. Und ich dachte mir, das möchte ich genauer wissen ...
Nach Andrew Tanenbaum kann eine ungerade Anzahl von Bitfehlern erkannt werden, wenn das Generatorpolynom x + 1 (= 11 bin) als Primfaktor enthält. Wenn wir jetzt z.B. einen der Standard CRC-Codes nehmen und eine Polynomdivision mit modulo 2 ausführen, dann ist der Rest immer 0. Das heißt also, dass 11 ein Primfaktor des Polynoms ist. Wenn also G(x) eine gerade Anzahl von Einsen enthält, dann ist 11 immer ein Primfaktor von G(x).
Noch etwas: Bei Punkt 2. muss es heißen: x^k + 1 darf nicht durch G(x) teilbar sein !!!!
Und zur Ergänzung: Bursts der Länge größer r+1 werden mit einer Wahrscheinlichkeit von (0.5)^r nicht erkannt.
Ich hoffe, das ich zur Auflösung der "merkwürdigen" Bedingung beitragen konnte.
Grüße
Uwe

Jan Haase, <haase@cs.uni-frankfurt.de> Zurück zu meiner Homepage