Aufgaben:Aufgabe 2.8: Huffman-Anwendung bei einer Markovquelle: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(21 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2460__Inf_A_2_8.png|right|]]
+
[[Datei:P_ID2460__Inf_A_2_8.png|right|frame|Binäre symmetrische Markovquelle]]
Wir betrachten hier die binäre symmetrische Markovquelle entsprechend nebenstehender Grafik, die durch den einzigen Parameter
+
Wir betrachten die binäre symmetrische Markovquelle entsprechend der Grafik, die durch den einzigen Parameter
 
:$$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =  
 
:$$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =  
 
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y})$$
 
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y})$$
vollständig beschrieben wird. Die angegebenen Quellensymbolfolgen gelten für <i>q</i> = 0.2 bzw. <i>q</i>&nbsp;=&nbsp;0.8. In der Teilaufgabe (a) ist zu klären, welche Symbolfolge mit <i>q</i> = 0.2 und welche mit <i>q</i> = 0.8 generiert wurde.
+
vollständig beschrieben wird.  
 +
*Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten &nbsp;$q = 0.2$&nbsp; bzw. &nbsp;$q = 0.8$.  
 +
*In der Teilaufgabe&nbsp; '''(1)'''&nbsp; ist zu klären, welche Symbolfolge &ndash; die rote oder die blaue &ndash; mit &nbsp;$q = 0.2$&nbsp; und welche mit &nbsp;$q = 0.8$&nbsp; generiert wurde.
  
Die Eigenschaften von Markovquellen werden im Kapitel 1.2 ausführlich beschrieben. Aufgrund der hier vorausgesetzten Symmetrie bezüglich der binären Symbole <b>X</b> und <b>Y</b> ergeben sich einige gravierende Vereinfachungen, wie in Aufgabe Z1.5 hergeleitet wird:
 
  
:* Die Symbole <b>X</b> und <b>Y</b> sind gleichwahrscheinlich, das heißt. es ist <i>p</i><sub>X</sub> = <i>p</i><sub>Y</sub> = 0.5. Damit lautet die erste Entropienäherung:
+
Die Eigenschaften von Markovquellen werden im Kapitel&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]]&nbsp; ausführlich beschrieben.&nbsp; Aufgrund der hier vorausgesetzten Symmetrie bezüglich der Binärsymbole &nbsp;$\rm X$&nbsp; und &nbsp;$\rm Y$&nbsp; ergeben sich einige gravierende Vereinfachungen, wie in der&nbsp; [[Aufgaben:1.5Z_Symmetrische_Markovquelle|Aufgabe  1.5Z]]&nbsp; hergeleitet wird:
:$$H_1 = 1\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $$
+
* Die Symbole &nbsp;$\rm X$&nbsp; und &nbsp;$\rm Y$&nbsp; sind gleichwahrscheinlich, das heißt, es gilt&nbsp; $p_{\rm X} = p_{\rm Y= 0.5$.&nbsp; <br>Damit lautet die erste Entropienäherung: &nbsp; $H_1 = 1\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $
 +
* Die Entropie der Markovquelle ergibt sich sowohl für &nbsp;$q = 0.2$&nbsp; als auch für &nbsp;$q = 0.8$&nbsp; zu
 +
:$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q}
 +
= 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
 +
* Bei Markovquellen sind alle Entropienäherungen&nbsp; $H_k$&nbsp; mit Ordnung&nbsp; $k \ge 2$&nbsp; durch&nbsp; $H_1$&nbsp;  und&nbsp; $H = H_{k \to \infty}$&nbsp; bestimmt:
 +
:$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$
 +
*Die folgenden Zahlenwerte gelten wieder für &nbsp;$q = 0.2$&nbsp; und &nbsp;$q = 0.8$&nbsp; gleichermaßen:
 +
:$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
 +
:$$H_3 = {1}/{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
  
:* Die Entropie der Markovquelle ergibt sich zu
+
In dieser Aufgabe soll der Huffman&ndash;Algorithmus auf&nbsp; $k$&ndash;Tupel angewandt werden, wobei wir uns auf&nbsp; $k = 2$&nbsp; und&nbsp; $k = 3$&nbsp; beschränken.
:$$H = q \cdot {\rm ld}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm ld}\hspace{0.15cm}\frac{1}{1-q}
 
= 0.722\,\,{\rm bit/Quellensymbol}
 
\hspace{0.05cm}.$$
 
