Aufgaben:Aufgabe 2.6Z: Nochmals zum Huffman–Code: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 75: Zeile 75:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>. Die Grafik zeigt die Konstruktion des Huffman&ndash;Codes mittels Baumdiagramm. Mit der Zuordnung rot &#8594; <b>1</b> und blau &#8594; <b>0</b> kommt man zu folgendem Code: &nbsp;
+
[[Datei:Inf_Z_2_6a_version2.png|right|frame|Huffman–Baumdiagramme zu den Teilaufgaben (1) und (3)]]
&nbsp; &nbsp; <b>A</b> &#8594; <b>11</b>, <b>B</b> &#8594; <b>10</b>, <b>C</b> &#8594; <b>01</b>, <b>D</b> &#8594; <b>001</b>, <b>E</b> &#8594; <b>000</b>.  
+
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>.  
 +
*Die Grafik zeigt die Konstruktion des Huffman&ndash;Codes mittels Baumdiagramm.  
 +
*Mit der Zuordnung rot &#8594; <b>1</b> und blau &#8594; <b>0</b> erhält man den Code: &nbsp; $\rm A$ &#8594; <b>11</b>, $\rm B$ &#8594; <b>10</b>, $\rm C$ &#8594; <b>01</b>, $\rm D$ &#8594; <b>001</b>, $\rm E$ &#8594; <b>000</b>.  
  
[[Datei:Inf_Z_2_6a_version2.png|Huffman–Baumdiagramme zu den Teilaufgaben (1) und (3)]]
 
 
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 den genau gleichen Code.
 
  
 +
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 den genau gleichen Code.
 +
<br clear=all>
 
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>, wie auch die folgende Rechnung zeigt:
 
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>, 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},$$
 
:$$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},$$
Zeile 87: Zeile 88:
 
\approx 2.0\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
 
\approx 2.0\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
  
*Nach dem Quellencodierungstheorem gilt stets <i>L</i><sub>M</sub> &#8805; <i>H</i>.  
+
*Nach dem Quellencodierungstheorem gilt stets $L_{\rm M} \ge H$.  
*Voraussetzung für <i>L</i><sub>M</sub> = <i>H</i> ist allerdings, dass alle Symbolwahrscheinlichkeiten in der Form 2<sup>&ndash;<i>k</i></sup> (<i>k</i> = 1, 2, 3, ...) dargestellt werden können, was hier nicht zutrifft.
+
*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)'''&nbsp; <b>A</b>, <b>B</b>, <b>C</b> werden beim Code 1 durch zwei Bit dargestellt, <b>E</b>, <b>F</b> durch drei Bit. Damit erhält man für
+
'''(3)'''&nbsp; $\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
 
* die mittlere Codewortlänge
Zeile 103: Zeile 105:
 
:$$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}  
 
:$$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}.$$
 
\Rightarrow\hspace{0.3cm} L_{\rm M} = H = 2.25\,{\rm bit/Quellensymbol} \hspace{0.05cm}.$$
Man erkennt: Mit diesen &bdquo;günstigeren&rdquo; Wahrscheinlichkeiten ergibt sich sogar eine größere mittlere Codewortlänge als mit den &bdquo;ungünstigeren&rdquo;. Die Gleichheit (<i>L</i><sub>M</sub> = <i>H</i>) ist allein auf die nun größere Quellenentropie zurückzuführen.
+
Man erkennt:  
 +
*Mit diesen &bdquo;günstigeren&rdquo; Wahrscheinlichkeiten ergibt sich sogar eine größere mittlere Codewortlänge als mit den &bdquo;ungünstigeren&rdquo;.  
 +
*Die Gleichheit $(L_{\rm M} = H)$ ist allein auf die nun größere Quellenentropie zurückzuführen.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; 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.01cm}' \ge L_{\rm M})$ möglich.
 +
*Das heißt: &nbsp; <u>Alle Aussagen</u> sind zutreffend.
  
'''(4)'''&nbsp; Beispielsweise liefert eine (von vielen) Simulationen mit den Wahrscheinlichkeiten gemäß der Teilaufgabe (3) die Folge <b>EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB</b> (mit <i>N</i> = 40 Zeichen). 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 (<i>L</i><sub>M</sub> = 2.25 bit/Quellensymbol). Bei anderem Startwert des Zufallsgenerators ist aber auch <i>L</i>&prime;<sub>M</sub> &#8805; <i>L</i><sub>M</sub> möglich. <u>Alle Aussagen</u> sind zutreffend.
 
  
  
 
'''(5)'''&nbsp; Richtig ist nur der <u>Lösungsvorschlag 1</u>:
 
'''(5)'''&nbsp; Richtig ist nur der <u>Lösungsvorschlag 1</u>:
* Code 1 ist ein Huffman&ndash;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).
+
* $\text{Code 1}$ ist ein Huffman&ndash;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)'''.
 +
 
 +
 
 +
* $\text{Code 2}$ ist kein Huffman&ndash;Code, da ein solcher stets präfixfrei sein müsste. Die Präfixfreiheit ist hier aber nicht gegeben, da <b>0</b> der Beginn des Codewortes <b>01</b> ist.
  
* Code 2 ist kein Huffman&ndash;Code, da ein solcher stets präfixfrei sein müsste. Die Präfixfreiheit ist hier aber nicht gegeben, da <b>0</b> der Beginn des Codewortes <b>01</b> ist.
 
  
* Code 3 ist ebenfalls kein Huffman&ndash;Code, da er eine um <i>p</i><sub>C</sub> (Wahrscheinlichkeit von <b>C</b>) größere mittlere Codewortlänge aufweist als erforderlich (Code 1). Er ist somit nicht optimal: Es gibt keine Symbolwahrscheinlichkeiten <i>p</i><sub>A</sub>, ... , <i>p</i><sub>E</sub>, die es rechtfertigen würden, das Symbol <b>C</b> mit <b>010</b> anstelle von <b>01</b> zu codieren.
+
* $\text{Code 3}$ ist ebenfalls kein Huffman&ndash;Code, da er eine um $p_{\rm C}$  (Wahrscheinlichkeit von $\rm C$ größere mittlere Codewortlänge aufweist als erforderlich $(\text{Code 1})$.  
 +
*Er ist somit nicht optimal: &nbsp; Es gibt keine Symbolwahrscheinlichkeiten $p_{\rm A}$, ... , $p_{\rm E}$, die es rechtfertigen würden, das Symbol $\rm C$ mit <b>010</b> anstelle von <b>01</b> zu codieren.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 28. September 2018, 09:52 Uhr

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


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

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


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


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