Aufgaben:Aufgabe 2.7Z: Huffman-Codierung für Zweiertupel einer Ternärquelle: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(9 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2458__Inf_Z_2_7.png|right|Huffman–Baum für Ternärquelle]]
+
[[Datei:P_ID2458__Inf_Z_2_7.png|right|frame|Huffman–Baum für <br>eine Ternärquelle]]
Wir betrachten den gleichen Sachverhalt wie in der [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe A2.7]]: Der Huffman&ndash;Algorithmus führt zu einem besseren Ergebnis, das heißt zu einer kleineren mittleren Codewortlänge $L_{\rm M}$, wenn man ihn nicht auf einzelne Symbole anwendet, sondern vorher $k$&ndash;Tupel bildet. Dadurch erhöht man den Symbolumfang von $M$ auf $M' = M^k$.
+
Wir betrachten den gleichen Sachverhalt wie in der&nbsp; [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe A2.7]]: &nbsp;
 +
*Der Huffman&ndash;Algorithmus führt zu einem besseren Ergebnis, das heißt zu einer kleineren mittleren Codewortlänge&nbsp; $L_{\rm M}$, wenn man ihn nicht auf einzelne Symbole anwendet, sondern vorher&nbsp; $k$&ndash;Tupel bildet.&nbsp;
 +
*Dadurch erhöht man den Symbolumfang von&nbsp; $M$&nbsp; auf $M\hspace{0.03cm}' = M^k$.
 +
 
  
 
Für die hier betrachtete Nachrichtenquelle gilt:
 
Für die hier betrachtete Nachrichtenquelle gilt:
* Symbolumfang: $M = 3$,
+
* Symbolumfang: &nbsp; $M = 3$,
* Symbolvorrat: $\{$<b>X</b>, <b>Y</b>, <b>Z</b>$\}$,
+
* Symbolvorrat: &nbsp; $\{$ $\rm X$,&nbsp; $\rm Y$,&nbsp; $\rm Z$ $\}$,
* Wahrscheinlichkeiten: $p_{\rm X} = 0.7$, $p_{\rm Y} = 0.2$, $p_{\rm Z} = 0.1$,
+
* Wahrscheinlichkeiten: &nbsp;  $p_{\rm X} = 0.7$,&nbsp; $p_{\rm Y} = 0.2$,&nbsp; $p_{\rm Z} = 0.1$,
* Entropie: $H = 1.157 \ \rm  bit/Ternärsymbol$.
+
* Entropie: &nbsp; $H = 1.157 \ \rm  bit/Ternärsymbol$.
 +
 
 +
 
 +
Die Grafik zeigt den Huffman&ndash;Baum, wenn man den Huffman&ndash;Algorithmus auf Einzelsymbole anwendet, also den Fall&nbsp; $k= 1$. <br>In der Teilaufgabe&nbsp; '''(2)'''&nbsp; sollen Sie den entsprechenden Huffman&ndash;Code angeben, wenn vorher Zweiertupel gebildet werden&nbsp; $(k=2)$.
 +
 
 +
 
 +
 
 +
 
  
  
