Cryptography Reference
In-Depth Information
3.3
Koderedundanz und erstes SHANNONsches
Kodierungstheorem
Die Anwendung eines gleichmäßigen oder ungleichmäßigen Kodes hängt na-
türlich vom Wissen über meine Quelle ab. Aus den Betrachtungen im Abschn.
2.2 ist klar geworden, dass sich dieses Wissen in der Größe der Entropie wi-
derspiegelt. Dieses Wissen gilt es jetzt auch geeignet in die Quellenkodierung
einzubeziehen, um damit die Koderedundanz minimal zu gestalten.
Zur Ermittlung der Koderedundanz entsprechend Definition 3.1.3 müssen wir
zunächst die
Kodewortlänge
bestimmen. Sie ergibt sich aus der Beziehung
l
=
ld
N
für
gleichmäßige
Kodes
.
(3.2)
Bei ungleichmäßigen Kodes kann nur der Mittelwert der Kodewortlängen
l
i
(
i
=1
,
2
, ..., N
) gebildet werden, der von den Auftrittswahrscheinlichkeiten
p
i
der einzelnen Kodewörter, d. h. von der Statistik der zu kodierenden Quelle,
abhängt. Danach ergibt sich eine
mittlere Kodewortlänge
N
l
m
=
p
i
l
i
für
ungleichmäßige
Kodes
.
(3.3)
i
=1
Jedes Kodewort ist eine Folge von Binärzeichen (
Bit
[binary digit]) bzw. Ka-
nalzeichen (
KZ
). Demnach kann die Kodewortlänge in
Bit
QZ
bzw.
KZ
QZ
(bezogen auf ein Quellenzeichen (
QZ
)) angegeben werden.
Aus praktisch einleuchtenden Gründen (weniger Speicherplatz, kürzere Über-
tragungszeiten der Information) werden generell möglichst kleine Kodewort-
längen angestrebt. Da jedoch die Kodewortlänge den mittleren Informationsge-
halt je Quellenzeichen verkörpert, gilt für einen dekodierbaren (binären) Kode
offensichtlich die untere Schranke
l
m
≥
H
m
.
Beweis:
H
m
− l
m
≤
0
.
Wir gehen von den Gln. (2.2) und (3.3) aus:
p
i
ld
p
i
−
p
i
l
i
ld
2
≤
0
,
i
i
p
i
ld
p
i
+
i
p
i
ld
2
−l
i
=
i
p
i
ld
2
−l
i
p
i
≤
0
.
i
