Aufgaben:Aufgabe 1.6: Nichtbinäre Markovquellen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(12 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Nachrichtenquellen mit Gedächtnis
+
{{quiz-Header|Buchseite=Informationstheorie/Nachrichtenquellen mit Gedächtnis
 
}}
 
}}
  
[[Datei:P_ID2253__Inf_A_1_6.png|right|]]
+
[[Datei:P_ID2253__Inf_A_1_6.png|right|frame|Markovquellen mit <br>$M = 3$&nbsp; und&nbsp; $M = 4$]]
:Die Grafik zeigt zwei ergodische Markovquellen (MQ):
+
Die Grafik zeigt zwei ergodische Markovquellen&nbsp; $\rm (MQ)$:
  
:* Die Quelle MQ3 ist durch <i>M</i> = 3 Zustände (Symbole) <b>N</b>, <b>M</b>, <b>P</b> gekennzeichnet. Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
+
* Die Quelle&nbsp; $\rm MQ3$&nbsp; ist durch&nbsp; $M = 3$&nbsp; Zustände (Symbole)&nbsp; $\rm N$,&nbsp; $\rm M$,&nbsp; $\rm P$&nbsp; gekennzeichnet.&nbsp; Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
 
:$$p_{\rm N} =  1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
 
:$$p_{\rm N} =  1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
  
:* Bei der Quelle MQ4 ist zusätzlich der Zustand <b>O</b> möglich &#8658; <i>M</i> = 4. Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
+
* Bei der Quelle&nbsp; $\rm MQ4$&nbsp; ist zusätzlich der Zustand&nbsp; $\rm O$&nbsp; möglich &nbsp; &#8658; &nbsp; $M = 4$.&nbsp; Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
 
:$$p_{\rm N} = p_{\rm M} = p_{\rm O} =  p_{\rm P} = 1/4\hspace{0.05cm}.$$
 
:$$p_{\rm N} = p_{\rm M} = p_{\rm O} =  p_{\rm P} = 1/4\hspace{0.05cm}.$$
  
:Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen &ndash; und nur bei diesen &ndash; durch <i>H</i><sub>1</sub> (Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend) und <i>H</i><sub>2</sub> (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel) gleichzeitig auch
+
Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen &ndash; und nur bei diesen &ndash; durch
 +
* $H_1$&nbsp; (erste Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und  
 +
* $H_2$&nbsp; (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel)  
  
:* die weiteren Entropienäherungen <i>H<sub>k</sub></i>(<i>k</i> = 3, 4, ... ) und
 
  
:* die tatsächliche Quellenentropie <i>H</i>
+
gleichzeitig auch bestimmt sind:
  
:bestimmt sind. Es gelten folgende Bestimmungsgleichungen:
+
* die weiteren Entropienäherungen&nbsp; $H_k$&nbsp; mit&nbsp; $k = 3, \ 4$,&nbsp; ...  und
:$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},\hspace{0.4cm}H_k =  \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H]  
+
* die tatsächliche Quellenentropie&nbsp; $H$.
 +
 
 +
 
 +
Es gelten folgende Bestimmungsgleichungen:
 +
:$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},$$
 +
:$$H_k =  {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ]  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>Hinweis:</b> Die Aufgabe gehört zu Kapitel 1.2. Hier finden Sie auch Hinweise zur Berechnung der ersten und zweiten Entropienäherung.
+
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
 +
*Bezug genommen wird insbesondere auf die Seite&nbsp;  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]].
 +
*Bei allen Entropien ist die Pseudoeinheit &bdquo;bit/Symbol&rdquo; hinzuzufügen.
 +
  
  
Zeile 28: Zeile 45:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Berechnen Sie die Entropienäherung <i>H</i><sub>1</sub> der Markovquelle MQ3.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_1$&nbsp;  der Markovquelle&nbsp;  $\rm MQ3$.
 
|type="{}"}
 
