Aufgaben:Aufgabe 2.6Z: Nochmals zum Huffman–Code - Versionsgeschichte

Guenter am 10. August 2021 um 14:48 Uhr

2021-08-10T14:48:12Z

Guenter am 10. August 2021 um 14:15 Uhr

2021-08-10T14:15:12Z

Guenter am 10. August 2021 um 14:13 Uhr

2021-08-10T14:13:38Z

Guenter am 10. August 2021 um 14:08 Uhr

2021-08-10T14:08:12Z

Guenter am 25. Januar 2020 um 15:25 Uhr

2020-01-25T15:25:03Z

Guenter am 25. Januar 2020 um 14:49 Uhr

2020-01-25T14:49:33Z

Guenter am 25. Januar 2020 um 14:44 Uhr

2020-01-25T14:44:40Z

Guenter am 25. Januar 2020 um 14:42 Uhr

2020-01-25T14:42:58Z

Guenter am 28. September 2018 um 08:52 Uhr

2018-09-28T08:52:37Z

Guenter am 28. September 2018 um 08:13 Uhr

2018-09-28T08:13:32Z

@@ Zeile 126: / Zeile 126: @@
 * 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)'''.
-* 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.
+* 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>1</b>&nbsp; der Beginn des Codewortes&nbsp; <b>10</b>&nbsp; ist.
 * 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.

@@ Zeile 28: / Zeile 28: @@
 *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_Shannon_Fano|Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&ndash;Version]].
+*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul:&nbsp; [[Applets:Huffman_Shannon_Fano|Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&ndash;Version]].
@@ Zeile 58: / Zeile 58: @@
-{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?
+{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}'$.&nbsp; Was ist möglich?
 |type="[]"}
 + $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,

@@ Zeile 25: / Zeile 25: @@
-''Hinweise:''
+<u>Hinweise:</u>
 *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]].
+Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul:&nbsp; [[Applets:Huffman_Shannon_Fano|Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&ndash;Version]].

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2453__Inf_Z_2_6.png|right|frame|Drei Codes zur Auswahl ]]
+[[Datei:P_ID2453__Inf_Z_2_6.png|right|frame|Drei Binärcodes zur Auswahl ]]
 Der Algorithmus von&nbsp; [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]&nbsp; realisiert eine Entropiecodierung mit folgenden Eigenschaften:

@@ Zeile 77: / Zeile 77: @@
 ===Musterlösung===
 {{ML-Kopf}}
-[[Datei:Inf_Z_2_6a_version2.png|right|frame|Huffman–Baumdiagramme zu den Teilaufgaben (1) und (3)]]
+[[Datei:Inf_Z_2_6a_version2.png|right|frame|Huffman–Baumdiagramme zu den Teilaufgaben&nbsp; '''(1)'''&nbsp; und&nbsp; '''(3)''']]
 '''(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>.
+*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;
-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.
+*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:
@@ Zeile 90: / Zeile 90: @@
 \approx 2.0\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
-*Nach dem Quellencodierungstheorem gilt stets $L_{\rm M} \ge H$.
+*Nach dem Quellencodierungstheorem gilt stets&nbsp; $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.
+*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; $\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
@@ Zeile 109: / Zeile 110: @@
 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.
+*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 '''(3)''' die Folge  mit $N = 40$ Zeichen:
+'''(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 $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$)$.
+*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 $(L_{\rm M}\hspace{0.01cm}' \ge L_{\rm M})$ möglich.
+*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 Aussagen</u> sind zutreffend.
+*Das heißt: &nbsp; <u>Alle &nbsp;Aussagen</u> sind zutreffend.
 '''(5)'''&nbsp; Richtig ist nur der <u>Lösungsvorschlag 1</u>:
-* $\text{Code 1}$ ist ein Huffman&ndash;Code, wie schon in den vorherigen Teilaufgaben gezeigt wurde.
+* 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)'''.
-* $\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})$.
+* 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ß}}

@@ Zeile 35: / Zeile 35: @@
 <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="[]"}
 + $\text{Code 1}$,
@@ Zeile 42: / Zeile 42: @@
-{Wie stehen die mittlere Codewortlänge $L_{\rm M}$ und die 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} \ge H$,
@@ Zeile 49: / 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="{}"}
 $\ p_{\rm A} \ = \ $ { 0.25 3% }
@@ Zeile 58: / Zeile 58: @@
-{Die in der Teilaufgabe '''(3)''' berechneten Wahrscheinlichkeiten gelten weiter. <br>Die mittlere Codewortlänge wird aber nun für eine Folge der Länge $N = 40$ ermittelt &nbsp;&#8658;&nbsp; $L_{\rm M}\hspace{0.01cm}'$. 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="[]"}
 + $L_{\rm M}\hspace{0.01cm}' < L_{\rm M}$,

@@ Zeile 4: / Zeile 4: @@
 [[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&nbsp; [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]&nbsp; 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}$.
+* Der Code führt bei gedächtnisloser Quelle zur kleinstmöglichen  mittleren Codewortlänge&nbsp; $L_{\rm M}$.
-* $L_{\rm M}$ ist aber nie kleiner als die Quellenentropie $H$.
+* $L_{\rm M}$&nbsp; ist aber nie kleiner als die Quellenentropie&nbsp; $H$.
-*Diese beiden Größen sind allein aus den $M$ Symbolwahrscheinlichkeiten berechenbar.
+*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 $M = 5$ und dem Alphabet
+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} \}.$$
+:$$\{ {\rm A},\ {\rm B},\ {\rm C},\ {\rm D},\ {\rm E} \}.$$
@@ Zeile 24: / Zeile 26: @@
 ''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 [[Applets:Huffman_Shannon_Fano|Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].
+*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul&nbsp; [[Applets:Huffman_Shannon_Fano|Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].