Exercise 2.6Z: Again on the Huffman Code

From LNTwww
Revision as of 15:28, 28 May 2021 by Javier (talk | contribs) (Text replacement - "„" to """)

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:


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

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  0  der Beginn des Codewortes  01  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.