Cryptography Reference
In-Depth Information
8.4
Fehlerkorrigierende HAMMING-Kodes
8.4.1
Korrekturschema
Definition 8.4.1
Der fehlerkorrigierende HAMMING-Kode ist ein speziel-
ler linearer Gruppenkode und bzgl. der HAMMING-Schranke ein dichtgepack-
ter Kode. Er hat eine minimale HAMMING-Distanz von
d
min
=3
und eine
Kodewortlänge von
n
=2
k
−
1
.
Der damit
einfehlerkorrigierende
HAMMING-Kode (1950) kann einfache Feh-
ler in einer Empfangsfolge
b
(d. h. Fehlermuster mit dem Gewicht
w
(
e
)=1
)
in einfacher Weise lokalisieren und (durch Negation des verfälschten Binärele-
ments) korrigieren. Ausgangspunkt für die Beschreibung ist die Kontrollma-
trix
H
, deren
n
=2
−
1)
von Null verschiedenen
k
-stelligen Binärfolgen darstellen. Ist in einem Kanalkodewort genau ein Ele-
ment verfälscht, dann gibt das mit Gl. (8.23) berechnete Syndrom die betref-
fende Spalte in
H
und damit die Position des fehlerhaften Elements an.
k
−
1
Spalten sämtliche
(2
k
HAMMING hat durch geschickte Vertauschung der Spalten von
H
erreicht,
dass die
i
-te Spalte von
H
der Dualdarstellung von
i
entspricht. Das Fehler-
syndrom
s
liefert dann unmittelbar die dual dargestellte Position des fehler-
haften Elements in
b
.
Beispiel 8.4.1
Die Kontrollmatrix eines
(7
,
4)
HAMMING-Kodes hat die Form
n
7
n
6
1
1
0
n
5
1
0
1
n
4
1
0
0
n
3
0
1
1
n
2
0
1
0
n
1
0
0
1
⎛
⎞
1
1
1
H
3
×
7
=
,
⎝
⎠
wenn die Elemente in abfallender Reihenfolge nummeriert werden.
9
⎛
⎞
1
1
1
⎝
⎠
,
Die Empfangsfolge
b
=(0010010)
führt mit Gl. (8.23) zu
s
=
d. h. zu der dualen Darstellung der „7“, und zeigt damit die Verfälschung des
Elements
n
7
an (vgl. mit Beispiel 8.3.11).
Die Festlegung, welche der
n
Elemente in einem Kanalkodewort die
l
Elemente
9
Wie im Beispiel 8.3.7 verwenden wir hier die verkürzte Schreibweise für die Elemente des
Kanalkodeworts
a
i
mit
u
in
=
n
n
,u
i,n−
1
=
n
n−
1
, ..., u
i
1
=
n
1
.