Die Grafik zeigt den Huffman&ndash;Baum, wenn man den Huffman&ndash;Algorithmus auf Einzelsymbole anwendet, also den Fall $k= 1$. In der Teilaufgabe (2) sollen Sie den entsprechenden Huffman&ndash;Code angeben, wenn vorher Zweiertupel gebildet werden ($k=2$).
 
  
  
 
''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]].
*Insbesondere wird auf die Seite [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_k.E2.80.93Tupel|Anwendung der Huffman-Codierung auf k-Tupel]] Bezug genommen.
+
*Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax164-QINU.60.22.27.7F.E2.80.93Tupel|Anwendung der Huffman-Codierung auf&nbsp; $k$-Tupel]]&nbsp; Bezug genommen.
*Eine vergleichbare Aufgabenstellung mit binären Eingangssymbolen wird in der  [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe 2.7]] behandelt.
+
*Eine vergleichbare Aufgabenstellung mit binären Eingangssymbolen wird in der&nbsp;   [[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe 2.7]]&nbsp; behandelt.
*Bezeichnen Sie die möglichen Zweiertupel mit &nbsp; &nbsp; <b>XX</b> = <b>A</b>,&nbsp;&nbsp;<b>XY</b> = <b>B</b>,&nbsp;&nbsp;<b>XZ</b> = <b>C</b>,&nbsp;&nbsp; <b>YX</b> = <b>D</b>,&nbsp;&nbsp;<b>YY</b> = <b>E</b>,&nbsp;&nbsp;<b>YZ</b> = <b>F</b>,&nbsp;&nbsp;<b>ZX</b> = <b>G</b>,&nbsp;&nbsp;<b>ZY</b> = <b>H</b>,&nbsp;&nbsp;<b>ZZ</b> = <b>I</b> .
+
*Bezeichnen Sie die möglichen Zweiertupel mit &nbsp; &nbsp; $\rm XX = A$,&nbsp; &nbsp;$\rm XY = B$,&nbsp; &nbsp;$\rm XZ = C$,&nbsp;&nbsp; $\rm YX = D$,&nbsp; &nbsp;$\rm YY = E$,&nbsp; &nbsp;$\rm YZ = F$,&nbsp; &nbsp;$\rm ZX = G$,&nbsp; &nbsp;$\rm ZY = H$,&nbsp; &nbsp;$\rm ZZ = I$.
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
  
  
Zeile 27: Zeile 36:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wie groß ist die mittlere Codewortlänge, wenn der Huffman&ndash;Algorithmus direkt auf die ternären Quellensymbole <b>X</b>, <b>Y</b> und <b>Z</b> angewendet wird?
+
{Wie groß ist die mittlere Codewortlänge, wenn der Huffman&ndash;Algorithmus direkt auf die ternären Quellensymbole&nbsp; $\rm X$,&nbsp; $\rm Y$&nbsp; und&nbsp; $\rm Z$&nbsp; angewendet wird?  
 
|type="{}"}
 
|type="{}"}
$k= 1\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.3 3% } $\ \rm bit/Quellensymbol$
+
$\underline{k=1}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.3 3% } $\ \rm bit/Quellensymbol$
  
  
{Wie groß sind die Tupel&ndash;Wahrscheinlichkeiten? Insbesondere:
+
{Wie groß sind hier die Tupel&ndash;Wahrscheinlichkeiten? Insbesondere:
 
|type="{}"}
 
|type="{}"}
$p_{\rm A} = {\rm Pr}($'''XX'''$)\ = \ $ { 0.49 3% }
+
$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.49 3% }
$p_{\rm B} = {\rm Pr}($'''XY'''$)\ = \ $ { 0.14 3% }
+
$p_{\rm B} = \rm Pr(XY)\ = \ $ { 0.14 3% }
$p_{\rm C} = {\rm Pr}($'''XZ'''$)\ = \ $ { 0.07 3% }
+
$p_{\rm C} = \rm Pr(XZ)\ = \ $ { 0.07 3% }
  
  
 
{Wie groß ist die mittlere Codewortlänge, wenn man zuerst Zweiertupel bildet und darauf den Huffman&ndash;Algorithmus  anwendet?
 
{Wie groß ist die mittlere Codewortlänge, wenn man zuerst Zweiertupel bildet und darauf den Huffman&ndash;Algorithmus  anwendet?
 
|type="{}"}
 
|type="{}"}
$k= 2\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.165 3% } $\ \rm bit/Quellensymbol$
+
$\underline{k=2}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $ { 1.165 3% } $\ \rm bit/Quellensymbol$
  
  
{Welche der folgenden Aussagen sind zutreffend, wenn man mehr als zwei Ternärzeichen zusammenfasst ($k>2$)?
+
{Welche der folgenden Aussagen sind zutreffend, wenn man mehr als zwei Ternärzeichen zusammenfasst&nbsp; $(k>2)$?
 
|type="[]"}
 
|type="[]"}
+ $L_{\rm M}$ fällt monoton mit steigendem $k$ ab.
+
+ $L_{\rm M}$&nbsp; fällt monoton mit steigendem &nbsp;$k$&nbsp; ab.
- $L_{\rm M}$ändert sich nicht, wenn man $k$ erhöht.
+
- $L_{\rm M}$&nbsp; ändert sich nicht, wenn man &nbsp;$k$&nbsp; erhöht.
- Für $k= 3$ erhält man $L_{\rm M} = 1.05 \ \rm bit/Quellensymbol$.
+
- Für &nbsp;$k= 3$&nbsp; erhält man &nbsp;$L_{\rm M} = 1.05 \ \rm bit/Quellensymbol$.
  
  
Zeile 56: Zeile 65:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;Die mittlere Codewortlänge ergibt sich mit <i>p</i><sub>X</sub> = 0.7, <i>L</i><sub>X</sub> = 1, <i>p</i><sub>Y</sub> = 0.2, <i>L</i><sub>Y</sub> = 2, <i>p</i><sub>Z</sub> = 0.1, <i>L</i><sub>Z</sub> = 2 zu
+
'''(1)'''&nbsp; Die mittlere Codewortlänge ergibt sich mit &nbsp;$p_{\rm X} = 0.7$, &nbsp;$L_{\rm X} = 1$, &nbsp;$p_{\rm Y} = 0.2$, &nbsp;$L_{\rm Y} = 2$, &nbsp;$p_{\rm Z} = 0.1$, &nbsp;$L_{\rm Z} = 2$ zu
 
