Cryptography Reference
In-Depth Information
so muss auch
d
(
a
i
,a
j
)=
w
(
a
k
=
a
i
⊕
d
min
sein, sonst läge ein Widerspruch vor.
Diese Eigenschaft nutzt man bei der Konstruktion der Generatormatrix. Damit
der Abstand zum Nullwort
a
j
)
≥
≥
d
min
ist, müssen alle Basisvektoren das Gewicht
w
d
min
haben. Ferner muss jede Modulo-2-Summe aus
i
(verschiedenen)
Basisvektoren (
i
=1
,
2
, ..., l
) mindestens
d
min
Einsen aufweisen.
Der Nachweis für
d
min
kann auch mit der zu
G
orthogonalen Kontrollmatrix
geführt werden.
≥
Es darf keine lineare Abhängigkeit zwischen
(
d
min
−
1)
oder weniger Spalten
in der Kontrollmatrix bestehen.
Beispiel 8.3.8
Der in den Beispielen 8.3.6 und 8.3.7 betrachtete
(7
,
4)
Linearkode
ist hinsicht-
lich der minimalen HAMMING-Distanz zu
analysieren
.
Auf der Basis der Generatormatrix:
Das minimale Gewicht von Basisvektoren und den Modulo-2-Verknüpfungen
von Basisvektoren ist
w
min
=3
und damit
d
min
=3
.
Auf der Basis der Kontrollmatrix:
Eine lineare Abhängigkeit liegt erst bei Betrachtung von 3 Spalten vor. So
führt z. B. die Modulo-2-Addition der Spalten
n
1
und
n
2
auf Spalte
n
3
.
Diesen Zusammenhang etwas anders zum Ausdruck gebracht:
d
min
=3
Spal-
ten in
H
bilden in der Addition den Nullvektor, wie z. B.
n
1
⊕
.
Der vorliegende
(7
,
4
,
3)
Linearkode kann also bei Anwendung der Fehlerkor-
rektur durch Wiederholung mit Sicherheit
f
e
=2
Fehler erkennen und durch
Rekonstruktion mit Sicherheit
f
k
=1
Fehler korrigieren.
n
2
⊕
n
3
=
0
8.3.5
Fehlererkennung und -korrektur von Linearkodes
Die Empfangsfolge
b
∈
B
entsteht durch Überlagerung des gesendeten Kanal-
kodeworts
a
A
mit einem Fehlerwort
e
aus dem Alphabet
E
der Fehlermus-
ter. Beide Wörter sind durch eine stellenweise Modulo-2-Addition verknüpft.
Bei einem Linearkode entsteht dann und nur dann eine nichterkennbare Verfäl-
schung, wenn
e
selbst ein Kanalkodewort ist (Axiom G1: Abgeschlossenheit).
Daraus folgt, dass
alle Fehlermuster, deren Gewicht
w
(
e
)
<d
min
ist, mit Si-
cherheit erkennbar
sind.
Um nun festzustellen, ob eine Empfangsfolge ein Kanalkodewort ist oder nicht,
d. h. ob eine (erkennbare) Verfälschung vorliegt oder nicht, benutzen wir die
∈
