Cryptography Reference
In-Depth Information
Der Vektor
s
wird als
Fehlersyndrom
[error syndrome] (auch Prüfvektor) be-
zeichnet. Mit Erkennung der Verfälschung kann das Syndrom dazu verwendet
werden, die Position der verfälschten Elemente in
b
festzustellen. Bei einem
Binärkode werden diese Elemente dann einfach negiert.
Offensichtlich ist eine Rekonstruktion nur dann möglich, wenn jedem Fehler-
syndrom maximal ein Fehlermuster zugeordnet ist. Die Anzahl der unterschied-
lichen Syndrome bestimmt damit die Anzahl der korrigierbaren Fehlermuster.
Da die Syndrome gemäß Gl. (8.23)
k
-stellige Vektoren sind, können also
(2
k
−
1)
verschiedene Fehlermuster korrigiert werden (bei
s
=
0
ist die Empfangsfolge
ein Kanalkodewort).
Ein Fehlermuster kann aus einem oder mehreren verfälschten Binärelementen
bestehen. Sollen in einer Empfangsfolge alle Fehlermuster korrigierbar sein, de-
ren Gewicht
w
(
e
)
≤
f
k
ist, dann lässt sich nach Gl. (8.7) der Minimalabstand
d
min
und damit nach Gl. (8.12) die Anzahl
k
der erforderlichen Kontrollele-
mente berechnen (s. a. Beispiel 8.1.6).
Um ein Fehlersyndrom bestimmten fehlerhaften Elementen in einer Empfangs-
folge zuzuordnen, ist
nur
die Untersuchung des Fehlermusters selbst erforder-
lich. Dies ist durch Gl. (8.23) begründet. Die Empfangsfolge
b
ergibt sich als
Überlagerung (d. h. als stellenweise Modulo-2-Addition) eines Kanalkodeworts
a
i
mit einem Fehlerwort
e
:
b
=
a
i
⊕ e.
Damit gilt für Gl. (8.23)
s
=
H · b
T
T
=
H · a
i
⊕ H · e
T
=
H · e
T
,
=
H ·
(
a
i
⊕ e
)
(8.24)
weil
H · a
i
ist. Diese Gleichung liefert die Zuordnung der (
k
-stelligen)
Fehlersyndrome zu den (
n
-stelligen) Fehlermustern, gespeichert in Tabellen
8
.
Zur Fehlerkorrektur werden Empfangsfolge und Fehlermuster addiert.
Bei Betrachtung von Linearkodes mit
f
k
=1
ist kein Speichern von Tabel-
len für die Zuordnung von Fehlersyndrom zu Fehlermuster notwendig. Jedem
(von Null verschiedenen) Syndrom ist ein bestimmtes Element in einer Emp-
fangsfolge zugeordnet. In den Kanalkodewörtern sind die Kontrollelemente so
festgelegt worden, dass die Modulo-2-Summe aller derjenigen Elemente eines
Kodeworts, die durch jeweils eine Zeile der Kontrollmatrix
H
berücksichtigt
werden, den Wert Null ergeben. Daraus folgt, dass bei Verfälschung eines Ele-
ments in einer Empfangsfolge genau diejenigen Zeilensummen modulo 2 der
=
0
8
Die Größe einer solchen Tabelle wächst mit
f
k
und den Kodeparametern. Man verzichtet
in der praktischen Anwendung darauf und setzt
f
k
>
1
mit anderen, leistungsfähigeren
Kodierungs- und Dekodierungsalgorithmen um. Eine bekannte Ausnahme bildet die De-
kodierung von GOLAY-Kodes, s. a. S. 203.
