Cryptography Reference
In-Depth Information
Sind in einem Kanalkodewort mehr als
f
k
Stellen verfälscht, dann entfernt sich
beispielsweise die Binärfolge
b
aus der Korrekturkugel des Kanalkodeworts
a
i
in die Korrekturkugel von
a
j
und wird mit Sicherheit falsch korrigiert. D. h.,
solange
d
(
a
i
,b
=
a
i
⊕ e
)
<d
(
a
j
,b
=
a
i
⊕ e
)
,
wird
b
auf
a
i
abgebildet, sonst auf
a
j
. Dieser Zusammenhang lässt sich auch mit
dem
HAMMING-Gewicht
w
eines Kanalkodeworts herstellen. Bei einem
Binärkode ergibt sich das Gewicht aus der Anzahl der mit „1“ belegten Stellen
im Kanalkodewort:
n
w
(
a
i
)=
u
ij
,
(8.9)
j
=1
d. h., solange
d
(
a
i
,b
)=
w
(
a
i
⊕ b
)=
w
(
e
)
≤ f
k
,
erfolgt die Korrektur in das Kanalkodewort
a
i
.
Ist die HAMMING-Distanz
d
min
geradzahlig
, gibt es immer Binärfolgen außer-
halb der Korrekturkugeln. In diesen Fällen erfolgt keine Zuordnung zu einem
Kodewort. Man spricht von Rekonstruktionsversagen. Betreffende Binärfolgen
(
w
(
e
)=
d
min
2
) werden lediglich erkannt. Für eine korrekte Rekonstruktion lässt
sich damit nur eine begrenzte Mindestdistanz von
d
=2
f
k
+1
<d
min
nutzen.
Für beliebiges
d
min
(gerade, ungerade) gilt aus Sicht der Rekonstruktion dem-
nach:
d
min
2
und
f
k
=
d
min
−
1
2
.
f
e
=
(8.10)
Beispiel 8.1.4
Bei
Fehlerkorrektur durch Rekonstruktion
sichert
d
min
=16
die Erkennung
von
f
e
=8
und die Korrektur von
f
k
=7
Fehlerstellen, für
d
min
=13
ist
f
e
=
f
k
=6
.
Offensichtlich hängt die minimale HAMMING-Distanz
d
min
eines Kanalkodes
von der Anzahl
k
der redundanten Stellen ab. Bei
k
=0
, wenn die Kanalkode-
wörter überhaupt keine redundanten Stellen enthalten und damit
A
=
A
∗
ist,
ist
d
min
=1
. Maximal kann der Minimalabstand den Wert der Kodewortlänge
n
annehmen, d. h.
k
=
n −
1
. Kodes mit dieser Eigenschaft heißen Wiederho-
lungskodes (s. a. Abschn. 8.2).
Für den Fall der Fehlerkorrektur durch Rekonstruktion lässt sich für einen vor-
gegebenen Wert von
d
min
und bei Kenntnis der Länge
n
der Kanalkodewörter