Cryptography Reference
In-Depth Information
In den meisten Fällen sind die Abstände zwischen den einzelnen Kanalkode-
wörtern unterschiedlich. Bezüglich der Erkennbarkeit bzw. Korrigierbarkeit
von Fehlern interessiert insbesondere die
minimale HAMMING-Distanz
d
min
[minimum distance] (auch Mindestdistanz, Minimalabstand) eines Kanal-
kodes.
Eine anschauliche geometrische Deutung ist im Bild 8.1.3 gegeben. Die Punkte
zwischen den Kanalkodewörtern
a
i
und
a
j
entsprechen der Anzahl der Stellen,
um die sich diese Kanalkodewörter unterscheiden.
Kodewort
a
i
Kodewort
a
j
Korrekturkugeln
d(
a
i
a
j
,
)
0
1
2
3
4
5
Bild 8.1.3
Geometrische Deutung der HAMMING-Distanz
Hat ein Fehlerwort kleiner als
d
min
(im Bild 8.1.3 sei
d
min
=
d
(
a
i
,a
j
)=5
)
von Null verschiedene Stellen, ist eine Verfälschung mit Sicherheit erkennbar.
Ein Fehler ist mit Sicherheit korrekt rekonstruierbar, wenn das Ergebnis der
Überlagerung in der Korrekturkugel des gesendeten Kodeworts bleibt. Enthält
das Fehlerwort
d
min
oder mehr Fehlerstellen, dann kann bei der Überlagerung
von beispielsweise
a
i
durch
e
eine Binärfolge
b
entstehen, die gerade einem
Kanalkodewort entspricht, z. B.
b
=
a
j
∈ A
. Solche Verfälschungen sind nicht
erkennbar und damit auch nicht korrigierbar.
Ein Kode, der mit Sicherheit alle Verfälschungen
≤
f
e
erkennen kann, muss
also eine minimale HAMMING-Distanz von
d
min
=
f
e
+1
(8.6)
besitzen. Mit
f
e
wird im Folgenden der Grad der Fehlererkennung bezeichnet.
Die Rekonstruktion wird korrekt ausgeführt, wenn die Anzahl
f
k
der verfälsch-
ten Stellen in der empfangenen Binärfolge kleiner als
d
min
2
ist, d. h., wenn
d
min
=2
f
k
+1
(8.7)
ist.
f
k
beschreibt in diesem Fall den Grad der Fehlerkorrektur. Der Term
2
f
k
steht für Fehlererkennung und Fehlerkorrektur, denn Fehlerkorrektur setzt im-
mer auch Erkennung voraus:
d
min
=
f
e
+
f
k
+1
.
(8.8)
