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

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2453__Inf_Z_2_6.png|right|Drei Codes zur Auswahl ]]
+
[[Datei:P_ID2453__Inf_Z_2_6.png|right|frame|Drei Codes zur Auswahl ]]
Der Algorithmus von [https://de.wikipedia.org/wiki/David_A._Huffman David Albert 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 gedächtnisloser Quelle zur kleinstmöglichen  mittleren Codewortlänge $L_{\rm M}$.
+
* 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).
 +
 
 +
 
 +
 
  
* $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 $\{$<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).
 
  
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
+
*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 [[Aufgaben:2.6_Zur_Huffman-Codierung|Aufgabe 2.6]].
+
*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 [[Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].
+
*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 25: Zeile 35:
  
 
<quiz display=simple>
 
<quiz display=simple>
{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?
+
{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="[]"}
 
+ $\text{Code 1}$,
 
+ $\text{Code 1}$,
Zeile 32: Zeile 42:
  
  
{Wie stehen mittlere Codewortlänge $L_{\rm M}$ und Entropie $H$ bei den gegebenen Wahrscheinlichkeiten 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="()"}
 
- $L_{\rm M} < H$,
 
- $L_{\rm M} < H$,
 
- $L_{\rm M} \ge H$,
 
- $L_{\rm M} \ge H$,
Zeile 39: Zeile 49:
  
  
{Betrachten Sie $\text{Code 1}$. Mit welchen Symbolwahrscheinlichkeiten würde $L_{\rm M} = H$ gelten?
+
{Betrachten Sie den&nbsp; $\text{Code 1}$.&nbsp; Mit welchen Symbolwahrscheinlichkeiten würde&nbsp; $L_{\rm M} = H$&nbsp; gelten?
 
|type="{}"}
 
|type="{}"}
 
$\ p_{\rm A} \ = \ $ { 0.25 3% }
 
$\ p_{\rm A} \ = \ $ { 0.25 3% }
Zeile 48: Zeile 58:
  
  
{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 &nbsp;&#8658;&nbsp; $L_{\rm M}'$. 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="[]"}
+ $L_{\rm M}' < L_{\rm M}$,
+
+ $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,
+ $L_{\rm M}' = L_{\rm M}$,
+
+ $L_{\rm M}\hspace{0.01cm}' = L_{\rm M}$,
+ $L_{\rm M}' > L_{\rm M}$.
+
+ $L_{\rm M}\hspace{0.01cm}' > L_{\rm M}$.
  
  
Zeile 67: Zeile 77:
 
===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&nbsp; '''(1)'''&nbsp; und&nbsp; '''(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.  
[[Datei:Inf_Z_2_6a_version2.png|Huffman–Baumdiagramme zu den Teilaufgaben (1) und (3)]]
+
*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;
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.
+
*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:
 
'''(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 79: Zeile 90:
 
\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&nbsp; $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&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.
  
  
'''(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$,&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
Zeile 95: Zeile 108:
 
:$$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&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.
  
'''(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).
+
* 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.