Erzeugung zyklischer Codes

3 Erzeugung zyklischer Codes

Der zu sichernde Datenblock mit einer Länge von $n$ Bit wird zur Bildung eines zyklischen Codes als erstes um $k$ Bit nach links verschoben. Dies bedeutet für das zugeordnete Polynom $M(x)$ eine Multiplikation mit $k x$ . Danach wird $M (x)$ durch ein sogenanntes Generatorpolynom $k k−1 2 G (x) = gkx + gk− 1x + ⋅⋅⋅+ g2x + g1x + g0$ vom Grad $k$ im Körper $GF (2)$ dividiert.

xkM(x) R (x) -------= F(x)+ ----- G(x) G (x)

(1)

Der dabei entstehende Divisionsrest

R (x) = CRC {M (x)} = xkM(x) mod G(x)

(2)

dessen Grad $k − 1$ ist, wird zur Kontrolle des Informationsblockes $M (x)$ verwendet.³ Dazu wird der entstandene CRC-Rest $R(x)$ einfach an den Datenblock $M (x)$ angehängt und so ein (gültiges) Codewort $C (x)$ des zu $G(x)$ gehörigen zyklischen Codes gebildet.

C (x) = xkM (x)+ R(x)

(3)

Zyklische Codes gehören zu den linearen Block-Codes. Sie haben die bemerkenswerte Eigenschaft, daß man ausgehend von einem bekannten Codewort alle anderen durch zyklische Verschiebung und Addition bestimmen kann [3]. $G(x)$ definiert alle Codeworte des zugeordneten Alphabets eindeutig und wird deshalb auch das erzeugende Polynom bzw. auch Generatorpolynom genannt.