Netzwerk-Grundlagen, Teil 2

Zyklische Redundanzprüfung

Bei dem Verfahren der zyklischen Redundanzprüfung (Cyclic Redundancy Check CRC) ist die Prüfoperation im Prinzip eine Division. Betrachten wir zunächst ein Beispiel mit Dezimalzahlen. Übertragen werden soll eine große Dezimalzahl wie etwa 35628828297292. Weiterhin wählt man einen Divisor D aus. Nimmt man dafür beispielsweise den Wert 17 und führt die Division aus, so erhält man bei ganzzahliger Division (Modulo-Operator % in C) einen Rest von 8. Der Sender kann damit zu der großen Zahl als Prüfwert die 8 senden. Der Empfänger rechnet dann zur Kontrolle (35628828297292-8)%17. Bleibt bei der Division ein Rest übrig, so liegt ein Übertragungsfehler vor.

Schon an diesem einfachen Beispiel werden einige Grundeigenschaften deutlich. Zunächst einmal sind nicht alle Divisoren gleich gut geeignet für diesen Zweck. Beispielsweise wäre 10 ein schlechter Divisor, da sich dann nur Fehler an der letzten Stelle auswirken würden.

Weiterhin wird ein größerer Divisor einen besseren Schutz bieten. Allerdings muss dann entsprechend mehr Platz für den Rest vorgehalten werden. Der Rest kann maximal den Wert D-1 annehmen. Der Divisor selbst hat sinnvollerweise einen festen Wert und braucht dann nicht mehr übertragen zu werden.

Die Übertragung dieses Ansatzes auf Binärdaten beruht auf der Interpretation von Bitfolgen als Polynomen. Für eine Bitfolge abcdef schreibt man:

Dabei genügt es, die Terme mit Einsen anzugeben. Für die Bitfolge 100101 erhält man dann zum Beispiel:

Die Prüfbits werden durch eine Division von solchen Polynomen bestimmt. CRC benutzt eine polynomiale Modulo-2-Arithmetik. In dieser Arithmetik reduziert sich die Subtraktion auf eine XOR-Operation. Die Division lässt sich – wie bei der üblichen Division – durch fortgesetzte Subtraktion ausführen.