|type="{}"}
$MQ3:\ H_1$ = { 1.5 3% } $bit/Symbol$
+
$H_1 \ = \ $ { 1.5 3% } $\ \rm bit/Symbol$
  
  
{Berechnen Sie die Entropienäherung <i>H</i><sub>2</sub> der Markovquelle MQ3.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_2$&nbsp;  der Markovquelle&nbsp;  $\rm MQ3$.
 
|type="{}"}
 
|type="{}"}
$MQ3:\ H_2$ = { 1.375 3% } $bit/Symbol$
+
$H_2 \ = \  $ { 1.375 3% } $\ \rm bit/Symbol$
  
  
{Wie groß sind die Näherungen <i>H</i><sub>3</sub> und <i>H</i><sub>4</sub> und die Quellenentropie <i>H</i>?
+
{Wie groß sind für&nbsp; $\rm MQ3$&nbsp; die tatsächliche Quellenentropie&nbsp; $H$&nbsp; und die Näherungen&nbsp; $H_3$&nbsp; und&nbsp; $H_4$?
 
|type="{}"}
 
|type="{}"}
$MQ3:\ H_3$ = { 1.333 3% } $bit/Symbol$
+
$H \ = \ $ { 1.25 3% } $\ \rm bit/Symbol$
$H_4$ = { 1.3125 3% } $bit/Symbol$
+
$H_3 \ = \ $ { 1.333 3% } $\ \rm bit/Symbol$
$H$ = { 1.25 3% } $bit/Symbol$
+
$H_4 \ = \ $ { 1.3125 3% } $\ \rm bit/Symbol$
  
  
{Berechnen Sie die Entropienäherung <i>H</i><sub>1</sub> der Markovquelle MQ4.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_1$&nbsp;  der Markovquelle&nbsp;  $\rm MQ4$.
 
|type="{}"}
 
|type="{}"}
$MQ4:\ H_1$ = { 2 3% } $bit/Symbol$
+
$H_1 \ = \  $ { 2 3% } $\ \rm bit/Symbol$
  
  
{Berechnen Sie die Entropienäherung <i>H</i><sub>2</sub> der Markovquelle MQ4.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_2$&nbsp;  der Markovquelle&nbsp;  $\rm MQ4$.
 
|type="{}"}
 
|type="{}"}
$MQ4:\ H_2$ = { 1.5 3% } $bit/Symbol$
+
$H_2 \ =  \ $ { 1.5 3% } $\ \rm bit/Symbol$
  
  
{Wie groß sind hier die Näherungen <i>H</i><sub>3</sub> und <i>H</i><sub>4</sub> und die Quellenentropie <i>H</i>?
+
{Wie groß sind für&nbsp; $\rm MQ4$&nbsp; die tatsächliche Quellenentropie&nbsp; $H$&nbsp; und die Näherungen&nbsp; $H_3$&nbsp; und&nbsp; $H_4$?
 
|type="{}"}
 
|type="{}"}
$MQ4:\ H_3$ = { 1.333 3% } $bit/Symbol$
+
$H \ =  \ $ { 1 3% } $\ \rm bit/Symbol$
$H_4$ = { 1.25 3% } $bit/Symbol$
+
$H_3 \ =  \ $ { 1.333 3% } $\ \rm bit/Symbol$
$H$ = { 1 3% } $bit/Symbol$
+
$H_4 \ =  \ $ { 1.25 3% } $\ \rm bit/Symbol$
 
 
  
  
Zeile 67: Zeile 83:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben. Daraus lässt sich die Entropienäherung <i>H</i><sub>1</sub> berechnen:
+
'''(1)'''&nbsp; Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben.  
 +
*Daraus lässt sich die Entropienäherung&nbsp; $H_1$&nbsp; berechnen:
 
:$$H_{\rm 1}  =  1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 )  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
 
