Aufgabe 2.6Z: Nochmals zum Huffman–Code
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
Musterlösung
(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.
