Cryptography Reference
In-Depth Information
Die Matrix
H
wird als
Kontroll-
oder
Prüfmatrix
des durch die Genera-
tormatrix
G
erzeugten Linearkodes bezeichnet. Diese liefert unmittelbar eine
Vorschrift zur Bildung der Kontrollstellen der Kanalkodewörter. Um dies zu
zeigen, betrachten wir noch einmal für das Produkt
a
i
·a
1
die Orthogonalitäts-
bedingung nach Gl. (8.19), aus der folgt, dass das Skalarprodukt jedes Vektors
a
i
aus
A
mit dem Vektor
a
1
aus
A
, der der ersten Zeile der Kontrollmatrix
entspricht, den Wert Null ergibt:
a
i
·
a
1
=
u
i
1
·
c
11
⊕
u
i
2
·
c
21
⊕
...
⊕
u
il
·
c
l
1
⊕
u
i,l
+1
·
1
⊕
u
i,l
+2
·
0
⊕
...
⊕
u
in
·
0
=0
.
Durch Umstellung dieser Gleichung lässt sich das erste Kontrollelement
u
i,l
+1
des Kanalkodeworts
a
i
bestimmen:
u
i,l
+1
=
u
i
1
·
c
l
1
.
Entsprechend können die übrigen Kontrollstellen von
a
i
berechnet werden,
indem für die zweite Kontrollstelle die zweite Zeile von
H
, für die dritte Kon-
trollstelle die dritte Zeile von
H
usw. herangezogen wird.
Allgemein gilt für die Berechnung der
k
Kontrollstellen
c
11
⊕
u
i
2
·
c
21
⊕
...
⊕
u
il
·
u
i,l
+
j
=
u
i
1
·
c
1
j
⊕
u
i
2
·
c
2
j
⊕
...
⊕
u
il
·
c
lj
(
j
=1
,
2
, ..., k
)
.
(8.22)
Bei einem binären Linearkode ergibt sich damit die
j
-te Kontrollstelle als Sum-
me der bitweisen Modulo-2-Addition aus denjenigen Stellen in dem zu kodie-
renden Quellenkodewort
a
i
, an deren Position in der
j
-ten Zeile der Kontroll-
matrix
H
eine „1“ steht. Das Ergebnis sind
Bestimmungsgleichungen für die
k
Kontrollstellen
.
Die Bestimmung der
k
Kontrollstellen ist mit der Berechnung von Paritäts-
elementen (s. Abschn. 8.2.1.2) vergleichbar. Die Modulo-2-Verknüpfung von
Informationsstellen führt zur Ergänzung auf geradzahlige Parität.
Beispiel 8.3.7
n
1
n
2
0
1
l
2
n
3
1
1
l
3
n
4
1
1
l
4
n
5
1
0
k
1
n
6
0
1
k
2
n
7
0
0
1
⎛
⎞
1
0
l
1
⎝
⎠
Aus Beispiel 8.3.6 ist die Matrix
6
H
3
×
7
=
bekannt.
k
3
Die Transformation eines beliebigen 4stelligen Quellenkodeworts
a
i
=(
l
1
l
2
l
3
l
4
)
6
Zum besseren Verständnis sind den Spalten die Positionen der Informations- und Kon-
trollstellen zugeordnet. Diese ergeben sich aus dem Aufbau der Generatormatrix und de-
ren Transformation in die Kontrollmatrix, s. Gln. (8.17) und (8.20). Die Anordnung der
Informations- und Kontrollstellen muss sich natürlich auch im Kanalkodewort widerspie-
geln.