:$$H_{\rm 1}  =  1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 )  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>2.</b>&nbsp;&nbsp;Die Verbundwahrscheinlichkeit ist <i>p</i><sub>XY</sub> = <i>p</i><sub>X</sub> &middot; <i>p</i><sub>Y|X</sub>, wobei <i>p</i><sub>X</sub> die Symbolwahrscheinlichkeit von X angibt und <i>p</i><sub>Y|X</sub> die bedingte Wahrscheinlichkeit für <b>Y</b>, unter der Voraussetzung, dass vorher <b>X</b> aufgetreten ist. <b>X</b> und <b>Y</b> sind hier Platzhalter für die Symbole <b>N</b>, <b>P</b>, <b>M</b>. Dann gilt:
+
 
:$$p_{\rm NN} \hspace{0.1cm} = \hspace{0.1cm}  1/2 \cdot 1/2 = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm PP} =  1/4 \cdot 0 = 0\hspace{0.05cm},\hspace{0.2cm}p_{\rm MM} =  1/4 \cdot 0 = 0 \hspace{0.05cm},\\
+
 
p_{\rm NP} \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm PM} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm MN} =  1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\\
+
'''(2)'''&nbsp; Die Verbundwahrscheinlichkeit ist&nbsp; $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$,&nbsp; wobei&nbsp; $p_{\rm X}$&nbsp; die Symbolwahrscheinlichkeit von&nbsp; $\rm X$&nbsp; angibt und&nbsp; $p_{\rm Y|X}$&nbsp; die bedingte Wahrscheinlichkeit für&nbsp; $\rm Y$, unter der Voraussetzung, dass vorher&nbsp; $\rm X$&nbsp; aufgetreten ist.  
p_{\rm NM} \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm MP} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm PN} =  1/4 \cdot 1/2 = 1/8$$
+
 
:$$\Rightarrow \hspace{0.3cm} H_{\rm 2}  = \frac{1}{2} \cdot \left [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \right ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}}  
+
*$\rm X$&nbsp; und&nbsp; $\rm Y$&nbsp; sind hier Platzhalter für die Symbole&nbsp; $\rm N$,&nbsp; $\rm P$&nbsp; und&nbsp; $\rm M$.&nbsp; Dann gilt:
 +
:$$p_{\rm NN} = 1/2 \cdot 1/2 = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm PP} =  1/4 \cdot 0 = 0\hspace{0.05cm},\hspace{0.2cm}p_{\rm MM} =  1/4 \cdot 0 = 0 \hspace{0.05cm},$$
 +
:$$ p_{\rm NP} =  1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm PM} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm MN} =  1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$
 +
:$$ p_{\rm NM} =  1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm MP} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm PN} =  1/4 \cdot 1/2 = 1/8$$
 +
