Cryptography Reference
In-Depth Information
Polynoms des Quellenkodeworts höchstens
(
n − k −
1)
,d.h.,daszukodieren-
de Quellenkodewort
a
∗
besteht aus
l
=
n − k
Elementen.
Bei der Kanalkodierung besteht die Aufgabe darin, jedem der
2
l
möglichen
l
-
stelligen Quellenkodewörter
a
∗
aus
A
∗
eineindeutig ein Kanalkodewort
a
aus
A
zuzuordnen. Für diese Zuordnung existieren, nachfolgend beschrieben, einfa-
che Bildungsverfahren. Im Ergebnis ist jedes Kanalkodewort
a
in seiner Poly-
nomdarstellung ein Vielfaches vom Generatorpolynom
g
(
x
)
, die Notwendigkeit
dafür zeigt Abschn. 8.5.2.4.
8.5.2.1 Generatormatrix und Kontrollmatrix
Eine uns schon bekannte Methode zur Bestimmung des Kanalkodeworts
a
ba-
siert auf einer Generatormatrix
G
(s. Abschn. 8.3.4.1). Bei einem zyklischen
Kode wird
G
auf der Grundlage des Generatorpolynoms
g
(
x
)
erzeugt.
g
(
x
)
ist
in Koe
zientendarstellung der Länge
n
ein Kanalkodewort in
A
, damit auch
jede zyklische Verschiebung (Definition 8.5.1).
Ein zyklischer Kode
A
der Länge
n
ist auf der Grundlage des Generatorpo-
lynoms
g
(
x
)=
x
k
+
u
k−
1
x
k−
1
+
...
+
u
0
x
0
in Koezientendarstellung durch
die folgende
l × n
Generatormatrix
⎛
⎞
00
...
01
u
k−
1
...u
1
u
0
00
...
1
u
k−
1
u
k−
2
...u
0
0
..............................
1
u
k−
1
⎝
⎠
G
l×n
=
..................
00
vollständig beschrieben.
Das Kanalkodewort
a ∈ A
entsteht aus der Multiplikation des zu kodierenden
Quellenkodeworts
a
∗
∈
A
∗
und der Generatormatrix
G
:
a
=
a
∗
· G
l×n
.
Die Menge aller Linearkombinationen der
l
Basisvektoren (Generatorwörter)
in
G
stellt die Gesamtheit aller Kanalkodewörter mit
L
=2
l
im Kodealphabet
A
dar, deren Kodepolynome
a
(
x
)
immer ein Vielfaches von
g
(
x
)
sind.
Die Kontrollmatrix
H
für einen zyklischen Kode kann, wie im Abschn. 8.3.4.2
gezeigt, durch Umwandlung der Generatormatrix
G
in ihre kanonische Staffel-
form nach Gl. (8.17) und Anwendung der Gl. (8.20) gewonnen werden. Feh-
lererkennung und Einfachfehlerkorrektur erfolgen dann Abschn. 8.3.5 entspre-
chend.
14
14
Zyklische Kodes bieten weiterhin die Möglichkeit, über das Hauptpolynom
f
(
x
)=
x
n
+1
(s. S. 168) ein Kontrollpolynom
h
(
x
)
f
(
x
)
g
(
x
)
mit
h
(
x
)=
zu berechnen. Die zyklische Ver-
schiebung von
h
(
x
)
in Koezientendarstellung der Länge
n
beschreibt eine Kontrollmatrix
H
k×n
.
