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

Aus LNTwww
Wechseln zu:Navigation, Suche
(13 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Entropiecodierung nach Huffman
+
{{quiz-Header|Buchseite=Informationstheorie/Entropiecodierung nach Huffman
 
}}
 
}}
  
[[Datei:P_ID2453__Inf_Z_2_6.png|right|]]
+
[[Datei:P_ID2453__Inf_Z_2_6.png|right|frame|Drei Codes zur Auswahl ]]
Der Algorithmus von David A. Huffman realisiert eine Entropiecodierung mit folgenden Eigenschaften:
+
Der Algorithmus von  [https://de.wikipedia.org/wiki/David_A._Huffman 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 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 <i>L</i><sub>M</sub>.
+
* Der Code führt bei gedächtnisloser Quelle zur kleinstmöglichen  mittleren Codewortlänge&nbsp; $L_{\rm M}$.
  
:* <i>L</i><sub>M</sub> ist aber nie kleiner als die Quellenentropie <i>H</i>. Diese beiden Größen sind allein aus den <i>M</i> Symbolwahrscheinlichkeiten berechenbar.
+
* $L_{\rm M}$&nbsp; ist aber nie kleiner als die Quellenentropie&nbsp; $H$.  
 +
*Diese beiden Größen sind allein aus den&nbsp; $M$&nbsp; Symbolwahrscheinlichkeiten berechenbar.
  
Vorausgesetzt wird für diese Aufgabe eine gedächtnislose Quelle mit dem Symbolumfang <i>M</i> = 5 und dem Alphabet {<b>A</b>, <b>B</b>, <b>C</b>, <b>D</b>, <b>E</b>}. In obiger Grafik sind drei Codes vorgegeben. Sie sollen entscheiden, welche dieser Codes durch Anwendung des Huffman&ndash;Algorithmus entstanden sind (oder sein könnten).
 
  
<b>Hinweis:</b> Die Aufgabe gehört zum Kapitel 2.3. Weitere Informationen zum Huffman&ndash;Algorithmus finden Sie auch im Angabenblatt zur Aufgabe A2.6. Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung.
+
Vorausgesetzt wird für diese Aufgabe eine gedächtnislose Quelle mit dem Symbolumfang&nbsp; $M = 5$&nbsp; und dem Alphabet
 +
:$$\{ {\rm A},\ {\rm B},\ {\rm C},\ {\rm D},\ {\rm E} \}.$$
 +
 
 +
In obiger Grafik sind drei Codes vorgegeben.&nbsp; Sie sollen entscheiden, welche dieser Codes durch Anwendung des Huffman&ndash;Algorithmus entstanden sind (oder sein könnten).
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum Kapitel&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
 +
*Weitere Informationen zum Huffman&ndash;Algorithmus finden Sie auch im Angabenblatt zur&nbsp; [[Aufgaben:2.6_Zur_Huffman-Codierung|Aufgabe 2.6]].
 +
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul&nbsp; [[Applets:Huffman-_und_Shannon-Fano-Codierung|Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].
 +
  
  
Zeile 20: Zeile 35:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Codes liefert Huffman für <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = <i>p</i><sub>C</sub> = 0.3, <i>p</i><sub>D</sub> = <i>p</i><sub>E</sub> = 0.05?
+
{Welche Codes könnten entsprechend Huffman für&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C= 0.3$&nbsp; und&nbsp; $p_{\rm D} = p_{\rm E= 0.05$&nbsp; entstanden sein?
 
|type="[]"}
 
|type="[]"}
+ Code 1,
+
+ $\text{Code 1}$,
- Code 2,
+
- $\text{Code 2}$,
- Code 3.
+
- $\text{Code 3}$.
  
  
{Wie stehen mittlere Codewortlänge <i>L</i><sub>M</Sub> und Entropie <i>H</i> in Relation?
+
{Wie stehen die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; und die Entropie&nbsp; $H$&nbsp; bei den gegebenen Wahrscheinlichkeiten in Relation?
|type="[]"}
+
|type="()"}
- <i>L</i><sub>M</Sub> < <i>H</i>,
+
- $L_{\rm M} < H$,
- <i>L</i><sub>M</Sub> = <i>H</i>,
+
- $L_{\rm M} \ge H$,
+ <i>L</i><sub>M</Sub> > <i>H</i>.
+
+ $L_{\rm M} > H$.
  
  
{Mit welchen Symbolwahrscheinlichkeiten würde hier <i>L</i><sub>M</Sub> = <i>H</i> gelten?
+
{Betrachten Sie den&nbsp; $\text{Code 1}$.&nbsp; Mit welchen Symbolwahrscheinlichkeiten würde&nbsp; $L_{\rm M} = H$&nbsp; gelten?
 
|type="{}"}
 
|type="{}"}
$p_A$ = { 0.25 3% }
+
$\ p_{\rm A} \ = \ $ { 0.25 3% }
$p_B$ = { 0.25 3% }
+
$\ p_{\rm B} \ = \ $ { 0.25 3% }
$p_C$ = { 0.25 3% }
+
$\ p_{\rm C} \ = \ $ { 0.25 3% }
$p_D$ = { 0.125 3% }
+
$\ p_{\rm D} \ = \ $ { 0.125 3% }
$p_E$ = { 0.125 3% }
+
$\ p_{\rm E} \ = \ $ { 0.125 3% }
  
  
{Die Angaben zu (3) gelten weiter. Die mittlere Codewortlänge wird aber nun für eine Folge der Länge <i>N</i> = 40 ermittelt &nbsp;&#8658;&nbsp; <i>L</i><sub>M</sub>&prime;. Was ist möglich?
+
{Die in der Teilaufgabe&nbsp; '''(3)'''&nbsp; berechneten Wahrscheinlichkeiten gelten weiter. <br>Die mittlere Codewortlänge wird aber nun für eine Folge der Länge&nbsp; $N = 40$&nbsp; ermittelt &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.03cm}'$. Was ist möglich?
 
|type="[]"}
 
|type="[]"}
+ <i>L</i><sub>M</sub>&prime; < <i>L</i><sub>M</sub>,
+
+ $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,
+ <i>L</i><sub>M</sub>&prime; = <i>L</i><sub>M</sub>,
+
+ $L_{\rm M}\hspace{0.01cm}' = L_{\rm M}$,
+ <i>L</i><sub>M</sub>&prime; > <i>L</i><sub>M</sub>.
+
+ $L_{\rm M}\hspace{0.01cm}' > L_{\rm M}$.
  
  
 
{Welcher Code könnte überhaupt ein Huffman&ndash;Code sein?
 
{Welcher Code könnte überhaupt ein Huffman&ndash;Code sein?
 
|type="[]"}
 
|type="[]"}
+ Code 1,
+
+ $\text{Code 1}$,
- Code 2,
+
- $\text{Code 2}$,
- Code 3.
+
- $\text{Code 3}$.
  
  
Zeile 62: Zeile 77:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;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 <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>. Richtig ist der <u>Lösungsvorschlag 1</u>.
+
[[Datei:Inf_Z_2_6a_version2.png|right|frame|Huffman–Baumdiagramme zu den Teilaufgaben&nbsp; '''(1)'''&nbsp; und&nbsp; '''(3)''']]
[[Datei:P_ID2454__Inf_Z_2_6a.png|center|]]
+
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>.
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.
+
*Die Grafik zeigt die Konstruktion des Huffman&ndash;Codes mittels Baumdiagramm.  
 +
*Mit der Zuordnung rot &nbsp; &#8594; &nbsp; <b>1</b> und blau &nbsp; &#8594; &nbsp; <b>0</b> erhält man: &nbsp; <br>$\rm A$ &nbsp; &#8594; &nbsp; <b>11</b>, $\rm B$ &nbsp; &#8594; &nbsp; <b>10</b>, $\rm C$ &nbsp; &#8594; &nbsp; <b>01</b>, $\rm D$ &nbsp; &#8594; &nbsp; <b>001</b>, $\rm E$ &nbsp; &#8594; &nbsp; <b>000</b>.  
 +
*Die linke Grafik gilt für die Wahrscheinlichkeiten gemäß Teilaufgabe&nbsp; '''(1)'''.&nbsp;
 +
*Das rechte Diagramm gehört zur Teilaufgabe&nbsp; '''(3)'''&nbsp; mit etwas anderen Wahrscheinlichkeiten.&nbsp;
 +
*Es liefert aber genau den gleichen Code.
 +
<br clear=all>
 +
'''(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},$$
 +
:$$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&nbsp; $L_{\rm M} \ge H$.
 +
*Voraussetzung für&nbsp; $L_{\rm M} = H$&nbsp; ist allerdings, dass alle Symbolwahrscheinlichkeiten in der Form&nbsp; $2^{-k} \ (k = 1, \ 2, \ 3,\ \text{ ...})$&nbsp; dargestellt werden können.
 +
*Dies trifft hier nicht zu.
 +
 
  
<b>b)</b>&nbsp;&nbsp;Nach dem Quellencodierungstheorem gilt stets <i>L</i><sub>M</sub> &#8805; <i>H</i>. 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. Richtig ist demnach <u>Lösungsvorschlag 3</u>, wie auch die folgende Rechnung (mit &bdquo;log<sub>2</sub>&rdquo; &nbsp;&#8658;&nbsp; &bdquo;ld&rdquo;) 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}.$$
 
  
<b>3.</b>&nbsp;&nbsp;<b>A</b>, <b>B</b>, <b>C</b> werden beim Code 1 durch 2 Bit dargestellt, <b>E</b>, <b>F</b> durch 3 Bit. Damit erhält man für
+
'''(3)'''&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; und&nbsp; $\rm C$&nbsp; werden beim&nbsp; $\text{Code 1}$&nbsp; durch zwei Bit dargestellt,&nbsp; $\rm E$&nbsp; und&nbsp; $\rm F$&nbsp; durch drei Bit.&nbsp; Damit erhält man für
  
:* die mittlere Codewortlänge
+
* 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
 
:$$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},$$
 
\hspace{0.05cm},$$
:* für die Quellenentropie:
+
* 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  
+
:$$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 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}}
+
{\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}.$$
 
\hspace{0.05cm}.$$
 
Durch Vergleich aller Terme kommt man zum Ergebnis:
 
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}$$
+
:$$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. 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&nbsp; $(L_{\rm M} = H)$&nbsp; ist demzufolge allein auf die nun größere Quellenentropie zurückzuführen.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Beispielsweise liefert eine (von vielen) Simulationen mit den Wahrscheinlichkeiten gemäß der Teilaufgabe&nbsp; '''(3)'''&nbsp; die Folge  mit&nbsp; $N = 40$&nbsp; Zeichen:
 +
:$$\rm EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB.$$
 +
 
 +
*Es ergibt sich&nbsp; $L_{\rm M}\hspace{0.01cm}' = ( 34 \cdot 2 + 6 \cdot 3)/50  = 2.15$&nbsp; bit/Quellensymbol, also ein kleinerer Wert als für die unbegrenzte Folge&nbsp; $(L_{\rm M} = 2.25$ bit/Quellensymbol$)$.
 +
*Bei anderem Startwert des Zufallsgenerators ist aber auch&nbsp; $(L_{\rm M}\hspace{0.03cm}' \ge L_{\rm M})$&nbsp; möglich.
 +
*Das heißt: &nbsp; <u>Alle &nbsp;Aussagen</u> sind zutreffend.
  
<b>4.</b>&nbsp;&nbsp;Beispielsweise liefert eine (von vielen) Simulationen mit den Wahrscheinlichkeiten gemäß der Teilaufgabe (c) die Folge <b>EBDCCBDABEBABCCCCCBCAABECAACCBAABBBCDCAB</b> (mit <nobr><i>N</i> = 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 (<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.
 
  
<b>5.</b>&nbsp;&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 (a) und (c).
+
'''(5)'''&nbsp; Richtig ist nur der <u>Lösungsvorschlag 1</u>:
 +
* Der&nbsp; $\text{Code 1}$&nbsp; ist ein Huffman&ndash;Code, wie schon in den vorherigen Teilaufgaben gezeigt wurde. <br>Dies gilt zwar nicht für alle Symbolwahrscheinlichkeiten, aber zumindest für die Parametersätze gemäß den Teilaufgaben&nbsp; '''(1)'''&nbsp; und&nbsp; '''(3)'''.
  
:* 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.
+
* Der&nbsp; $\text{Code 2}$&nbsp; ist kein Huffman&ndash;Code, da ein solcher stets präfixfrei sein müsste. <br>Die Präfixfreiheit ist hier aber nicht gegeben, da&nbsp; <b>0</b>&nbsp; der Beginn des Codewortes&nbsp; <b>01</b>&nbsp; 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.
+
* Der&nbsp; $\text{Code 3}$&nbsp; ist ebenfalls kein Huffman&ndash;Code, da er eine um&nbsp;  $p_{\rm C}$&nbsp;  größere mittlere Codewortlänge aufweist als erforderlich&nbsp; $($siehe $\text{Code 1})$. Er ist nicht optimal.&nbsp; <br>Es gibt keine Symbolwahrscheinlichkeiten&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm E}$, die es rechtfertigen würden, das Symbol&nbsp; $\rm C$&nbsp; mit&nbsp; <b>010</b>&nbsp; anstelle von&nbsp; <b>01</b>&nbsp; zu codieren.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 25. Januar 2020, 16:25 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 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.