: Der Zahlenwert gilt nur für <i>q</i> = 0.2 sowie für <i>q</i> = 0.8.
 
  
:* Bei Markovquellen sind alle Entropienäherungen höherer Ordnung durch <i>H</i><sub>1</sub> und <i>H</i> bestimmt. Die folgenden Zahlenwerte gelten wieder für <i>q</i> = 0.2 und <i>q</i> = 0.8 gleichermaßen:
 
:$$H_2 \hspace{0.2cm} =  \hspace{0.2cm} \frac{1}{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/Quellensymbol}\hspace{0.05cm},\\
 
H_3 \hspace{0.2cm} =  \hspace{0.2cm} \frac{1}{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
 
  
Wie auf der letzten Theorieseite dieses Kapitels 2.3 soll hier der Huffman&ndash;Algorithmus auf <i>k</i>&ndash;Tupel angewandt werden, wobei wir uns auf <i>k</i> = 2 und <i>k</i> = 3 beschränken.
 
  
<b>Hinweis:</b> Die Aufgabe gehört zum Themengebiet von Kapitel 2.3. Nützliche Informationen finden Sie auch in Aufgabe A2.7 und Aufgabe Z2.7. Für die Huffman&ndash;Codierung können Sie das folgende Interaktionsmodul benutzen:
 
  
Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung
+
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum  Kapitel &nbsp;[[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
 +
*Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax169-QINU.60.22.27.7F.E2.80.93Tupel|Anwendung der Huffman-Codierung auf k-Tupel]]&nbsp;  Bezug genommen.
 +
*Nützliche Informationen finden Sie auch in den Angabenblättern zu    &nbsp;[[Aufgaben:2.7_Huffman-Anwendung_für_binäre_Zweiertupel|Aufgabe 2.7]]&nbsp; und &nbsp;[[Aufgaben:2.7Z_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle|Aufgabe 2.7Z]].
 +
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:&nbsp; [[Applets:Huffman_Shannon_Fano|Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&ndash;Version]].
 +
 
  
  
Zeile 34: Zeile 43:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche der vorne angegebenen Beispielfolgen gilt für <i>q</i> = 0.8?
+
{Welche der vorne angegebenen Beispielfolgen gilt für&nbsp; $q = 0.8$?
|type="[]"}
+
|type="()"}
- Quellensymbolfolge 1,
+
- die rote Quellensymbolfolge&nbsp; '''1''',
+ Quellensymbolfolge 2,
+
+ die blaue Quellensymbolfolge&nbsp; '''2'''.
  
  
Zeile 43: Zeile 52:
 
|type="[]"}
 
|type="[]"}
 
- Auch die direkte Anwendung von Huffman ist hier sinnvoll.
 
