Cryptography Reference
In-Depth Information
Im vorgestellten Beispiel liegt ein Wahrscheinlichkeitsfeld vor, das nach dem
SHANNON-FANO-Verfahren nur eine einzige Aufteilungsmöglichkeit zulässt.
Dass dies nicht immer so sein muss, zeigt z. B. das folgende Wahrscheinlich-
keitsfeld mit drei verschiedenen Aufteilungsmöglichkeiten und damit unter-
schiedlichen Kodierungsmöglichkeiten:
0
,
40 0 0 00
0
,
20 100 100 01
0
,
10 101 101 100
0
,
10 1100 110 101
0
,
10 1101 1110 110
0
,
05 1110 11110 1110
0
,
05 1111 11111 1111
Der Leser möge sich selbst davon überzeugen, dass diese drei möglichen Kodes
in dem Sinne gleichwertig sind, dass sie die gleiche Koderedundanz aufweisen.
3.4.2.2 HUFFMAN-Verfahren (1952)
Diesem Kodierungsverfahren liegt folgender Algorithmus zugrunde:
1. Ordnen des gegebenen Wahrscheinlichkeitsfeldes nach fallenden Werten.
2. Zusammenfassen der letzten zwei Wahrscheinlichkeiten (die mit den kleins-
ten Werten) zu einem neuen Wert (s. Bild 3.4.1).
3. Erneutes Ordnen des reduzierten Wahrscheinlichkeitsfeldes entsprechend
Schritt 1.
4. Wiederholen der Schritte 2. und 3. solange, bis die Zusammenfassung der
beiden letzten Elemente den Wert 1 ergibt.
5. Aufstellen eines Kodebaumes entsprechend dem Reduktionsschema und Zu-
ordnung der Kodesymbole 0 und 1. Auslesen der Kodewörter vom Wurzel-
knoten zu den Blattknoten, notwendig zur Erfüllung der Dekodierbarkeits-
bedingung gemäß Definition 3.2.1.
Beispiel 3.4.2
Für das gegebene Wahrscheinlichkeitsfeld im Beispiel 3.4.1 ist ein Optimalkode
nach dem HUFFMAN-Verfahren zu entwerfen und mit dem entsprechenden
SHANNON-FANO-Kode zu vergleichen.
Lösung:
Gemäß dem Algorithmus ergibt sich folgendes Lösungsschema:
1.
(
p
i
)=(0
,
40 0
,
18 0
,
14 0
,
10 0
,
08 0
,
05 0
,
05)
Die Schritte 2. bis 4. (Reduktionsschema) und 5. (Kodebaum) sind im Bild
3.4.1 dargestellt.