Cryptography Reference
In-Depth Information
8.4.2
Verkürzte HAMMING-Kodes
Das Korrekturschema eines einfehlerkorrigierenden HAMMING-Kodes lässt
sich auch dann anwenden, wenn
n<
2
k
−
1
und damit der Kode nicht dicht-
gepackt ist. In diesem Fall werden weniger Informationsstellen verwendet als
möglich. Die Kodewortlänge ist
n
=
l
+
k
und die
n
Spalten der Kontrollmatrix
H
sind die dualen Darstellungen von
n, n
−
1
, ...,
1
.
Beispiel 8.4.3
Es ist die Kontrollmatrix eines einfehlerkorrigierenden HAMMING-Kodes an-
zugeben, mit dem 5stellige Quellenkodewörter aus
A
∗
kodiert werden können.
1. Schritt:
Berechnung von
k
Nach Gl. (8.12) ist
5+
i
=
ld
5+
k
+
5+
k
1
=
ld
(1 + 5 +
k
)
.
i
=0
1
k ≥
ld
0
Die Ungleichung ist für den kleinstmöglichen Wert
k
=4
erfüllt.
2. Schritt:
Bestimmung von
n
Mit
k
=4
ist
n
=5+4=9
, d. h., es wird ein verkürzter, einfehlerkorrigie-
render (9,5)HAMMING-Kode erzeugt. (Mit
k
=4
wäre eine Kodewortlänge
von
n
=15
möglich.)
3. Schritt:
Konstruktion der Kontrollmatrix
H
n
9
n
8
1
0
0
k
4
n
7
0
1
1
l
4
n
6
0
1
1
l
3
n
5
0
1
0
l
2
n
4
0
1
0
k
3
n
3
0
0
1
l
1
n
2
0
0
1
k
2
n
1
0
0
0
1
⎛
⎞
1
0
0
l
5
⎝
⎠
H
4
×
9
=
k
1
Bestimmungsgleichungen:
Kontrollgleichungen:
k
4
=
l
5
s
4
=
n
9
⊕
n
8
k
3
=
l
4
⊕
l
3
⊕
l
2
s
3
=
n
7
⊕
n
6
⊕
n
5
⊕
n
4
k
2
=
l
4
⊕
l
3
⊕
l
1
s
2
=
n
7
⊕
n
6
⊕
n
3
⊕
n
2
k
1
=
l
5
⊕
l
4
⊕
l
2
⊕
l
1
s
1
=
n
9
⊕
n
7
⊕
n
5
⊕
n
3
⊕
n
1
Da die im Kode enthaltene Redundanz nicht voll ausgeschöpft wird, gibt es
Syndrome, die nicht in
H
enthalten sind. Bei Prüfung von Empfangsfolgen las-
sen diese nicht in
H
definierten Syndrombelegungen auf Mehrfachfehler schlie-
ßen. Es kommt zu Rekonstruktionsversagen. Führen Mehrfachfehler auf Kor-
rektorspalten von
H
, wie bei dichtgepackten Kodes überhaupt, erfolgt prinzi-
piell eine Einfachfehler- und damit Falschkorrektur. Bei verkürzten Kodes sind
demzufolge alle Rekonstruktionsergebnisse möglich.