- Auch die direkte Anwendung von Huffman ist hier sinnvoll.
+ Huffman macht bei Bildung von Zweiertupeln (<i>k</i> = 2) Sinn.
+
+ Huffman macht bei Bildung von Zweiertupeln&nbsp; $(k = 2)$&nbsp; Sinn.
+ Huffman macht bei Bildung von Dreiertupeln (<i>k</i> = 3) Sinn.
+
+ Huffman macht bei Bildung von Dreiertupeln&nbsp; $(k = 3)$&nbsp; Sinn.
  
  
{Wie lauten die Wahrscheinlichkeiten der Zweiertupel (<i>k</i> = 2) für <i>q</i> = 0.8?
+
{Wie lauten die Wahrscheinlichkeiten der <u>Zweiertupel</u>&nbsp; $(k = 2)$&nbsp; für &nbsp;$\underline{q = 0.8}$?
 
|type="{}"}
 
|type="{}"}
$q = 0.8; k = 2:\ p_A = Pr(XX)$ = { 0.4 3% }
+
$p_{\rm A} = \rm Pr(XX)\ = \ $ { 0.4 3% }
$p_B = Pr(XY)$ = { 0.1 3% }
+
$p_{\rm B} = \rm Pr(XY)\ = \ $ { 0.1 3% }
$p_C = Pr(YX)$ = { 0.1 3% }
+
$p_{\rm C} = \rm Pr(YX)\ = \ $ { 0.1 3% }
$p_D = Pr(YY)$ = { 0.4 3% }
+
$p_{\rm D} = \rm Pr(YY)\ = \ $ { 0.4 3% }
  
  
{Ermitteln Sie mit dem angegebenen Flash&ndash;Modul den Huffman&ndash;Code für <i>k</i> = 2. Wie groß ist in diesem Fall die mittlere Codewortlänge?
+
{Ermitteln Sie den Huffman&ndash;Code für&nbsp; $\underline{k = 2}$.&nbsp; Wie groß ist in diesem Fall die mittlere Codewortlänge?
 
|type="{}"}
 
|type="{}"}
$L_M$ = { 0.9 3% } bit/Quellensymbol
+
$L_{\rm M} \ = \ $ { 0.9 3% } $\ \rm bit/Quellensymbol$
  
  
{Welche Schranke ergibt sich für die mittlere Codewortlänge, wenn Zweiertupel gebildet werden (<i>k</i> = 2)? Interpretation.
+
{Welche Schranke ergibt sich für die mittlere Codewortlänge, wenn <u>Zweiertupel</u> gebildet werden&nbsp; $(k = 2)$? Interpretation.
|type="[]"}
+
|type="()"}
- <i>L</i><sub>M</sub> &#8805; <i>H</i><sub>1</sub> = 1 bit/Quellensymbol,
+
- $L_{\rm M} \ge H_1 =  1.000$&nbsp; bit/Quellensymbol,
+ <i>L</i><sub>M</sub> &#8805; <i>H</i><sub>2</sub> &asymp; 0.861 bit/Quellensymbol,
+
+ $L_{\rm M} \ge H_2 \approx  0.861$&nbsp; bit/Quellensymbol,
- <i>L</i><sub>M</sub> &#8805; <i>H</i><sub>3</sub> &asymp; 0.815 bit/Quellensymbol,
+
- $L_{\rm M} \ge H_3 \approx  0.815$&nbsp; bit/Quellensymbol,  
- <i>L</i><sub>M</sub> &#8805; <i>H</i> &asymp; 0.722 bit/Quellensymbol,
+
- $L_{\rm M} \ge H_{k \to \infty} \approx  0.722$&nbsp; bit/Quellensymbol,  
- <i>L</i><sub>M</sub> &#8805; 0.5 bit/Quellensymbol.
+
- $L_{\rm M} \ge 0.5$&nbsp; bit/Quellensymbol.
  
  
{Berechnen Sie die Wahrscheinlichkeiten für <i>k</i> = 3.
+
{Berechnen Sie die Wahrscheinlichkeiten der <u>Dreiertupel</u>&nbsp; $(k = 3)$&nbsp; für &nbsp;$\underline{q = 0.8}$?
 
|type="{}"}
 
|type="{}"}
$q = 0.8; k = 3:\ p_A = Pr(XXX)$ = { 0.32 3% }
+
$p_{\rm A} = \rm Pr(XXX)\ = \ $ { 0.32 3% }
$p_B = Pr(XXY)$ = { 0.08 3% }
+
$p_{\rm B} = \rm Pr(XXY)\ = \ $ { 0.08 3% }
$p_C = Pr(XYX)$ = { 0.02 3% }
+
$p_{\rm C} = \rm Pr(XYX)\ = \ $ { 0.02 3% }
$p_D = Pr(XYY)$ = { 0.08 3% }
+
$p_{\rm D} = \rm Pr(XYY)\ = \ $ { 0.08 3% }
$p_E = Pr(YXX)$ = { 0.08 3% }
+
$p_{\rm E} = \rm Pr(YXX)\ = \ $ { 0.08 3% }
$p_F = Pr(YXY)$ = { 0.02 3% }
+
$p_{\rm F} = \rm Pr(YXY)\ = \ $ { 0.02 3% }
$p_G = Pr(YYX)$ = { 0.08 3% }
+
$p_{\rm G} = \rm Pr(YYX)\ = \ $ { 0.08 3% }
$p_H = Pr(YYY)$ = { 0.32 3% }
+
$p_{\rm H} = \rm Pr(YYY)\ = \ $ { 0.32 3% }
  
  
{Ermitteln Sie mit dem genannten Flash&ndash;Modul den Huffman&ndash;Code für <i>k</i> = 3. Wie groß ist in diesem Fall die mittlere Codewortlänge?
+
{Ermitteln Sie den Huffman&ndash;Code für $\underline{k = 3}$.&nbsp; Wie groß ist in diesem Fall die mittlere Codewortlänge?
 
|type="{}"}
 
|type="{}"}
$L_M$ = { 0.84 3% } bit/Quellensymbol
+
$L_{\rm M} \ = \ $ { 0.84 3% } $\ \rm bit/Quellensymbol$
  
  
Zeile 91: Zeile 100:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;Bei der Quellensymbolfolge 2 erkennt man sehr viel weniger Symbolwechsel als in der roten Folge. Die blaue Symbolfolge 2 wurde mit dem Parameter
+
'''(1)'''&nbsp; Richtig ist der  <u>Lösungsvorschlag 2</u>:
:$$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =  
+
*Bei der blauen Quellensymbolfolge&nbsp; '''2'''&nbsp; erkennt man sehr viel weniger Symbolwechsel als in der roten Folge.  
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.8$$
+
*Die Symbolfolge&nbsp; '''2'''&nbsp; wurde mit dem Parameter&nbsp; $q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) =  
erzeugt und die rote Symbolfolge 1 mit <i>q</i> = 0.2 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>.
+
{\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.8$&nbsp; erzeugt und die rote Symbolfolge&nbsp; '''1'''&nbsp; mit&nbsp; $q = 0.2$.
 +
 +
 
 +
 
 +
'''(2)'''&nbsp; Richtig sind die <u>Antworten 2 und 3</u>.:
 +
*Da hier die Quellensymbole&nbsp; $\rm X$&nbsp; und&nbsp; $\rm Y$&nbsp; als gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.
 +
*Dagegen kann man die inneren statistischen Bindungen  der Markovquelle zur Datenkomprimierung nutzen, wenn man&nbsp; $k$&ndash;Tupel bildet&nbsp; $(k &#8805; 2)$.
 +
*Je größer&nbsp; $k$&nbsp; ist, desto mehr nähert sich die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; der Entropie&nbsp; $H$.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Die Symbolwahrscheinlichkeiten sind&nbsp; $p_{\rm X} = p_{\rm Y}  = 0.5$.&nbsp; Damit erhält man für die Zweiertupel:
 +
:$$p_{\rm A} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{  = 0.4}  \hspace{0.05cm},$$
 +
:$$p_{\rm B} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{  = 0.1}  \hspace{0.05cm},$$
 +
:$$p_{\rm C} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YX}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{  = 0.1}  \hspace{0.05cm},$$
 +
:$$p_{\rm D} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YY}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot q = 0.5 \cdot 0.8\hspace{0.15cm}\underline{  = 0.4}  \hspace{0.05cm}.$$
 +
 
 +
 
 +
