Cryptography Reference
In-Depth Information
0,40 0,18 0,14 0,10 0,08
0,05 0,05
0,40 0,18 0,14 0,10
0,10 0,08
0,40 0,18 0,18
0,14 0,10
0,40 0,24
0,18 0,18
0,40
0,60
0,40
0,36 0,24
0,36
0,24
0
0,60 0,40
0,18
0,18
1,00
0,10
0,14
0,08
0,10
1 1 0
0,05
0,05
1 0 0
1 0 1
1 1 1 0
1 1 1 1 0
1 1 1 1 1
Bild 3.4.1
HUFFMAN-Verfahren
Anhand des Kodebaumes können wir die mittlere Kodewortlänge bestimmen:
l
m
=0
,
40
·
1+0
,
18
·
3+0
,
14
·
3+0
,
10
·
3+0
,
08
·
4+2
·
0
,
05
·
5
=2
,
48
Bit/QZ .
Damit beträgt die Koderedundanz bei diesem Optimalkode nur noch
R
K
=2
,
48
Bit/QZ ·
1
bit/Bit −
2
,
43
bit/QZ
=0
,
05
bit/QZ .
Anmerkung:
Wie beim SHANNON-FANO-Verfahren ergeben sich auch beim HUFFMAN-
Verfahren unterschiedliche, aber gleichwertige Kodierungsmöglichkeiten. Sie
entstehen dadurch, dass die zusammengefassten Wahrscheinlichkeitswerte an
verschiedenen Stellen eingeordnet werden können, wenn noch andere gleich-
große Werte vorliegen. Die Bestätigung dieser Feststellung wird dem Leser zur
Übung empfohlen.
Hinweis
:
Aufgaben
s. Abschn. 3.5
Wir wollen diesen Abschnitt mit einer vergleichenden Betrachtung der vorge-
stellten Verfahren bezüglich Koderedundanz abschließen.
Beide Verfahren liefern Ergebnisse, die sich i. Allg. nur wenig, oft gar nicht
voneinander unterscheiden. Es ist aber theoretisch nachgewiesen worden, z. B.
in [KÄM 71], dass das
HUFFMAN-Verfahren immer Kodes mit minimaler Re-
dundanz
liefert, d. h., es gibt kein anderes Verfahren, das Kodes mit geringerer
Redundanz erzeugen kann. Dies ist neben der einfachen technischen Realisie-
rung der entscheidende Grund dafür, dass dieses Verfahren praktisch häufig
zur Anwendung kommt. HUFFMAN-Kodes werden u. a. bei der Kodierung
