Rechnernetze

Implementierung der Polynomdivision

Der Kodierer bzw. Dekodierer muss offenbar eine Polynom-Division durchführen. Da heutige Hardware dann besonders günstig ist, wenn sie in großen Stückzahlen hergestellt wird, sollten Sender und Empfänger – so weit möglich – die gleiche Hardware verwenden. Außerdem sollte die Kodierung bzw. Dekodierung so schnell sein, dass sie die Übertragung nicht wesentlich behindert. Die heute übliche Realisierung geschieht durch ein Schieberegister (nach Peterson und Brown, 1961), welches auf der Sende- und Empfangsseite gleich aufgebaut ist. Es genügt daher den oben genannten Ansprüchen. Darüber hinaus ist natürlich stets auch eine Softwarelösung möglich.

Bei der Polynomdivision wird der Divisor G(X) an dem Dividenden R(X) beginnend mit der höchsten Stelle entlanggeschoben und gegebenenfalls G(X)·X^s addiert. Bei dem Schieberegisterverfahren wird genauso vorgegangen, wobei nur jener Bereich (r Bits) im Register erfasst wird, der von G(X) verändert werden kann.

Sind die höchsten r Bits von R(X) in das Register geschoben (siehe Bild), so wird genau dann G(X)·X^s addiert, wenn das höchste (rechte) Bit gesetzt ist; in dem Schieberegister werden genau in diesem Fall die Bits an den Stellen 15, 2 und 0 komplementiert. In jedem Falle werden alle Bits um eine Stelle nach rechts geschoben (während bei der Polynomdivison G(X) nach links geschoben wird). Danach hat man den gleichen Zustand wie vorher erreicht, nur dass jetzt die nächste Stelle bearbeitet werden kann. Dieses Verfahren wird solange fortgesetzt, bis das letzte Bit von R(X) in das Schieberegister verbracht wurde. Dessen Inhalt bildet dann offenbar den Rest bei der Division von R(X) mit G(X) und kann hinter den Daten, die während der Polynomrestberechnung an dem Schieberegister vorbeigeleitet werden, übertragen werden.

Schieberegister mit Divisor Q(X) = X¹⁶ + X¹⁵ + X² + 1