Cryptography Reference
In-Depth Information
des Quellenkodeworts aus dem Alphabet
A
∗
und welche die
k
Kontrollelemente
sind, ist im Prinzip willkürlich. Um eine einfache Kodierung zu ermöglichen,
ist es jedoch zweckmäßig, diejenigen Elemente als Kontrollelemente zu verwen-
den, deren Spalten nur eine „1“ enthalten, weil dann nur jeweils eine der durch
H
definierten Bestimmungsgleichungen für die Berechnung eines Kontrollele-
ments erforderlich ist. (Anderenfalls müsste ein Gleichungssystem mit bis zu
k
Gleichungen gelöst werden.) Die Kontrollelemente
k
i
+1
sind demnach an den
Positionen
n
2
i
(
i
=0
,
1
,
2
, ...
)
angeordnet. An den Positionen
n
3
,n
5
,n
6
, ...
be-
finden sich die Elemente
l
1
,l
2
,l
3
, ...
des Quellenkodeworts aus
A
∗
.
Das Kanalkodewort übernimmt entsprechend den Aufbau der Kontrollmatrix:
a
i
=([
...
]
n
7
n
6
n
5
n
4
n
3
n
2
n
1
)=([
...
]
l
4
l
3
l
2
k
3
l
1
k
2
k
1
)
.
Wir sehen, auch dieser
Kode ist systematisch
, die Positionen der Informations-
und Kontrollelemente sind bekannt.
Kodierung und Dekodierung erfolgen auf der Basis von
H
. Weniger rechenin-
tensiv ist dabei die Anwendung der sich aus
H
ableitenden Bestimmungs- und
Kontrollgleichungen.
Beispiel 8.4.2
Die Bestimmungsgleichungen
k
j
(
j
=3
,
2
,
1)
für den HAMMING-Kode aus
Beispiel 8.4.1 sind:
1-te Zeile:
k
3
=
n
2
2
=
n
7
⊕ n
6
⊕ n
5
=
l
4
⊕ l
3
⊕ l
2
,
2-te Zeile:
k
2
=
n
2
1
=
n
7
⊕ n
6
⊕ n
3
=
l
4
⊕ l
3
⊕ l
1
,
3-te Zeile:
k
1
=
n
2
0
=
n
7
⊕ n
5
⊕ n
3
=
l
4
⊕ l
2
⊕ l
1
.
Das Quellenkodewort
a
i
=(1011)
ist zu kodieren.
Mit
a
i
=(
l
4
l
3
l
2
l
1
)
ist
a
i
=(101
k
3
1
k
2
k
1
)
. Die Bestimmungsgleichungen be-
rechnen
a
i
=(1010101)
.
Die Kontrollgleichungen
s
j
(
j
=3
,
2
,
1)
ergeben sich wie folgt:
1-te Zeile:
s
3
=
n
7
⊕
n
6
⊕
n
5
⊕
n
4
=
l
4
⊕
l
3
⊕
l
2
⊕
k
3
,
2-te Zeile:
s
2
=
n
7
⊕
n
6
⊕
n
3
⊕
n
2
=
l
4
⊕
l
3
⊕
l
1
⊕
k
2
,
3-te Zeile:
s
1
=
n
7
⊕
k
1
.
Im Falle eines Fehlers wird dieser durch das Fehlersyndrom
s
=(
s
k
, ..., s
2
,s
1
)
n
5
⊕
n
3
⊕
n
1
=
l
4
⊕
l
2
⊕
l
1
⊕
T
j
=1
k
lokalisiert und die
n
i
-te Stelle mit
i
=
s
j
2
j−
1
korrigiert.
Die Empfangsfolgen
b
1
=(1101011)
und
b
2
=(1100110)
sind zu prüfen
und gegebenenfalls zu korrigieren.
Die Anwendung der Kontrollgleichungen ergibt für
b
1
das Syndrom
s
=(110)
T
,
d. h., durch Korrektur des Elements
n
6
=
l
3
wird
b
1
,korr
=(1001011)
ein Ka-
nalkodewort. Für die Binärfolge
b
2
ist das Syndrom
s
=
0
,b
2
ist damit ein
Kanalkodewort.