:$$\Rightarrow \hspace{0.3cm} H_{\rm 2}  = {1}/{2} \cdot \big [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>3.</b>&nbsp;&nbsp;Da MQ3 Markoveigenschaften aufweist, können aus <i>H</i><sub>1</sub> und <i>H</i><sub>2</sub> alle Entropienäherungen <nobr><i>H<sub>k</sub></i> (<i>k</i> = 3, 4, ... )</nobr> direkt angegeben werden und auch der Grenzwert <i>H</i> = <i>H<sub>k</sub></i> für <i>k</i> &#8594; &#8734;:
+
 
:$$H  \hspace{0.1cm} = \hspace{0.1cm} 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{1.25cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},\\
+
 
H_3 \hspace{0.1cm} =  \hspace{0.1cm}  (H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},\\
+
'''(3)'''&nbsp; $\rm MQ3$&nbsp; weist Markoveigenschaften auf.
H_4 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
+
* Deshalb können aus&nbsp; $H_1$&nbsp; und&nbsp; $H_2$&nbsp; alle Näherungen&nbsp; $H_3$,&nbsp; $H_4$,&nbsp; ... und auch der Grenzwert&nbsp; $H =H_\infty$&nbsp;  für&nbsp; $k \to \infty$&nbsp; angegeben werden:
:Die 10. Entropienäherung unterscheidet sich noch immer, wenn auch nur  geringfügig (um 2%) vom Endwert <i>H</i> = 1.25 bit/Symbol:
+
:$$H  =  2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
 +
:$$ H_3 \hspace{0.1cm} =  \hspace{0.1cm}= (H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
 +
:$$ H_4 = (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
 +
*Die zehnte Entropienäherung unterscheidet sich noch immer vom Endwert&nbsp; $H = 1.25 \, \rm bit/Symbol$,&nbsp; wenn auch nur  geringfügig&nbsp; $($um $2\%)$&nbsp;:
 
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10  {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
 
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10  {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
  
:<b>4.</b>&nbsp;&nbsp;Entsprechend der Angabe sind hier die Symbole gleichwahrscheinlich. Daraus folgt:
+
 
 +
 
 +
'''(4)'''&nbsp; Entsprechend der Angabe sind bei&nbsp; $\rm MQ4$&nbsp; die&nbsp; $M = 4$&nbsp; Symbole gleichwahrscheinlich.  
 +
*Daraus folgt:
 
:$$H_{\rm 1}  = H_{\rm 0}  = {\rm log}_2\hspace{0.1cm} (4)  \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}}  
 
:$$H_{\rm 1}  = H_{\rm 0}  = {\rm log}_2\hspace{0.1cm} (4)  \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>5.</b>&nbsp;&nbsp;Von den <i>M</i><sup>2</sup> = 16 möglichen Zweiertupeln sind acht Kombinationen nicht möglich: <b>NP</b>, <b>NO</b>, <b>PP</b>, <b>PO</b>, <b>OM</b>, <b>ON</b>, <b>MM</b>, <b>MN</b>. Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert 1/8, wie an zwei Beispielen gezeigt werden soll:
+
 
:$$p_{\rm NN} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8  \hspace{0.05cm},\\
+
 
p_{\rm MP} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm M} \cdot p_{\rm P\hspace{0.01cm}|\hspace{0.01cm}M} = 1/4 \cdot 1/2 = 1/8  \hspace{0.05cm}.$$
+
'''(5)'''&nbsp; Von den&nbsp; $M^2 = 16$&nbsp; möglichen Zweiertupeln sind nun acht Kombinationen nicht möglich:  
:$$\Rightarrow \hspace{0.3cm} H_2 =  \frac{1}{2} \cdot \left [ 8 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm} (8)  \right ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
+
:$$\rm NP, NO, PP, PO, OM, ON, MM, MN.$$
 +
 
 +
*Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert&nbsp; $1/8$, wie an zwei Beispielen gezeigt wird:
 +
:$$p_{\rm NN} = p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8  \hspace{0.05cm},\hspace{0.5cm}
 +
p_{\rm MP} = p_{\rm M} \cdot p_{\rm P\hspace{0.01cm}|\hspace{0.01cm}M} = 1/4 \cdot 1/2 = 1/8  \hspace{0.05cm}.$$
 +
:$$\Rightarrow \hspace{0.3cm} H_2 =  {1}/{2} \cdot \big [ 8 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8)  \big ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>6.</b>&nbsp;&nbsp;Aufgrund der Markoveigenschaft gilt hier:
+
 
:$$H  \hspace{0.1cm} = \hspace{0.1cm} 2 \cdot H_2 - H_1 = 2\cdot 1.5 - 2 \hspace{1.15cm} \underline {= 1 \,{\rm bit/Symbol}}\hspace{0.05cm},\\
+
 
H_3 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 2 \cdot H)/3 = (2 + 2 \cdot 1)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},\\
+
'''(6)'''&nbsp; Aufgrund der Markoveigenschaft gilt hier:
H_4 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 3 \cdot H)/4 = (2 + 3 \cdot 1)/4 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
+
:$$H  =  2 \cdot H_2 - H_1 = 2\cdot 1.5 - 2 \hspace{0.15cm} \underline {= 1 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
:Auch hier unterscheidet sich die 10. Näherung noch deutlich vom Endwert, nämlich um 10%:
+
:$$ H_3 =  (H_1 + 2 \cdot H)/3 = (2 + 2 \cdot 1)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
 +
:$$ H_4 = (H_1 + 3 \cdot H)/4 = (2 + 3 \cdot 1)/4 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
 +
*Auch hier unterscheidet sich die zehnte Näherung noch deutlich vom Endwert, nämlich um&nbsp; $10\%$:
 
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (2 + 9 \cdot 1)/10  {= 1.1 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
 
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (2 + 9 \cdot 1)/10  {= 1.1 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
:Eine Abweichung um 2% ergibt sich hier erst für <i>k</i> = 50. Zum Vergleich: Bei der Markovquelle MQ3 wurde diese Annäherung bereits mit <i>k</i> = 10 erreicht.
+
*Eine Abweichung um nur&nbsp;  $2\%$&nbsp; ergibt sich hier erst für&nbsp; $k = 50$.&nbsp; Zum Vergleich: &nbsp; Bei der Markovquelle&nbsp; $\rm MQ3$&nbsp; wurde diese Annäherung bereits mit&nbsp; $k = 10$&nbsp; erreicht.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 17. Januar 2020, 16:42 Uhr

Markovquellen mit
$M = 3$  und  $M = 4$

Die Grafik zeigt zwei ergodische Markovquellen  $\rm (MQ)$:

  • Die Quelle  $\rm MQ3$  ist durch  $M = 3$  Zustände (Symbole)  $\rm N$,  $\rm M$,  $\rm P$  gekennzeichnet.  Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
$$p_{\rm N} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
  • Bei der Quelle  $\rm MQ4$  ist zusätzlich der Zustand  $\rm O$  möglich   ⇒   $M = 4$.  Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
$$p_{\rm N} = p_{\rm M} = p_{\rm O} = p_{\rm P} = 1/4\hspace{0.05cm}.$$

Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen – und nur bei diesen – durch

  • $H_1$  (erste Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und
  • $H_2$  (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel)


gleichzeitig auch bestimmt sind:

  • die weiteren Entropienäherungen  $H_k$  mit  $k = 3, \ 4$,  ... und
  • die tatsächliche Quellenentropie  $H$.


Es gelten folgende Bestimmungsgleichungen:

$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},$$
$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ] \hspace{0.05cm}.$$





Hinweise:


Fragebogen

1

Berechnen Sie die Entropienäherung  $H_1$  der Markovquelle  $\rm MQ3$.

$H_1 \ = \ $

$\ \rm bit/Symbol$

2

Berechnen Sie die Entropienäherung  $H_2$  der Markovquelle  $\rm MQ3$.

$H_2 \ = \ $

$\ \rm bit/Symbol$

3

Wie groß sind für  $\rm MQ3$  die tatsächliche Quellenentropie  $H$  und die Näherungen  $H_3$  und  $H_4$?

$H \ = \ $

$\ \rm bit/Symbol$
$H_3 \ = \ $

$\ \rm bit/Symbol$
$H_4 \ = \ $

$\ \rm bit/Symbol$

4

Berechnen Sie die Entropienäherung  $H_1$  der Markovquelle  $\rm MQ4$.

$H_1 \ = \ $

$\ \rm bit/Symbol$

5

Berechnen Sie die Entropienäherung  $H_2$  der Markovquelle  $\rm MQ4$.

$H_2 \ = \ $

$\ \rm bit/Symbol$

6

Wie groß sind für  $\rm MQ4$  die tatsächliche Quellenentropie  $H$  und die Näherungen  $H_3$  und  $H_4$?

$H \ = \ $

$\ \rm bit/Symbol$
$H_3 \ = \ $

$\ \rm bit/Symbol$
$H_4 \ = \ $

$\ \rm bit/Symbol$


Musterlösung

(1)  Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben.

  • Daraus lässt sich die Entropienäherung  $H_1$  berechnen:
$$H_{\rm 1} = 1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 ) \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(2)  Die Verbundwahrscheinlichkeit ist  $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$,  wobei  $p_{\rm X}$  die Symbolwahrscheinlichkeit von  $\rm X$  angibt und  $p_{\rm Y|X}$  die bedingte Wahrscheinlichkeit für  $\rm Y$, unter der Voraussetzung, dass vorher  $\rm X$  aufgetreten ist.

  • $\rm X$  und  $\rm Y$  sind hier Platzhalter für die Symbole  $\rm N$,  $\rm P$  und  $\rm M$.  Dann gilt:
$$p_{\rm NN} = 1/2 \cdot 1/2 = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm PP} = 1/4 \cdot 0 = 0\hspace{0.05cm},\hspace{0.2cm}p_{\rm MM} = 1/4 \cdot 0 = 0 \hspace{0.05cm},$$
$$ p_{\rm NP} = 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm PM} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm MN} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$
$$ p_{\rm NM} = 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm MP} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm PN} = 1/4 \cdot 1/2 = 1/8$$
$$\Rightarrow \hspace{0.3cm} H_{\rm 2} = {1}/{2} \cdot \big [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(3)  $\rm MQ3$  weist Markoveigenschaften auf.

  • Deshalb können aus  $H_1$  und  $H_2$  alle Näherungen  $H_3$,  $H_4$,  ... und auch der Grenzwert  $H =H_\infty$  für  $k \to \infty$  angegeben werden:
$$H = 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
$$ H_3 \hspace{0.1cm} = \hspace{0.1cm}= (H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
$$ H_4 = (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
  • Die zehnte Entropienäherung unterscheidet sich noch immer vom Endwert  $H = 1.25 \, \rm bit/Symbol$,  wenn auch nur geringfügig  $($um $2\%)$ :
$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10 {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$


(4)  Entsprechend der Angabe sind bei  $\rm MQ4$  die  $M = 4$  Symbole gleichwahrscheinlich.

  • Daraus folgt:
$$H_{\rm 1} = H_{\rm 0} = {\rm log}_2\hspace{0.1cm} (4) \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(5)  Von den  $M^2 = 16$  möglichen Zweiertupeln sind nun acht Kombinationen nicht möglich:

$$\rm NP, NO, PP, PO, OM, ON, MM, MN.$$
  • Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert  $1/8$, wie an zwei Beispielen gezeigt wird:
$$p_{\rm NN} = p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\hspace{0.5cm} p_{\rm MP} = p_{\rm M} \cdot p_{\rm P\hspace{0.01cm}|\hspace{0.01cm}M} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$
$$\Rightarrow \hspace{0.3cm} H_2 = {1}/{2} \cdot \big [ 8 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(6)  Aufgrund der Markoveigenschaft gilt hier:

$$H = 2 \cdot H_2 - H_1 = 2\cdot 1.5 - 2 \hspace{0.15cm} \underline {= 1 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
$$ H_3 = (H_1 + 2 \cdot H)/3 = (2 + 2 \cdot 1)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
$$ H_4 = (H_1 + 3 \cdot H)/4 = (2 + 3 \cdot 1)/4 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
  • Auch hier unterscheidet sich die zehnte Näherung noch deutlich vom Endwert, nämlich um  $10\%$:
$$H_{10} = (H_1 + 9 \cdot H)/10 = (2 + 9 \cdot 1)/10 {= 1.1 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
  • Eine Abweichung um nur  $2\%$  ergibt sich hier erst für  $k = 50$.  Zum Vergleich:   Bei der Markovquelle  $\rm MQ3$  wurde diese Annäherung bereits mit  $k = 10$  erreicht.