Aufgaben:Aufgabe 2.6Z: Nochmals zum Huffman–Code

• Zurück zum Buch

Drei Binärcodes 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:  Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version.

Fragebogen

1

Welche Codes könnten entsprechend Huffman für  $p_{\rm A} = p_{\rm B} = p_{\rm C} = 0.3$  und  $p_{\rm D} = p_{\rm E} = 0.05$  entstanden sein?

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

2

Wie stehen die mittlere Codewortlänge  $L_{\rm M}$  und die Entropie  $H$  bei den gegebenen Wahrscheinlichkeiten in Relation?

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

3

Betrachten Sie den  $\text{Code 1}$.  Mit welchen Symbolwahrscheinlichkeiten würde  $L_{\rm M} = H$  gelten?

$\ p_{\rm A} \ = \ $

$\ p_{\rm B} \ = \ $

$\ p_{\rm C} \ = \ $

$\ p_{\rm D} \ = \ $

$\ p_{\rm E} \ = \ $

4

Die in der Teilaufgabe  (3)  berechneten Wahrscheinlichkeiten gelten weiter.
Die mittlere Codewortlänge wird aber nun für eine Folge der Länge  $N = 40$  ermittelt  ⇒  $L_{\rm M}\hspace{0.03cm}'$.  Was ist möglich?

	$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}$.

5

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

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

Musterlösung

Musterlösung

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:  
  $\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 aber genau den 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 demzufolge 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.03cm}' \ge L_{\rm M})$  möglich.
• Das heißt:   Alle  Aussagen sind zutreffend.

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

• Der  $\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).

• Der  $\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  1  der Beginn des Codewortes  10  ist.

• Der  $\text{Code 3}$  ist ebenfalls kein Huffman–Code, da er eine um  $p_{\rm C}$  größere mittlere Codewortlänge aufweist als erforderlich  $($siehe $\text{Code 1})$. Er ist 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.