Aufgaben:Aufgabe 2.6Z: Nochmals zum Huffman–Code: Unterschied zwischen den Versionen
Nabil (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Entropiecodierung nach Huffman }} right| Der Algorithmus v…“) |
Nabil (Diskussion | Beiträge) |
||
Zeile 100: | Zeile 100: | ||
− | [[Category:Aufgaben zu | + | [[Category:Aufgaben zu Informationstheorie und Quellencodierung|^2.3 Entropiecodierung nach Huffman^]] |
Version vom 7. Oktober 2016, 23:24 Uhr
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
Musterlösung
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 LM ≥ H. Voraussetzung für LM = H ist allerdings, dass alle Symbolwahrscheinlichkeiten in der Form 2–k (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 L′M ≥ LM 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.