Cryptography Reference
In-Depth Information
Beispiel 8.3.4
Der im Beispiel 8.3.3 angegebene
(7
,
3)
Linearkode kann durch folgende Gene-
ratormatrizen beschrieben werden:
⎛
⎞
⎛
⎞
1001101
0101010
0010010
1001101
1100111
1110101
⎝
⎠
,G
2
=
⎝
⎠
.
G
1
=
Wie können nun Basisvektoren gefunden werden, die linear unabhängig sind?
Eine Möglichkeit besteht im systematischen Probieren. Dies ist aber sehr auf-
wendig. Wählt man dagegen die Basisvektoren so aus, dass die ersten
l
Spal-
ten der Generatormatrix eine Einheitsmatrix bilden, dann sind die Zeilen der
Generatormatrix mit Sicherheit linear unabhängig. Die im Beispiel 8.3.4 ange-
gebene Matrix
G
1
entspricht dieser Darstellung.
Allgemein gilt:
⎛
⎞
100
...
0
g
1
,l
+1
g
1
,l
+2
... g
1
n
010
...
0
g
2
,l
+1
g
2
,l
+2
... g
2
n
............................
000
...
1
g
l,l
+1
g
l,l
+2
... g
ln
⎝
⎠
G
l×n
=
⎛
⎞
100
...
0
c
11
c
12
... c
1
k
010
...
0
c
21
c
22
... c
2
k
........................
000
...
1
c
l
1
c
l
2
... c
lk
⎝
⎠
=[
I
l
C
]
.
=
(8.17)
Die
l
×
n
Generatormatrix
G
lässt sich damit als Konkatenation einer
l
×
l
Einheitsmatrix
I
l
(Matrix über den Informationsstellen) und einer
l
k
Ma-
trix
C
(Matrix über den Kontrollstellen) darstellen. Diese Form einer Matrix
bezeichnet man als
kanonische
oder
reduzierte Staffelform
. Durch geeig-
netes Vertauschen und Addieren der Zeilen lässt sich jede Matrix mit
l
linear
unabhängigen Zeilen in diese Form bringen.
Erinnern wir uns jetzt daran, dass das Ziel der Kanalkodierung die Transforma-
tion
l
-stelliger Quellenkodewörter des Alphabets
A
∗
in
n
-stellige Kanalkode-
wörter des Alphabets
A
ist (vgl. Abschn. 8.1.3). Die Zuordnung der Quellen-
kodewörter zu den Kanalkodewörtern ist prinzipiell frei wählbar. Eine der mög-
lichen Zuordnungen besteht darin, dass die
l
-stellige Binärfolge der Quellen-
kodewörter unverändert bleibt und als Kanalkodewort um
n
×
l
=
k
Kon-
trollstellen ergänzt wird. Man spricht in diesem Fall von einem systematischen
Kode.
−
