Cryptography Reference
In-Depth Information
in den Kanalkodewörtern
a
i
enthalten sind. Es handelt sich also um keinen
systematischen Kode (s. a. Definition 8.3.2).
8.5.2.3 Divisionsverfahren
Ein zyklischer Kode
A
der Länge
n
ist durch ein Generatorpolynom
g
(
x
)
(vom Grad
k
) beschrieben. Das Kodepolynom
a
(
x
)
des Kodeworts
a
entsteht
aus der Multiplikation des zu kodierenden Polynoms
a
∗
(
x
)
mit
x
k
und der
Subtraktion eines Restpolynoms
r
(
x
)
:
a
(
x
)=
a
∗
(
x
)
x
k
− r
(
x
)
,
wobei
r
(
x
)=(
a
∗
(
x
)
x
k
)
mod
g
(
x
)
.
Bei diesem Verfahren wird
a
∗
(
x
)
mit
x
k
multipliziert, d. h., das Polynom wird
um die
k
redundanten Stellen nach links verschoben. Man erhält ein Poly-
nom, dessen Grad kleiner oder gleich
(
n
−
1)
ist und dessen Koe
zienten
u
k−
1
,u
k−
2
, ..., u
1
,u
0
sämtlich Null sind. Dieses Polynom ist in der Regel nicht
ohne Rest durch
g
(
x
)
teilbar, ist also kein Kodepolynom. Das Restpolynom
r
(
x
)
ist vom Grad kleiner als der Grad
k
von
g
(
x
)
. Subtrahiert man dieses
Restpolynom von
a
∗
(
x
)
x
k
(wegen der Modulo-2-Arithmetik entspricht dies
einer Addition), so erhält man ein Kodepolynom, d. h.,
a
(
x
)
ist wieder ein
Vielfaches von
g
(
x
)
:
a
(
x
)=
a
∗
(
x
)
x
k
+
r
(
x
)
im
GF
(2)
.
Das Restpolynom
r
(
x
)
widerspiegelt die Belegung der Kontrollstellen im Kode-
polynom
a
(
x
)
.
Beispiel 8.5.8
Die Kanalkodewörter eines zyklischen Kodes mit
g
(
x
)=
x
3
+
x
+1
aus Beispiel
8.5.7 sollen nach dem Divisionsverfahren gebildet werden.
Für das zu kodierende Quellenkodewort
a
∗
= (0111)
, das dem Polynom
a
∗
(
x
)=
x
2
+
x
+1
entspricht, gilt dann
a
∗
(
x
)
x
k
=(
x
2
+
x
+1)
x
3
=
x
5
+
x
4
+
x
3
.
Die Division durch
g
(
x
)
liefert:
(
x
5
+
x
4
+
x
3
):(
x
3
+
x
+1)=
x
2
+
x
x
5
+
x
3
+
x
2
x
4
+
x
2
x
4
+
x
2
+
x
x
=
r
(
x
)
.
Das Kodepolynom lautet damit:
a
(
x
)=
a
∗
(
x
)
x
k
+
r
(
x
)=
x
5
+
x
4
+
x
3
+
x
.
Dies entspricht dem Kanalkodewort
a
=(0111010)=[
a
∗
010]
.
Für alle Quellenkodewörter
a
i
∈
A
∗
erhält man mit Anwendung des Divisions-
verfahrens die folgende Zuordnung zu
a
i
∈ A
:
