Cryptography Reference
In-Depth Information
p
i
ld
p
i
+
i
p
i
l
i
<
−
p
i
,
i
i
l
m
<H
m
+1
.
Die Zusammenfassung beider Schranken der mittleren Kodewortlänge für den
annähernd redundanzfreien Kode ergibt
H
m
≤ l
m
<H
m
+1
.
(3.6)
Auf der Grundlage von Gl. (3.6) hat C.E. SHANNON nachgewiesen, dass es
prinzipiell möglich ist, jede diskrete Quelle völlig redundanzfrei zu kodieren
,
auch wenn keine „idealen Wahrscheinlichkeiten“ vorliegen.
Dies besagt das
erste SHANNONsche Kodierungstheorem
, das wie folgt
zu beweisen ist:
Man nimmt eine
m
-fache Erweiterung der Quelle vor, d. h., die Quellenzeichen
werden nicht einzeln, sondern in Blöcken von
m
Zeichen kodiert. Analog zu
Gl. (3.6) gilt dann (s. a. 2. Aufgabe zum Abschn. 3.3)
mH
m
≤ ml
m
<mH
m
+1
und nach der Division durch
m
H
m
≤ l
m
<H
m
+
m
.
(3.7)
Aus Gl. (3.7) folgt, dass die mittlere Kodewortlänge durch Vergrößerung von
m
beliebig an den unteren Grenzwert
H
m
angenähert werden kann und da-
mit die Koderedundanz beliebig klein wird. Eine praktische Realisierung nach
diesem Prinzip bedeutet jedoch, dass die Forderung nach unverzögerter Kodie-
rung und Dekodierung der einzelnen Quellenzeichen nicht erfüllt werden kann.
In den folgenden Abschnitten werden wir uns mit Möglichkeiten einer redun-
danzreduzierenden Kodierung befassen.
3.4
Optimalkodierung
3.4.1
Grundsätzliches
Obwohl, wie oben gezeigt wurde, redundanz
freie
Kodes prinzipiell möglich
sind, muss man bei der praktischen Realisierbarkeit vom Aufwand-Nutzen-
Verhältnis ausgehen. So würde es sicher keinen nennenswerten Effekt ergeben,
wenn die Einsparung einer unbedeutenden Koderedundanz mit großen Zeitver-
zögerungen erkauft werden müsste. Deshalb wird man i. Allg. auf die Forderung