[[Datei:P_ID2462__Inf_A_2_8d.png|right|frame|Zur Huffman–Codierung für $k = 2$]]
 +
'''(4)'''&nbsp; Nebenstehender Bildschirmabzug des (früheren) SWF&ndash;Programms&nbsp; [[Applets:Huffman_Shannon_Fano|Shannon&ndash;Fano&ndash;&nbsp; und Huffman&ndash;Codierung]]&nbsp; zeigt die Konstruktion des Huffman&ndash;Codes für&nbsp; $k = 2$&nbsp; mit den soeben berechneten Wahrscheinlichkeiten.
 +
*Damit gilt für die mittlere Codewortlänge:
 +
:$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$
 +
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{  = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
 +
 
  
<b>2.</b>&nbsp;&nbsp;Da hier die Quellensymbole <b>X</b> und <b>Y</b> gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn. Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man <i>k</i>&ndash;Tupel bildet (<i>k</i> &#8805; 2). Richtig sind demnach die <u>Antworten 2 und 3</u>. Je größer <i>k</i> ist, desto mehr nähert sich die Codewortlänge <i>L</i><sub>M</sub> der Entropie <i>H</i>.
+
'''(5)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Nach dem Quellencodierungstheorem gilt&nbsp; $L_{\rm M} &#8805; H$.  
 +
*Wendet man aber Huffman&ndash;Codierung an und lässt dabei Bindungen zwischen nicht benachbarten Symbolen außer Betracht&nbsp; $(k = 2)$,&nbsp; so gilt als unterste Grenze der Codewortlänge nicht&nbsp; $H = 0.722$, sondern&nbsp; $H_2 = 0.861$&nbsp; (auf den Zusatz bit/Quellensymbol wird für den Rest der Aufgabe verzichtet).
 +
*Das Ergebnis der Teilaufgabe&nbsp; '''(4)'''&nbsp; war&nbsp; $L_{\rm M} = 0.9.$
 +
*Würde eine unsymmetrische Markovkette vorliegen und zwar derart, dass sich für die Wahrscheinlichkeiten&nbsp; $p_{\rm A}$, ... , $p_{\rm D}$&nbsp; die Werte&nbsp; $50\%$,&nbsp; $25\%$&nbsp; und zweimal&nbsp; $12.5\%$&nbsp; ergeben würden,&nbsp; so käme man auf die mittlere Codewortlänge&nbsp; $L_{\rm M}  = 0.875$.
 +
*Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß aber auch der Aufgabensteller (G. Söder) nicht.
 +
*Auch nicht, wie sich der Wert&nbsp; $0.875$&nbsp; auf&nbsp; $0.861$&nbsp; senken ließe. Der Huffman&ndash;Algorithmus ist hierfür jedenfalls ungeeignet.
  
<b>3.</b>&nbsp;&nbsp;Die Symbolwahrscheinlichkeiten <i>p</i><sub>X</sub> und <i>p</i><sub>Y</sub> sind jeweils 0.5. Damit erhält man für die Zweiertupel:
 
:$$p_{\rm A} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{  = 0.4}  \hspace{0.05cm},\\
 
p_{\rm B} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{  = 0.1}  \hspace{0.05cm},\\
 
p_{\rm C} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YX}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{  = 0.1}  \hspace{0.05cm},\\
 
p_{\rm D} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YY}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot q = 0.5 \cdot 0.8\hspace{0.15cm}\underline{  = 0.4}  \hspace{0.05cm}.$$
 
[[Datei:P_ID2462__Inf_A_2_8d.png|right|]]
 
  
<b>4.</b>&nbsp;&nbsp;Nebenstehender Bildschirmabzug des Programms Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung zeigt die Konstruktion des Huffman&ndash;Codes für <i>k</i> = 2 mit den soeben berechneten Wahrscheinlichkeiten. Damit gilt für die mittlere Codewortlänge:
+
'''(6)'''&nbsp; Mit&nbsp; $q = 0.8$&nbsp; und&nbsp; $1 - q = 0.2$&nbsp; erhält man:
:$$L_{\rm M}' \hspace{0.2cm} =  \hspace{0.2cm} 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = \\  
+
:$$p_{\rm A} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX})  = 0.5 \cdot q^2 \hspace{0.15cm}\underline{  = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},$$
\hspace{0.2cm} =  1.8\,\,{\rm bit/Zweiertupel}$$
+
:$$p_{\rm B} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{  = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},$$
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = \frac{L_{\rm M}'}{2}\hspace{0.15cm}\underline{  = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
+
:$$p_{\rm C} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYX}) = 0.5 \cdot (1-q)^2\hspace{0.15cm}\underline{  = 0.02} = p_{\rm F}= {\rm Pr}(\boldsymbol{\rm YXY}) \hspace{0.05cm},$$
 +
:$$p_{\rm D} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYY}) = 0.5 \cdot (1-q) \cdot q \hspace{0.15cm}\underline{  = 0.08} = p_{\rm E}  = {\rm Pr}(\boldsymbol{\rm YXX})\hspace{0.05cm}.$$
  
<br><br><b>5.</b>&nbsp;&nbsp;Nach dem Quellencodierungstheorem gilt <i>L</i><sub>M</sub> &#8805; <i>H</i>. Wendet man aber Huffman&ndash;Codierung an und lässt dabei Bindungen zwischen nicht benachbarten Symbolen außer Betracht (<i>k</i> = 2), so gilt als unterste Grenze der Codewortlänge nicht <i>H</i> = 0.722, sondern <i>H</i><sub>2</sub> = 0.861 (auf den Zusatz bit/Quellensymbol wird für den Rest der Aufgabe verzichtet) &nbsp;&#8658;&nbsp;<u>Lösungsvorschlag 2</u>.
 
  
Das Ergebnis der Teilaufgabe 4) war <i>L</i><sub>M</sub> = 0.9. Würde eine unsymmetrische Markovkette vorliegen und zwar derart, dass sich für die Wahrscheinlichkeiten <i>p</i><sub>A</sub>, ... , <i>p</i><sub>D</Sub> die Werte 50%, 25% und zweimal 12.5% ergeben würden, so käme man auf die mittlere Codewortlänge <i>L</i><sub>M</sub> = 0.875. Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß ich (G. Söder) nicht. Auch nicht, wie sich der Wert 0.875 auf 0.861 senken ließe. Der Huffman&ndash;Algorithmus ist hierfür jedenfalls ungeeignet.
+
[[Datei:P_ID2463__Inf_A_2_8g.png|right|frame|Zur Huffman–Codierung für $k = 3$]]
 +
'''(7)'''&nbsp; Der Bildschirmabzug des des (früheren) SWF&ndash;Programms&nbsp; [[Applets:Huffman_Shannon_Fano|Shannon&ndash;Fano&ndash;&nbsp; und Huffman&ndash;Codierung]]&nbsp; verdeutlicht die Konstellation des Huffman&ndash;Codes für&nbsp; $k = 3$.&nbsp;
  
<b>6.</b>&nbsp;&nbsp;Mit <i>q</i> = 0.8 und 1 &ndash; <i>q</i> = 0.2 erhält man:
+
Damit erhält man für die mittlere Codewortlänge:
:$$p_{\rm A} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX})  = 0.5 \cdot q^2 \hspace{0.15cm}\underline{  = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},\\
+
:$$L_{\rm M}\hspace{0.01cm}' =  0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 2.52\,\,{\rm bit/Dreiertupel}$$
p_{\rm B} \hspace{0.2cm} \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{  = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},\\
+
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{  = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
p_{\rm C} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYX}) = 0.5 \cdot (1-q)^2\hspace{0.15cm}\underline{  = 0.02} = p_{\rm F}= {\rm Pr}(\boldsymbol{\rm YXY}) \hspace{0.05cm},\\
 
p_{\rm D} \hspace{0.2cm} =  \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYY}) = 0.5 \cdot (1-q) \cdot q \hspace{0.15cm}\underline{  = 0.08} = p_{\rm E}  = {\rm Pr}(\boldsymbol{\rm YXX})\hspace{0.05cm}.$$
 
  
<b>7.</b>&nbsp;&nbsp;Der Bildschirmabzug des Flash&ndash;Moduls verdeutlicht die Konstellation des Huffman&ndash;Codes für <i>k</i> = 3. Damit erhält man für die mittlere Codewortlänge:
+
*Man erkennt die Verbesserung gegenüber der Teilaufgabe&nbsp; '''(4)'''.
:$$L_{\rm M}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 =  2.52\,\,{\rm bit/Dreiertupel}$$
+
*Die für&nbsp; $k = 2$&nbsp; gültige Schranke&nbsp; $H_2 = 0.861$&nbsp; wird nun von der mittleren Codewortlänge&nbsp; $L_{\rm M}$&nbsp; unterschritten.  
:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}'}/{3}\hspace{0.15cm}\underline{  = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
+
*Die neue Schranke für&nbsp; $k = 3$&nbsp; ist&nbsp; $H_3 = 0.815$.  
[[Datei:P_ID2463__Inf_A_2_8g.png|center|]]
+
*Um die Quellenentropie&nbsp; $H = 0.722$&nbsp; zu erreichen&nbsp; (besser gesagt:&nbsp; diesem Endwert bis auf ein&nbsp; $&epsilon;$&nbsp; nahe zu kommen), müsste man allerdings unendlich lange Tupel bilden&nbsp; $(k &#8594; &#8734;)$.
Man erkennt die Verbesserung gegenüber (4). Die für <i>k</i> = 2 gültige informationstheoretische Schranke <i>H</i><sub>2</sub> = 0.861 wird nun unterschritten (<i>L</i><sub>M</sub>). Die neue Schranke für <i>k</i> = 3 ist  <i>H</i><sub>3</sub> = 0.815. Um die Quellenentropie <i>H</i>&nbsp;=&nbsp;0.722 zu erreichen (besser gesagt: diesem Endwert bis auf ein &epsilon; näher zu kommen), müsste man allerdings unendlich lange Tupel bilden (<i>k</i> &#8594; &#8734;).
 
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 11. August 2021, 13:06 Uhr

Binäre symmetrische Markovquelle

Wir betrachten die binäre symmetrische Markovquelle entsprechend der Grafik, die durch den einzigen Parameter

$$q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y})$$

vollständig beschrieben wird.

  • Die angegebenen Quellensymbolfolgen gelten für die bedingten Wahrscheinlichkeiten  $q = 0.2$  bzw.  $q = 0.8$.
  • In der Teilaufgabe  (1)  ist zu klären, welche Symbolfolge – die rote oder die blaue – mit  $q = 0.2$  und welche mit  $q = 0.8$  generiert wurde.


Die Eigenschaften von Markovquellen werden im Kapitel  Nachrichtenquellen mit Gedächtnis  ausführlich beschrieben.  Aufgrund der hier vorausgesetzten Symmetrie bezüglich der Binärsymbole  $\rm X$  und  $\rm Y$  ergeben sich einige gravierende Vereinfachungen, wie in der  Aufgabe 1.5Z  hergeleitet wird:

  • Die Symbole  $\rm X$  und  $\rm Y$  sind gleichwahrscheinlich, das heißt, es gilt  $p_{\rm X} = p_{\rm Y} = 0.5$. 
    Damit lautet die erste Entropienäherung:   $H_1 = 1\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $
  • Die Entropie der Markovquelle ergibt sich sowohl für  $q = 0.2$  als auch für  $q = 0.8$  zu
$$H = q \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{q} + (1-q) \cdot {\rm log_2}\hspace{0.15cm}\frac{1}{1-q} = 0.722\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
  • Bei Markovquellen sind alle Entropienäherungen  $H_k$  mit Ordnung  $k \ge 2$  durch  $H_1$  und  $H = H_{k \to \infty}$  bestimmt:
$$H_k = {1}/{k}\cdot \big [ H_1 + H \big ] \hspace{0.05cm}.$$
  • Die folgenden Zahlenwerte gelten wieder für  $q = 0.2$  und  $q = 0.8$  gleichermaßen:
$$H_2 = {1}/{2}\cdot \big [ H_1 + H \big ] = 0.861\,\,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
$$H_3 = {1}/{3} \cdot \big [ H_1 + 2H \big ] = 0.815\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

In dieser Aufgabe soll der Huffman–Algorithmus auf  $k$–Tupel angewandt werden, wobei wir uns auf  $k = 2$  und  $k = 3$  beschränken.





Hinweise:


Fragebogen

1

Welche der vorne angegebenen Beispielfolgen gilt für  $q = 0.8$?

die rote Quellensymbolfolge  1,
die blaue Quellensymbolfolge  2.

2

Welche der folgenden Aussagen treffen zu?

Auch die direkte Anwendung von Huffman ist hier sinnvoll.
Huffman macht bei Bildung von Zweiertupeln  $(k = 2)$  Sinn.
Huffman macht bei Bildung von Dreiertupeln  $(k = 3)$  Sinn.

3

Wie lauten die Wahrscheinlichkeiten der Zweiertupel  $(k = 2)$  für  $\underline{q = 0.8}$?

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

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

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

$p_{\rm D} = \rm Pr(YY)\ = \ $

4

Ermitteln Sie den Huffman–Code für  $\underline{k = 2}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?

$L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

5

Welche Schranke ergibt sich für die mittlere Codewortlänge, wenn Zweiertupel gebildet werden  $(k = 2)$? Interpretation.

$L_{\rm M} \ge H_1 = 1.000$  bit/Quellensymbol,
$L_{\rm M} \ge H_2 \approx 0.861$  bit/Quellensymbol,
$L_{\rm M} \ge H_3 \approx 0.815$  bit/Quellensymbol,
$L_{\rm M} \ge H_{k \to \infty} \approx 0.722$  bit/Quellensymbol,
$L_{\rm M} \ge 0.5$  bit/Quellensymbol.

6

Berechnen Sie die Wahrscheinlichkeiten der Dreiertupel  $(k = 3)$  für  $\underline{q = 0.8}$?

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

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

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

$p_{\rm D} = \rm Pr(XYY)\ = \ $

$p_{\rm E} = \rm Pr(YXX)\ = \ $

$p_{\rm F} = \rm Pr(YXY)\ = \ $

$p_{\rm G} = \rm Pr(YYX)\ = \ $

$p_{\rm H} = \rm Pr(YYY)\ = \ $

7

Ermitteln Sie den Huffman–Code für $\underline{k = 3}$.  Wie groß ist in diesem Fall die mittlere Codewortlänge?

$L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$


Musterlösung

(1)  Richtig ist der Lösungsvorschlag 2:

  • Bei der blauen Quellensymbolfolge  2  erkennt man sehr viel weniger Symbolwechsel als in der roten Folge.
  • Die Symbolfolge  2  wurde mit dem Parameter  $q = {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.8$  erzeugt und die rote Symbolfolge  1  mit  $q = 0.2$.


(2)  Richtig sind die Antworten 2 und 3.:

  • Da hier die Quellensymbole  $\rm X$  und  $\rm Y$  als gleichwahrscheinlich angenommen wurden, macht die direkte Anwendung von Huffman keinen Sinn.
  • Dagegen kann man die inneren statistischen Bindungen der Markovquelle zur Datenkomprimierung nutzen, wenn man  $k$–Tupel bildet  $(k ≥ 2)$.
  • Je größer  $k$  ist, desto mehr nähert sich die mittlere Codewortlänge  $L_{\rm M}$  der Entropie  $H$.


(3)  Die Symbolwahrscheinlichkeiten sind  $p_{\rm X} = p_{\rm Y} = 0.5$.  Damit erhält man für die Zweiertupel:

$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XX}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot q = 0.5 \cdot 0.8 \hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm},$$
$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XY}) = p_{\rm X} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm X}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$
$$p_{\rm C} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YX}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm X}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot (1-q)= 0.5 \cdot 0.2 \hspace{0.15cm}\underline{ = 0.1} \hspace{0.05cm},$$
$$p_{\rm D} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm YY}) = p_{\rm Y} \cdot {\rm Pr}(\boldsymbol{\rm Y}\hspace{0.05cm}|\hspace{0.05cm}\boldsymbol{\rm Y}) = 0.5 \cdot q = 0.5 \cdot 0.8\hspace{0.15cm}\underline{ = 0.4} \hspace{0.05cm}.$$


Zur Huffman–Codierung für $k = 2$

(4)  Nebenstehender Bildschirmabzug des (früheren) SWF–Programms  Shannon–Fano–  und Huffman–Codierung  zeigt die Konstruktion des Huffman–Codes für  $k = 2$  mit den soeben berechneten Wahrscheinlichkeiten.

  • Damit gilt für die mittlere Codewortlänge:
$$L_{\rm M}\hspace{0.01cm}' = 0.4 \cdot 1 + 0.4 \cdot 2 + (0.1 + 0.1) \cdot 3 = 1.8\,\,{\rm bit/Zweiertupel}$$
$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 0.9\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$


(5)  Richtig ist der Lösungsvorschlag 2:

  • Nach dem Quellencodierungstheorem gilt  $L_{\rm M} ≥ H$.
  • Wendet man aber Huffman–Codierung an und lässt dabei Bindungen zwischen nicht benachbarten Symbolen außer Betracht  $(k = 2)$,  so gilt als unterste Grenze der Codewortlänge nicht  $H = 0.722$, sondern  $H_2 = 0.861$  (auf den Zusatz bit/Quellensymbol wird für den Rest der Aufgabe verzichtet).
  • Das Ergebnis der Teilaufgabe  (4)  war  $L_{\rm M} = 0.9.$
  • Würde eine unsymmetrische Markovkette vorliegen und zwar derart, dass sich für die Wahrscheinlichkeiten  $p_{\rm A}$, ... , $p_{\rm D}$  die Werte  $50\%$,  $25\%$  und zweimal  $12.5\%$  ergeben würden,  so käme man auf die mittlere Codewortlänge  $L_{\rm M} = 0.875$.
  • Wie die genauen Parameter dieser unsymmetrischen Markovquelle aussehen, weiß aber auch der Aufgabensteller (G. Söder) nicht.
  • Auch nicht, wie sich der Wert  $0.875$  auf  $0.861$  senken ließe. Der Huffman–Algorithmus ist hierfür jedenfalls ungeeignet.


(6)  Mit  $q = 0.8$  und  $1 - q = 0.2$  erhält man:

$$p_{\rm A} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXX}) = 0.5 \cdot q^2 \hspace{0.15cm}\underline{ = 0.32} = p_{\rm H} = {\rm Pr}(\boldsymbol{\rm YYY})\hspace{0.05cm},$$
$$p_{\rm B} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XXY}) = 0.5 \cdot q \cdot (1-q) \hspace{0.15cm}\underline{ = 0.08}= p_{\rm G} = {\rm Pr}(\boldsymbol{\rm YYX}) \hspace{0.05cm},$$
$$p_{\rm C} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYX}) = 0.5 \cdot (1-q)^2\hspace{0.15cm}\underline{ = 0.02} = p_{\rm F}= {\rm Pr}(\boldsymbol{\rm YXY}) \hspace{0.05cm},$$
$$p_{\rm D} \hspace{0.2cm} = \hspace{0.2cm} {\rm Pr}(\boldsymbol{\rm XYY}) = 0.5 \cdot (1-q) \cdot q \hspace{0.15cm}\underline{ = 0.08} = p_{\rm E} = {\rm Pr}(\boldsymbol{\rm YXX})\hspace{0.05cm}.$$


Zur Huffman–Codierung für $k = 3$

(7)  Der Bildschirmabzug des des (früheren) SWF–Programms  Shannon–Fano–  und Huffman–Codierung  verdeutlicht die Konstellation des Huffman–Codes für  $k = 3$. 

Damit erhält man für die mittlere Codewortlänge:

$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 2 + 0.24 \cdot 3 + 0.04 \cdot 5 = 2.52\,\,{\rm bit/Dreiertupel}$$
$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{3}\hspace{0.15cm}\underline{ = 0.84\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
  • Man erkennt die Verbesserung gegenüber der Teilaufgabe  (4).
  • Die für  $k = 2$  gültige Schranke  $H_2 = 0.861$  wird nun von der mittleren Codewortlänge  $L_{\rm M}$  unterschritten.
  • Die neue Schranke für  $k = 3$  ist  $H_3 = 0.815$.
  • Um die Quellenentropie  $H = 0.722$  zu erreichen  (besser gesagt:  diesem Endwert bis auf ein  $ε$  nahe zu kommen), müsste man allerdings unendlich lange Tupel bilden  $(k → ∞)$.