:$$L_{\rm M} = p_{\rm X} \cdot 1 + (p_{\rm Y} + p_{\rm Z}) \cdot 2 \hspace{0.15cm}\underline{= 1.3\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$
 
:$$L_{\rm M} = p_{\rm X} \cdot 1 + (p_{\rm Y} + p_{\rm Z}) \cdot 2 \hspace{0.15cm}\underline{= 1.3\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$
Dieser Wert liegt noch deutlich über der Quellenentropie <i>H</i> = 1.157 bit/Quellensymbol.
+
*Dieser Wert liegt noch deutlich über der Quellenentropie&nbsp; $H = 1.157$&nbsp; bit/Quellensymbol.
 
 
<b>2.</b>&nbsp;&nbsp;Es gibt <i>M</i><sup>&nbsp;</sup>&prime; = <i>M</i><sup>&nbsp;2</sup> = 3<sup>2</sup> = 9 Zweiertupel mit folgenden Wahrscheinlichkeiten:
 
 
 
: <i>p</i><sub>A</sub> = Pr(<b>XX</b>) <u>= 0.49</u>,&nbsp;&nbsp;&nbsp;<i>p</i><sub>B</sub> = Pr(<b>XY</b>) <u>= 0.14</u>,&nbsp;&nbsp;&nbsp; <i>p</i><sub>C</sub> = Pr(<b>XZ</b>) <u>= 0.07</u>,
 
  
: <i>p</i><sub>D</sub> = Pr(<b>YX</b>) = 0.14,&nbsp;&nbsp;&nbsp; <i>p</i><sub>E</sub> = Pr(<b>YY</b>) = 0.04,&nbsp;&nbsp;&nbsp; <i>p</i><sub>F</sub> = Pr(<b>YZ</b>) = 0.02,
 
  
: <i>p</i><sub>G</sub> = Pr(<b>YX</b>) = 0.07,&nbsp;&nbsp;&nbsp; <i>p</i><sub>H</sub> = Pr(<b>YY</b>) = 0.02,&nbsp;&nbsp;&nbsp; <i>p</i><sub>I</sub> = Pr(<b>YZ</b>) = 0.01.
 
  
<b>3.</b>&nbsp;&nbsp;Die Grafik zeigt den Huffman&ndash;Baum für die Anwendung mit <i>k</i> = 2.
+
'''(2)'''&nbsp; Es gibt&nbsp; $M\hspace{0.03cm}' = M^k = 3^2 = 9$&nbsp; Zweiertupel mit folgenden Wahrscheinlichkeiten:
[[Datei:P_ID2459__Inf_Z_2_7c.png|Huffman–Baum für Ternärquelle und Zweiertupel]]
 
Damit erhält man
 
  
:* für die einzelnen Zweiertupels folgende Binärcodierungen: <br>
+
[[Datei:P_ID2459__Inf_Z_2_7c.png|right|frame|Huffman–Baum für Ternärquelle und Zweiertupel]]
: <b>XX</b> = <b>A</b> &#8594; <b>0</b>,&nbsp;&nbsp;&nbsp;<b>XY</b> = <b>B</b> &#8594; <b>111</b>,&nbsp;&nbsp;&nbsp;<b>XZ</b> = <b>C</b> &#8594; <b>1011</b>,&nbsp;&nbsp;&nbsp; <b>YX</b> = <b>D</b> &#8594; <b>110</b>,&nbsp;&nbsp;&nbsp;<b>YY</b> = <b>E</b> &#8594; <b>1000</b>, <br>
+
:$$p_{\rm A} = \rm Pr(XX) = 0.7 \cdot 0.7\hspace{0.15cm}\underline{= 0.49},$$
: <b>YZ</b> = <b>F</b> &#8594; <b>10010</b>,&nbsp;&nbsp;&nbsp; <b>ZX</b> = <b>G</b> &#8594; <b>1010</b>,&nbsp;&nbsp;&nbsp;<b>ZY</b> = <b>H</b> &#8594; <b>100111</b>,&nbsp;&nbsp;&nbsp;<b>ZZ</b> = <b>I</b> &#8594; <b>100110</b> .
+
:$$p_{\rm B} = \rm Pr(XY) = 0.7 \cdot 0.2\hspace{0.15cm}\underline{= 0.14},$$
 +
:$$p_{\rm C} = \rm Pr(XZ) = 0.7 \cdot 0.1\hspace{0.15cm}\underline{= 0.07},$$
 +
:$$p_{\rm D} = \rm Pr(YX) = 0.2 \cdot 0.7 = 0.14,$$
 +
:$$p_{\rm E} = \rm Pr(YY) = 0.2 \cdot 0.2 = 0.04,$$
 +
:$$p_{\rm F} = \rm Pr(YZ) = 0.2 \cdot 0.1 = 0.02,$$
 +
:$$p_{\rm G} = \rm Pr(ZX) = 0.1 \cdot 0.7 = 0.07,$$
 +
:$$p_{\rm H} = \rm Pr(ZY) = 0.1 \cdot 0.2 = 0.02,$$
 +
:$$p_{\rm I} = \rm Pr(ZZ) = 0.1 \cdot 0.1 = 0.01.$$
 +
<br clear=all>
  
:* für die mittlere Codewortlänge:
+
'''(3)'''&nbsp; Die Grafik zeigt den Huffman&ndash;Baum für die Anwendung mit $k = 2$.&nbsp; Damit erhält man
:$$L_{\rm M}' \hspace{0.2cm} =  \hspace{0.2cm} 0.49 \cdot 1 + (0.14 + 0.14) \cdot 3 + (0.07 + 0.04 + 0.07) \cdot 4 + \\
+
* für die einzelnen Zweiertupels folgende Binärcodierungen: <br>
\hspace{0.2cm} + \hspace{0.2cm}0.02 \cdot 5 + (0.02 + 0.01) \cdot 6 = 2.33\,\,{\rm bit/Zweiertupel}$$
+
: &nbsp; &nbsp;  $\rm XX = A$ &nbsp; &#8594; &nbsp; '''0''', &nbsp; &nbsp;  $\rm XY = B$ &nbsp; &#8594; &nbsp; '''111''', &nbsp; &nbsp; $\rm XZ = C$ &nbsp; &#8594; &nbsp; <b>1011</b>,
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}'}/{2}\hspace{0.15cm}\underline{ = 1.165\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
+
: &nbsp; &nbsp; $\rm YX = D$ &nbsp; &#8594; &nbsp; <b>110</b>, &nbsp; &nbsp;  $\rm YY = E$ &nbsp; &#8594; &nbsp; <b>1000</b>, &nbsp; &nbsp;  $\rm YZ = F$ &nbsp; &#8594; &nbsp; <b>10010</b>,
 +
: &nbsp; &nbsp;  $\rm ZX = G$ &nbsp; &#8594; &nbsp; <b>1010</b>, &nbsp; &nbsp;  $\rm ZY = H$ &nbsp; &#8594; &nbsp; <b>100111</b>, &nbsp; &nbsp; $\rm ZZ =I$ &nbsp; &#8594; &nbsp; <b>100110</b>; 
  
<b>4.</b>&nbsp;&nbsp;Richtig ist <u>Aussage 1</u>, auch wenn <i>L</i><sub>M</sub> mit wachsendem <i>k</i> nur sehr langsam abfällt.
+
* für die mittlere Codewortlänge:
 +
:$$L_{\rm M}\hspace{0.01cm}' =0.49 \cdot 1 + (0.14 + 0.14) \cdot 3 + (0.07 + 0.04 + 0.07) \cdot 4 + 0.02 \cdot 5 + (0.02 + 0.01) \cdot 6 = 2.33\,\,{\rm bit/Zweiertupel}$$
 +
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{  = 1.165\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
  
:* Die letzte Aussage ist falsch, da <i>L</i><sub>M</sub> auch für <i>k</i> &#8594; &#8734; nicht kleiner sein kann als <i>H</i> = 1.157 bit/Quellensymbol.
 
  
:* Aber auch die zweite Aussage ist falsch: Da mit <i>k</i> = 2 weiterhin <i>L</i><sub>M</sub> > <i>H</i> gilt, führt <i>k</i> = 3 zu einer Verbesserung.
+
'''(4)'''&nbsp; Richtig ist die <u>Aussage 1</u>, auch wenn&nbsp; $L_{\rm M}$&nbsp; mit wachsendem&nbsp; $k$&nbsp; nur sehr langsam abfällt.
 +
* Die letzte Aussage ist falsch, da&nbsp; $L_{\rm M}$&nbsp; auch für&nbsp; $k &#8594; &#8734;$&nbsp; nicht kleiner sein kann als&nbsp; $H = 1.157$&nbsp; bit/Quellensymbol.
 +
* Aber auch die zweite Aussage ist nicht unbedingt richtig: &nbsp; Da mit&nbsp; $k = 2$&nbsp; weiterhin&nbsp; $L_{\rm M} > H$&nbsp; gilt, kann&nbsp; $k = 3$&nbsp; zu einer weiteren Verbesserung führen.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 25. Januar 2020, 18:26 Uhr

Huffman–Baum für
eine Ternärquelle

Wir betrachten den gleichen Sachverhalt wie in der  Aufgabe A2.7:  

  • Der Huffman–Algorithmus führt zu einem besseren Ergebnis, das heißt zu einer kleineren mittleren Codewortlänge  $L_{\rm M}$, wenn man ihn nicht auf einzelne Symbole anwendet, sondern vorher  $k$–Tupel bildet. 
  • Dadurch erhöht man den Symbolumfang von  $M$  auf $M\hspace{0.03cm}' = M^k$.


Für die hier betrachtete Nachrichtenquelle gilt:

  • Symbolumfang:   $M = 3$,
  • Symbolvorrat:   $\{$ $\rm X$,  $\rm Y$,  $\rm Z$ $\}$,
  • Wahrscheinlichkeiten:   $p_{\rm X} = 0.7$,  $p_{\rm Y} = 0.2$,  $p_{\rm Z} = 0.1$,
  • Entropie:   $H = 1.157 \ \rm bit/Ternärsymbol$.


Die Grafik zeigt den Huffman–Baum, wenn man den Huffman–Algorithmus auf Einzelsymbole anwendet, also den Fall  $k= 1$.
In der Teilaufgabe  (2)  sollen Sie den entsprechenden Huffman–Code angeben, wenn vorher Zweiertupel gebildet werden  $(k=2)$.





Hinweise:

  • Die Aufgabe gehört zum Kapitel  Entropiecodierung nach Huffman.
  • Insbesondere wird auf die Seite  Anwendung der Huffman-Codierung auf  $k$-Tupel  Bezug genommen.
  • Eine vergleichbare Aufgabenstellung mit binären Eingangssymbolen wird in der  Aufgabe 2.7  behandelt.
  • Bezeichnen Sie die möglichen Zweiertupel mit     $\rm XX = A$,   $\rm XY = B$,   $\rm XZ = C$,   $\rm YX = D$,   $\rm YY = E$,   $\rm YZ = F$,   $\rm ZX = G$,   $\rm ZY = H$,   $\rm ZZ = I$.


Fragebogen

1

Wie groß ist die mittlere Codewortlänge, wenn der Huffman–Algorithmus direkt auf die ternären Quellensymbole  $\rm X$,  $\rm Y$  und  $\rm Z$  angewendet wird?

$\underline{k=1}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

2

Wie groß sind hier die Tupel–Wahrscheinlichkeiten? Insbesondere:

$p_{\rm A} = \rm Pr(XX)\ = \ $

$p_{\rm B} = \rm Pr(XY)\ = \ $

$p_{\rm C} = \rm Pr(XZ)\ = \ $

3

Wie groß ist die mittlere Codewortlänge, wenn man zuerst Zweiertupel bildet und darauf den Huffman–Algorithmus anwendet?

$\underline{k=2}\text{:} \hspace{0.25cm}L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

4

Welche der folgenden Aussagen sind zutreffend, wenn man mehr als zwei Ternärzeichen zusammenfasst  $(k>2)$?

$L_{\rm M}$  fällt monoton mit steigendem  $k$  ab.
$L_{\rm M}$  ändert sich nicht, wenn man  $k$  erhöht.
Für  $k= 3$  erhält man  $L_{\rm M} = 1.05 \ \rm bit/Quellensymbol$.


Musterlösung

(1)  Die mittlere Codewortlänge ergibt sich mit  $p_{\rm X} = 0.7$,  $L_{\rm X} = 1$,  $p_{\rm Y} = 0.2$,  $L_{\rm Y} = 2$,  $p_{\rm Z} = 0.1$,  $L_{\rm Z} = 2$ zu

$$L_{\rm M} = p_{\rm X} \cdot 1 + (p_{\rm Y} + p_{\rm Z}) \cdot 2 \hspace{0.15cm}\underline{= 1.3\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$
  • Dieser Wert liegt noch deutlich über der Quellenentropie  $H = 1.157$  bit/Quellensymbol.


(2)  Es gibt  $M\hspace{0.03cm}' = M^k = 3^2 = 9$  Zweiertupel mit folgenden Wahrscheinlichkeiten:

Huffman–Baum für Ternärquelle und Zweiertupel
$$p_{\rm A} = \rm Pr(XX) = 0.7 \cdot 0.7\hspace{0.15cm}\underline{= 0.49},$$
$$p_{\rm B} = \rm Pr(XY) = 0.7 \cdot 0.2\hspace{0.15cm}\underline{= 0.14},$$
$$p_{\rm C} = \rm Pr(XZ) = 0.7 \cdot 0.1\hspace{0.15cm}\underline{= 0.07},$$
$$p_{\rm D} = \rm Pr(YX) = 0.2 \cdot 0.7 = 0.14,$$
$$p_{\rm E} = \rm Pr(YY) = 0.2 \cdot 0.2 = 0.04,$$
$$p_{\rm F} = \rm Pr(YZ) = 0.2 \cdot 0.1 = 0.02,$$
$$p_{\rm G} = \rm Pr(ZX) = 0.1 \cdot 0.7 = 0.07,$$
$$p_{\rm H} = \rm Pr(ZY) = 0.1 \cdot 0.2 = 0.02,$$
$$p_{\rm I} = \rm Pr(ZZ) = 0.1 \cdot 0.1 = 0.01.$$


(3)  Die Grafik zeigt den Huffman–Baum für die Anwendung mit $k = 2$.  Damit erhält man

  • für die einzelnen Zweiertupels folgende Binärcodierungen:
    $\rm XX = A$   →   0,     $\rm XY = B$   →   111,     $\rm XZ = C$   →   1011,
    $\rm YX = D$   →   110,     $\rm YY = E$   →   1000,     $\rm YZ = F$   →   10010,
    $\rm ZX = G$   →   1010,     $\rm ZY = H$   →   100111,     $\rm ZZ =I$   →   100110;
  • für die mittlere Codewortlänge:
$$L_{\rm M}\hspace{0.01cm}' =0.49 \cdot 1 + (0.14 + 0.14) \cdot 3 + (0.07 + 0.04 + 0.07) \cdot 4 + 0.02 \cdot 5 + (0.02 + 0.01) \cdot 6 = 2.33\,\,{\rm bit/Zweiertupel}$$
$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 1.165\,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$


(4)  Richtig ist die Aussage 1, auch wenn  $L_{\rm M}$  mit wachsendem  $k$  nur sehr langsam abfällt.

  • Die letzte Aussage ist falsch, da  $L_{\rm M}$  auch für  $k → ∞$  nicht kleiner sein kann als  $H = 1.157$  bit/Quellensymbol.
  • Aber auch die zweite Aussage ist nicht unbedingt richtig:   Da mit  $k = 2$  weiterhin  $L_{\rm M} > H$  gilt, kann  $k = 3$  zu einer weiteren Verbesserung führen.