Cryptography Reference
In-Depth Information
Gl. (8.12) ist eine notwendige Bedingung für die minimale Anzahl redundan-
ter Stellen
k
(
untere Schranke
) und damit zur Gewährleistung der richtigen
Korrektur von
≤ f
k
Fehlern. Sie wird (wie auch Gl. (8.11)) als
HAMMING-
Schranke
bezeichnet und stellt für die Berechnung der Anzahl Quellenkode-
wörter
L
eine
obere Schranke
dar (s. Beispiel 8.1.5). Das Gleichheitszeichen gilt
nur für bestimmte Tripel von
d
min
,
k
und
l
. Entsprechende Kodes heißen
dicht-
gepackt
oder
perfekt
. Sie sind dadurch gekennzeichnet, dass sich keine Binär-
folgen zwischen den Korrekturkugeln (s. Bild 8.1.3) befinden. Jede Binärfolge
b
lässt sich genau einem Kanalkodewort
a
zuordnen:
d
(
a, b
)
≤
d
min
−
1
2
=
f
k
,
was eine ungerade minimale HAMMING-Distanz voraussetzt. Für nicht dicht-
gepackte Kodes ist die linke Seite der Ungleichung (8.12) größer als die rechte,
d. h., die Redundanz des Kanalkodes wird nicht voll ausgenutzt.
Beispiel 8.1.6
Ein Kanalkodierer soll 20stellige Quellenkodewörter in einen Kanalkode mit
d
min
=3
transformieren. Wie groß muss
k
sein?
Lösung:
Mit Gl. (8.12) ist
i
=0
i
=
ld
(1 +
n
)=
ld
(1 + 20 +
k
)
und somit
k
=5
.
1
k ≥
ld
Die Kanalkodewörter haben damit eine Kodewortlänge von
n
=
l
+
k
=25
.
Der Kode ist nicht perfekt.
Neben der HAMMING-Schranke (1950) gibt es weitere Schranken zur Abschät-
zung von Kodekenngrößen. Die SINGLETON-Schranke (1964) stellt ebenfalls
eine untere Schranke für die Anzahl redundanter Stellen und eine obere Schran-
ke für die Anzahl der Quellenkodewörter dar. REED-SOLOMON-(RS-)Kodes
erfüllen diese Schranke mit Gleichheit (s. Abschn. 8.5.4).
Die Anzahl
k
der redundanten Stellen in einem Kanalkodewort der Länge
n
führt zu einer weiteren charakteristischen Größe, die wir als
relative Redun-
danz
r
k
bezeichnen:
n
−
l
n
=
k
n
.
r
k
=
(8.13)
Die Effektivität eines Kanalkodes ist um so größer, je kleiner seine relative
Redundanz - bei vorgegebener HAMMING-Distanz
d
min
-ist.
Die
Koderate
[code rate]
R
(auch Informationsrate) beschreibt dagegen das
Verhältnis der Informationsstellen
l
zur Gesamtkodewortlänge
n
mit
l
n
.
R
=
(8.14)
