Rechnernetze

Das CRC-Verfahren zur Fehlererkennung

Wir verwenden jetzt Polynome und entsprechende Bitfolgen bzw. Codewörter gleichberechtigt. Für die betrachteten Zeichensequenzen führen wir zunächst die folgenden Bezeichnungen ein:

G(X) = Generatorpolynom vom Grad r

U(X) = Nachrichtenpolynom vom Grad = k-1

D(X) = Rest der Division von U(X)*X^r mit G(X)

C(X) = Übertragenes Codepolynom vom Grad = n-1, wobei n=k+r

E(X) = Fehlerpolynom vom Grad n-1

R(X) = C(X)+E(X): Empfangenes Codepolynom vom Grad n-1

Das Polynomprüfverfahren wird in der Regel auf die folgende Weise durchgeführt:

Sender und Empfänger vereinbaren ein Generatorpolynom G(X) vom Grad r.
Der Sender dividiert das zu übertragende Nachrichtenpolynom U(X)*X^r durch G(X) und bestimmt den Rest dieser Division: D(X), so dass gilt:

U(X)*X^r = G(X)·Q(X) + D(X).

Der Rest D(X) wird zusätzlich zum Nachrichtenpolynom übermittelt:

C(X) = U(X)·X^r + D(X) = G(X)·Q(X).
Das Polynom wird bei der Übertragung evtl. verfälscht; die Verfälschung wird durch das Fehlerpolynom E(X) beschrieben: R(X) = C(X) + E(X).
Der Empfänger dividiert das empfangene Polynom R(X) durch G(X); ist der Rest nicht null, so liegt ein Übertragungsfehler vor.

Die Übertragungsprozedur lässt sich also folgendermaßen formal darstellen:

Zunächst wird das Codepolynom C(X) gebildet, indem an den Nachrichtenvektor der Rest von U(X)*X^r/G(X) angehängt wird. Der Empfänger erhält dieses Polynom, eventuell durch E(X) verfälscht. Nach Division von R(X) mit G(X) gilt:

Also erhalten wir hier den gleichen Rest wie bei der Division von E(X) mit G(X). Es bleibt also genau dann ein Rest, wenn E(X) nach Division mit G(X) einen Rest lässt. Daher werden genau bestimmte Kombinationen von Bitfehlern E(X) von diesem Verfahren erkannt, die nur von G(X) abhängen. Im Abschnitt Bitfilter untersuchen wir genauer, wie man diese Bitfehlerkombinationen beschreiben kann.

Beispiel

Die Bitfolge U= 1010101011 lässt sich mit der Generatorbitfolge G= 110101 prüfen, indem die Bitfolge 101010101100000 durch die Generatorbitfolge G=110101 geteilt wird. Der Rest ist D=11101. Der Sender überträgt die Bitfolge C=101010101111101. Wird diese Bitfolge unverfälscht übertragen, so ist die empfangene Bitfolge R= 101010101111101. Wird dieses durch G=110101 geteilt, so erhalten wir den Rest 0.
U(X) = X⁹ + X⁷ + X⁵ + X³ + X + 1.
G(X) = X⁵ + X⁴ + X² + 1.
U(X)*X⁵ = X¹⁴ + X¹² + X¹⁰ + X⁸ + X⁶ + X⁵.
D(X) = X⁴ + X³ + X² + 1.
C(X) = X¹⁴ + X¹² + X¹⁰ + X⁸ + X⁶ + X⁵ + X⁴ + X³ + X² + 1.
R(X) = X¹⁴ + X¹² + X¹⁰ + X⁸ + X⁶ + X⁵ + X⁴ + X³ + X² + 1.

D'(X) = Rest von C(X) / G(X) = 0.

Sei E(X) = 100000110000. Dann ist R = 101110101001101. Der Rest ist jetzt D'=01011.

E(X) = X¹¹ + X⁵ + X⁴.
R(X) = X¹⁴ + X¹² + X¹¹ + X¹⁰ + X⁸ + X⁶ + X³ + X² + 1.
D'(X) = X³ + X + 1.