Exercise 2.6Z: Again on the Huffman Code

From LNTwww

P ID2453 Inf Z 2 6.png

Der Algorithmus von David A. 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 einer gedächtnislosen Quelle zur kleinstmöglichen mittleren Codewortlänge LM.
  • LM 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 {A, B, C, D, 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).

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


Fragebogen

1

Welche Codes liefert Huffman für pA = pB = pC = 0.3, pD = pE = 0.05?

Code 1,
Code 2,
Code 3.

2

Wie stehen mittlere Codewortlänge LM und Entropie H in Relation?

LM < H,
LM = H,
LM > H.

3

Mit welchen Symbolwahrscheinlichkeiten würde hier LM = H gelten?

$p_A$ =

$p_B$ =

$p_C$ =

$p_D$ =

$p_E$ =

4

Die Angaben zu (3) gelten weiter. Die mittlere Codewortlänge wird aber nun für eine Folge der Länge N = 40 ermittelt  ⇒  LM′. Was ist möglich?

LM′ < LM,
LM′ = LM,
LM′ > LM.

5

Welcher Code könnte überhaupt ein Huffman–Code sein?

Code 1,
Code 2,
Code 3.


Musterlösung

1.  Die Grafik zeigt die Konstruktion des Huffman–Codes mittels Baumdiagramm. Mit der Zuordnung rot → 1 und blau → 0 kommt man zu folgendem Code A11, B10, C01, D001, E000. Richtig ist der Lösungsvorschlag 1.

P ID2454 Inf Z 2 6a.png

Die linke Grafik gilt für die Wahrscheinlichkeiten gemäß Teilaufgabe (a). Das rechte Diagramm gehört zur Teilaufgabe (3) mit etwas anderen Wahrscheinlichkeiten. Es liefert den genau gleichen Code.

b)  Nach dem Quellencodierungstheorem gilt stets LMH. Voraussetzung für LM = H ist allerdings, dass alle Symbolwahrscheinlichkeiten in der Form 2k (k = 1, 2, 3, ...) dargestellt werden können. Richtig ist demnach Lösungsvorschlag 3, wie auch die folgende Rechnung (mit „log2”  ⇒  „ld”) 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 ld}\hspace{0.15cm}(1/0.3) + 2 \cdot 0.05 \cdot {\rm ld}\hspace{0.15cm}(1/0.05) \approx 2.0\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

3.  A, B, C werden beim Code 1 durch 2 Bit dargestellt, E, F durch 3 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 ld}\hspace{0.15cm}\frac{1}{p_{\rm A}} + p_{\rm B}\cdot {\rm ld}\hspace{0.15cm}\frac{1}{p_{\rm B}} + p_{\rm C}\cdot {\rm ld}\hspace{0.15cm}\frac{1}{p_{\rm C}} + p_{\rm D}\cdot {\rm ld}\hspace{0.15cm}\frac{1}{p_{\rm D}} + p_{\rm E}\cdot {\rm ld}\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}$$
$$\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. Die Gleichheit (LM = 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 (c) die Folge EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB (mit <nobr>N = 40 Zeichen).</nobr> Damit ergibt sich:

$$L_{\rm M}' = ( 34 \cdot 2 + 6 \cdot 3)/50 = 2.15\,{\rm bit/Quellensymbol} \hspace{0.05cm},$$

also ein kleinerer Wert als für die unendlich lange Folge (LM = 2.25 bit/Quellensymbol). Bei anderem Startwert des Zufallsgenerators ist aber auch LMLM möglich. Alle Aussagen sind zutreffend.

5.  Richtig ist nur der Lösungsvorschlag 1.

  • 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 (a) und (c).
  • 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.
  • Code 3 ist ebenfalls kein Huffman–Code, da er eine um pC (Wahrscheinlichkeit von C) größere mittlere Codewortlänge aufweist als erforderlich (Code 1). Er ist somit nicht optimal: Es gibt keine Symbolwahrscheinlichkeiten pA, ... , pE, die es rechtfertigen würden, das Symbol C mit 010 anstelle von 01 zu codieren.