Cryptography Reference
In-Depth Information
Präsenz des Kodealphabets. Eine Empfangsfolge muss immer mit allen Kode-
wörtern verglichen werden, um zum einen eine fehlerhafte Folge erkennen und
zum anderen in das Kodewort mit kleinstem Abstand korrigieren zu können.
Man stelle sich den Aufwand bei sehr großer Anzahl Kanalkodewörter vor.
8.2.1
Blockkodes
Wenn die Kanalkodewörter des Alphabets
A
eine feste Länge haben, bezeichnet
man den Kode als Blockkode (s. Abschn. 8.3).
8.2.1.1 Wiederholungskodes [repetition codes]
Der
(
n,
1
,n
)
Wiederholungskode besitzt
L
=2
=2
Kanalkodewörter der Länge
n
, das Nullwort und das Einswort. Der Minimalabstand
d
min
=
n
ermöglicht
l
die Rekonstruktion von bis zu
f
k
=
n−
1
2
Einzelfehlern.
Mit ausreichender Länge
n
wäre damit auch eine quasi fehlerfreie Übertra-
gung bei nur geringer Restfehlerwahrscheinlichkeit möglich, allerdings bei ei-
ner Koderate von
R
=
n
→
0
. Das Kodierungsproblem wäre gelöst, jedoch auf
Kosten hoher Kodierungs- und Dekodierungsverzögerungen.
8.2.1.2 Iterierte Kodes
Zu den einfachen iterierten Kanalkodes gehören die binären
Paritätskodes
[parity check codes], die z. B. für die interne Datenübertragung in Rechnern
verwendet werden. Jedes
l
-stellige Quellenkodewort
a
i
=(
u
i
1
u
i
2
... u
il
)
wird
durch ein Paritätselement [parity element]
u
i,l
+1
auf geradzahliges Gewicht
[even parity check] ergänzt:
l
u
i,l
+1
=
u
ij
mod
2
.
j
=1
Das Kanalkodewort lautet
a
i
=(
u
i
1
u
i
2
... u
il
u
i,l
+1
)
, die minimale HAMMING-
Distanz beträgt
d
min
=2
, d. h., es liegt ein
(
n, n −
1
,
2)
Paritätskode vor.
Zur Fehlererkennung wird ein Syndromwert über
b
=(
u
1
u
2
... u
l
u
l
+1
)
mit
n
=
l
+1
s
0
=
u
j
mod
2
j
=1
berechnet. Ist das Ergebnis der Prüfung
s
0
=0
, liegt keine oder eine nicht er-
kennbare Verfälschung vor (alle Fehlermuster geradzahligen Gewichts bleiben
unerkannt),
b
∗
=(
u
1
u
2
... u
l
)
.Bei
s
0
=1
werden nicht nur mit Sicherheit alle
Einfachfehler (
f
e
=1)
, sondern alle ungeradzahligen Fehler erkannt.
