Exercise 2.6Z: Again on the Huffman Code

Drei Codes zur Auswahl

Der Algorithmus von David Albert Huffman realisiert eine Entropiecodierung mit folgenden Eigenschaften:

Der entstehende Binärcode ist präfixfrei und somit in einfacher Weise (und sofort) decodierbar.

Der Code führt bei gedächtnisloser Quelle zur kleinstmöglichen mittleren Codewortlänge $L_{\rm M}$.

$L_{\rm M}$ ist aber nie kleiner als die Quellenentropie $H$.
Diese beiden Größen sind allein aus den $M$ Symbolwahrscheinlichkeiten berechenbar.

Vorausgesetzt wird für diese Aufgabe eine gedächtnislose Quelle mit dem Symbolumfang $M = 5$ und dem Alphabet

$$\{ {\rm A},\ {\rm B},\ {\rm C},\ {\rm D},\ {\rm E} \}.$$

In obiger Grafik sind drei Codes vorgegeben. Sie sollen entscheiden, welche dieser Codes durch Anwendung des Huffman–Algorithmus entstanden sind (oder sein könnten).

Hinweise:

Die Aufgabe gehört zum Kapitel Entropiecodierung nach Huffman.
Weitere Informationen zum Huffman–Algorithmus finden Sie auch im Angabenblatt zur Aufgabe 2.6.
Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul Shannon–Fano– und Huffman–Codierung.

Fragebogen

Musterlösung

Solution

Huffman–Baumdiagramme zu den Teilaufgaben (1) und (3)

(1) Richtig ist der Lösungsvorschlag 1.

Die Grafik zeigt die Konstruktion des Huffman–Codes mittels Baumdiagramm.
Mit der Zuordnung rot → 1 und blau → 0 erhält man den Code: $\rm A$ → 11, $\rm B$ → 10, $\rm C$ → 01, $\rm D$ → 001, $\rm E$ → 000.

Die linke Grafik gilt für die Wahrscheinlichkeiten gemäß Teilaufgabe (1). Das rechte Diagramm gehört zur Teilaufgabe (3) mit etwas anderen Wahrscheinlichkeiten. Es liefert den genau gleichen Code.
(2) Richtig ist der Lösungsvorschlag 3, wie auch die folgende Rechnung zeigt:

$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (0.3 + 0.3 + 0.3) \cdot 2 + (0.05 + 0.05) \cdot 3 = 2.1\,{\rm bit/Quellensymbol}\hspace{0.05cm},$$

$$H \hspace{0.2cm} = \hspace{0.2cm} 3 \cdot 0.3 \cdot {\rm log_2}\hspace{0.15cm}(1/0.3) + 2 \cdot 0.05 \cdot {\rm log_2}\hspace{0.15cm}(1/0.05) \approx 2.0\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

Nach dem Quellencodierungstheorem gilt stets $L_{\rm M} \ge H$.
Voraussetzung für $L_{\rm M} = H$ ist allerdings, dass alle Symbolwahrscheinlichkeiten in der Form $2^{-k} \ (k = 1, 2, 3,\ \text{ ...})$ dargestellt werden können.
Dies trifft hier nicht zu.

(3) $\rm A$, $\rm B$ und $\rm C$ werden beim $\text{Code 1}$ durch zwei Bit dargestellt, $\rm E$ und $\rm F$ durch drei Bit. Damit erhält man für

die mittlere Codewortlänge

$$L_{\rm M} = p_{\rm A}\cdot 2 + p_{\rm B}\cdot 2 + p_{\rm C}\cdot 2 + p_{\rm D}\cdot 3 + p_{\rm E}\cdot 3 \hspace{0.05cm},$$

für die Quellenentropie:

$$H = p_{\rm A}\cdot {\rm log_2}\hspace{0.15cm}\frac{1}{p_{\rm A}} + p_{\rm B}\cdot {\rm log_2}\hspace{0.15cm}\frac{1}{p_{\rm B}} + p_{\rm C}\cdot {\rm log_2}\hspace{0.15cm}\frac{1}{p_{\rm C}} + p_{\rm D}\cdot {\rm log_2}\hspace{0.15cm}\frac{1}{p_{\rm D}} + p_{\rm E}\cdot {\rm log_2}\hspace{0.15cm}\frac{1}{p_{\rm E}} \hspace{0.05cm}.$$

Durch Vergleich aller Terme kommt man zum Ergebnis:

$$p_{\rm A}= p_{\rm B}= p_{\rm C}\hspace{0.15cm}\underline{= 0.25} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm D}= p_{\rm E}\hspace{0.15cm}\underline{= 0.125}\hspace{0.3cm} \Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Man erkennt:

Mit diesen „günstigeren” Wahrscheinlichkeiten ergibt sich sogar eine größere mittlere Codewortlänge als mit den „ungünstigeren”.
Die Gleichheit $(L_{\rm M} = H)$ ist allein auf die nun größere Quellenentropie zurückzuführen.

(4) Beispielsweise liefert eine (von vielen) Simulationen mit den Wahrscheinlichkeiten gemäß der Teilaufgabe (3) die Folge mit $N = 40$ Zeichen:

$$\rm EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB.$$

Es ergibt sich $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50 = 2.15$ bit/Quellensymbol, also ein kleinerer Wert als für die unbegrenzte Folge $(L_{\rm M} = 2.25$ bit/Quellensymbol$)$.
Bei anderem Startwert des Zufallsgenerators ist aber auch $(L_{\rm M}\hspace{0.01cm}' \ge L_{\rm M})$ möglich.
Das heißt: Alle Aussagen sind zutreffend.

(5) Richtig ist nur der Lösungsvorschlag 1:

$\text{Code 1}$ ist ein Huffman–Code, wie schon in den vorherigen Teilaufgaben gezeigt wurde.
Dies gilt zwar nicht für alle Symbolwahrscheinlichkeiten, aber zumindest für die Parametersätze gemäß den Teilaufgaben (1) und (3).

$\text{Code 2}$ ist kein Huffman–Code, da ein solcher stets präfixfrei sein müsste. Die Präfixfreiheit ist hier aber nicht gegeben, da 0 der Beginn des Codewortes 01 ist.

$\text{Code 3}$ ist ebenfalls kein Huffman–Code, da er eine um $p_{\rm C}$ (Wahrscheinlichkeit von $\rm C$ größere mittlere Codewortlänge aufweist als erforderlich $(\text{Code 1})$.
Er ist somit nicht optimal: Es gibt keine Symbolwahrscheinlichkeiten $p_{\rm A}$, ... , $p_{\rm E}$, die es rechtfertigen würden, das Symbol $\rm C$ mit 010 anstelle von 01 zu codieren.

	$L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,
	$L_{\rm M}\hspace{0.01cm}' = L_{\rm M}$,
	$L_{\rm M}\hspace{0.01cm}' > L_{\rm M}$.

	$\text{Code 1}$,
	$\text{Code 2}$,
	$\text{Code 3}$.

	$L_{\rm M} < H$,
	$L_{\rm M} \ge H$,
	$L_{\rm M} > H$.

	$\text{Code 1}$,
	$\text{Code 2}$,
	$\text{Code 3}$.