Aufgaben:Aufgabe 1.6Z: Ternäre Markovquelle: 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_ID2254__Inf_Z_1_6.png|right|]]
+
[[Datei:Inf_Z_1_6_vers2.png|right|frame|Ternäre Markovquelle]]
:Die Grafik zeigt eine Markovquelle mit <i>M</i> = 3 Zuständen <b>A</b>, <b>B</b> und <b>C</b>. Für die beiden Parameter dieses Markovprozesses soll gelten:
+
Die Grafik zeigt eine Markovquelle mit&nbsp; $M = 3$&nbsp; Zuständen&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; und&nbsp; $\rm C$.  
 +
 
 +
Für die beiden Parameter dieses Markovprozesses soll gelten:
 
:$$0 \le p \le 0.5 \hspace{0.05cm},\hspace{0.2cm}0 \le q \le 1 \hspace{0.05cm}.$$
 
:$$0 \le p \le 0.5 \hspace{0.05cm},\hspace{0.2cm}0 \le q \le 1 \hspace{0.05cm}.$$
:Aufgrund der Markoveigenschaft dieser Quelle kann die Entropie auf unterschiedliche Weise ermittelt werden:
+
Aufgrund der Markoveigenschaft dieser Quelle kann die Entropie auf unterschiedliche Weise ermittelt werden:
  
:<ul class="liste_ohne"><li>Man berechnet die beiden ersten Entropienäherungen <i>H</i><sub>1</sub> und <i>H</i><sub>2</sub>. Dann gilt:
+
*Man berechnet die <i>beiden ersten Entropienäherungen</i>&nbsp; $H_1$&nbsp; und&nbsp; $H_2$.&nbsp; Dann gilt für die tatsächliche Entropie:
 
:$$H  = 2 \cdot H_{\rm 2} - H_{\rm 1}  \hspace{0.05cm}.$$
 
:$$H  = 2 \cdot H_{\rm 2} - H_{\rm 1}  \hspace{0.05cm}.$$
  
:<ul class="liste_ohne"><li>Nach der so genannten <i>direkten Berechnungsmethode</i> kann die Entropie aber auch wie folgt berechnet werden (insgesamt 9 Terme):
+
*Nach der <i>direkten Berechnungsmethode</i> kann die Entropie aber auch wie folgt geschrieben werden&nbsp; (insgesamt neun Terme):
:$$H = p_{\rm AA}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  ...
+
:$$H = p_{\rm AA}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  \ \text{...}
  \hspace{0.15cm},$$
+
  \hspace{0.05cm}, \
:$$p_{\rm AA} = p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm},\hspace{0.2cm}
+
\text{wobei} \ p_{\rm AA} = p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm},\hspace{0.2cm}
p_{\rm AB} = p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm}, \hspace{0.1cm}...$$
+
p_{\rm AB} = p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm}, \ \text{...}$$
 +
 
 +
 
  
:<b>Hinwis:</b> Die Aufgabe gehört zum Themenkomplex von Kapitel 1.2.
+
 
 +
 
 +
 
 +
 
 +
 
 +
''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 23: Zeile 36:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Für welche Parameter <i>p</i>, <i>q</i> ergibt sich die maximale Entropie pro Symbol?
+
{Für welche Parameter &nbsp;$p$ &nbsp;und&nbsp;  $q$&nbsp; ergibt sich die maximale Entropie pro Symbol?
 
|type="{}"}
 
|type="{}"}
$p$ = { 0.333 3% }
+
$p \ = \ $ { 0.333 1% }
$q$ = { 1.585 3% }
+
$q\ =  \ $ { 1 1% }
$H_\text{max}$ = { 1.585 3% } $bit/Symbol$
+
$H_\text{max} \ =  \ $ { 1.585 1% } $\ \rm bit/Symbol$
  
  
{Es sei <i>p</i> = 1/4 und <i>q</i> = 1. Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung?
+
{Es sei &nbsp;$p = 1/4$ &nbsp;und&nbsp;  $q = 1$.&nbsp; Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung?
 
|type="{}"}
 
|type="{}"}
$p = 1/4, q = 1:\ \ H_1$ = { 1.585 3% } $bit/Symbol$
+
$H_1 = \ \ $ { 1.585 3% } $\ \rm bit/Symbol$
  
  
{Weiterhin gelte <i>p</i> = 1/4 und <i>q</i> = 1. Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung?
+
{Weiterhin gelte &nbsp;$p = 1/4$ &nbsp;und&nbsp;  $q = 1$.&nbsp; Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung?
 
|type="{}"}
 
|type="{}"}
$p = 1/4, q = 1:\ \ H_2$ = { 1.5425 3% } $bit/Symbol$
+
$H_2 = \ \ $ { 1.5425 1% } $\ \rm bit/Symbol$
  
  
{Wie groß ist die Quellenentropie mit <i>p</i> = 1/4, <i>q</i> = 1?
+
{Wie groß ist die tatsächliche Quellenentropie mit &nbsp;$p = 1/4$ &nbsp;und&nbsp;  $q = 1$?
 
|type="{}"}
 
|type="{}"}
$p = 1/4, q = 1:\ \ H$ = { 1.5 3% } $bit/Symbol$
+
$H = \ \ $ { 1.5 1% } $\ \rm bit/Symbol$
  
  
{Wie groß ist die Quellenentropie mit  <i>p</i> = 1/2, <i>q</i> = 0?
+
{Wie groß ist die tatsächliche Quellenentropie mit  &nbsp;$p = 1/2$ &nbsp;und&nbsp;  $q = 0$?
 
|type="{}"}
 
|type="{}"}
$p = 1/2, q = 0:\ \ H$ = { 0.667 3% } $bit/Symbol$
+
$H = \ \ $ { 0.667 1% } $\ \rm bit/Symbol$
  
  
Zeile 55: Zeile 68:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<i>Hinweis:</i> Aus Platzgründen verwenden wir in der Musterlösung &bdquo;ld&rdquo; anstelle von  &bdquo;log<sub>2</sub>&rdquo;.
+
'''(1)'''&nbsp; Die maximale Entropie ergibt sich dann, wenn die Symbole&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; und&nbsp; $\rm C$&nbsp; gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:
 +
[[Datei:Inf_Z_1_6_vers2.png|right|frame|Übergangsdiagramm für&nbsp; $p = 1/4$,&nbsp; $q = 1$]]
 +
* $p_{\rm A} = p_{\rm A|A} =  p_{\rm A|B} = p_{\rm A|C}  = 1/3$,
 +
* $p_{\rm B} = p_{\rm B|A} =  p_{\rm B|B} = p_{\rm B|C}  = 1/3$,
 +
* $p_{\rm C} = p_{\rm C|A} =  p_{\rm C|B} = p_{\rm C|C}  = 1/3$.
  
:<b>a)</b>&nbsp;&nbsp;Die maximale Entropie ergibt sich dann, wenn die Symbole <b>A</b>, <b>B</b> und <b>C</b> gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:
 
  
:* <i>p</i><sub>A</sub> = <i>p</i><sub>A|A</sub> = <i>p</i><sub>A|B</sub> = <i>p</i><sub>A|C</sub> = 1/3,
+
Daraus lassen sich die gesuchten Werte bestimmen:
 +
*Beispielsweise erhält man aus&nbsp; $p_{\rm C|C}  = 1/3$&nbsp; den Wert &nbsp;$p \hspace{0.15cm}\underline{= 1/3}$.
 +
*Berücksichtigt man noch die Beziehung &nbsp;$p_{\rm A|A} = p \cdot q$,&nbsp; so folgt &nbsp;$q \hspace{0.15cm}\underline{= 1}$.
 +
* Damit ergibt sich die maximale Entropie &nbsp;$H_\text{max} ={\rm  log_2} \ 3\hspace{0.15cm}\underline{= 1.585\  \rm bit/Symbol}$.
  
:* <i>p</i><sub>B</sub> = <i>p</i><sub>B|A</sub> = <i>p</i><sub>B|B</sub> = <i>p</i><sub>B|C</sub> = 1/3,
 
  
:* <i>p</i><sub>C</sub> = <i>p</i><sub>C|A</sub> = <i>p</i><sub>C|B</sub> = <i>p</i><sub>C|C</sub> = 1/3.
 
  
:Beispielsweise erhält man aus <i>p</i><sub>C|C</sub> = 1/3 der Wert <u><i>p</i> = 1/3</u>. Berücksichtigt man noch <i>p</i><sub>A|A</sub> = <i>q</i> &middot; <i>p</i>, so folgt <u><i>q</i> = 1</u>. Damit ergibt sich die maximale Entropie <i>H</i><sub>max</sub> = ld 3 <u>= 1.585 bit/Symbol</u>.
+
'''(2)'''&nbsp; Mit den Parameterwerten&nbsp;  $p = 1/4$ &nbsp;und&nbsp;  $q = 1$ ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:
[[Datei:P_ID2255__Inf_Z_1_6b.png|right|]]
+
* $p_{\rm A|A} =  p_{\rm B|B} = p_{\rm C|C= 1/4$&nbsp; (rot markiert),
 +
* $p_{\rm A|B} =  p_{\rm B|C} = p_{\rm C|A= 1/2$&nbsp; (grün markiert),
 +
*$p_{\rm A|C} = p_{\rm B|A} = p_{\rm C|CB}  = 1/4$&nbsp; (blau markiert).
  
:<b>2.</b>&nbsp;&nbsp;Mit den Parameterwerten <i>p</i> = 1/4 und <i>q</i> = 1 ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:
 
  
:* <i>p</i><sub>A|A</sub> = <i>p</i><sub>B|B</sub> = <i>p</i><sub>C|C</sub> = 1/4 (rot markiert),
+
Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind:
 +
:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3 \hspace{0.3cm}
 +
\Rightarrow \hspace{0.3cm} H_1 =  {\rm log_2}\hspace{0.1cm} 3  \hspace{0.15cm} \underline {= 1.585 \,{\rm bit/Symbol}}
 +
\hspace{0.05cm}.$$
  
:* <i>p</i><sub>A|B</sub> = <i>p</i><sub>B|C</sub> = <i>p</i><sub>C|A</sub> = 1/2 (grün markiert),
 
  
:* <i>p</i><sub>A|C</sub> = <i>p</i><sub>B|A</sub> = <i>p</i><sub>C|B</sub> = 1/4 (blau markiert).
 
  
:Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind:
+
'''(3)'''&nbsp; Für die zweite Entropienäherung benötigt man&nbsp; $3^2 = 9$&nbsp; Verbundwahrscheinlichkeiten.
:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3$$
+
*Mit dem Ergebnis aus&nbsp; '''(2)'''&nbsp; erhält man hierfür:
:$$\Rightarrow \hspace{0.3cm} H_1 =  {\rm ld}\hspace{0.1cm} 3  \hspace{0.15cm} \underline {= 1.585 \,{\rm bit/Symbol}}  
+
:$$p_{\rm AA} = p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12  \hspace{0.05cm},\hspace{0.5cm}
 +
p_{\rm AB} = p_{\rm BC}=p_{\rm CA}=1/6$$
 +
:$$\Rightarrow \hspace{0.2cm} H_2  = \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm ld}\hspace{0.1cm} 12  +
 +
3 \cdot \frac{1}{6} \cdot {\rm log_2}\hspace{0.1cm} 6 \right ] \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 4  + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 +  \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 2 +  \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3  
 +
  = \frac{3}{4} + \frac{{\rm log_2}\hspace{0.1cm} 3}{2} \hspace{0.15cm} \underline {= 1.5425 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>3.</b>&nbsp;&nbsp;Für die zweite Entropienäherung benötigt man die 3<sup>2</sup> = 9 Verbundwahrscheinlichkeiten. Mit dem Ergebnis der Teilaufgabe b) erhält man hierfür:
 
:$$p_{\rm AA} \hspace{0.1cm} =  \hspace{0.1cm} p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12  \hspace{0.05cm},\\
 
p_{\rm AB} \hspace{0.1cm} =  \hspace{0.1cm} p_{\rm BC}=p_{\rm CA}=1/6$$
 
:$$\Rightarrow \hspace{0.2cm} H_2 \hspace{0.15cm} =  \hspace{0.15cm}  \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm ld}\hspace{0.1cm} 12  +
 
3 \cdot \frac{1}{6} \cdot {\rm ld}\hspace{0.1cm} 6 \right ] = \\
 
\hspace{0.15cm} =  \hspace{0.15cm}  \frac{1}{4} \cdot {\rm ld}\hspace{0.1cm} 4  + \frac{1}{4} \cdot {\rm ld}\hspace{0.1cm} 3 +  \frac{1}{4} \cdot {\rm ld}\hspace{0.1cm} 2 +  \frac{1}{4} \cdot {\rm ld}\hspace{0.1cm} 3
 
= \frac{3}{4} + \frac{{\rm ld}\hspace{0.1cm} 3}{2} \hspace{0.15cm} \underline {= 1.5425 \,{\rm bit/Symbol}}
 
\hspace{0.05cm}.$$
 
  
:<b>4.</b>&nbsp;&nbsp;Aufgrund der Markoveigenschaft der Quelle gilt
+
 
:$$H = 2 \cdot H_2 - H_1 = [ {3}/{2} + {\rm ld}\hspace{0.1cm} 3] -  {\rm ld}\hspace{0.1cm} 3\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
+
'''(4)'''&nbsp; Aufgrund der Markoveigenschaft der Quelle gilt
 +
:$$H = 2 \cdot H_2 - H_1 = \big [ {3}/{2} + {\rm log_2}\hspace{0.1cm} 3 \big ] -  {\rm log_2}\hspace{0.1cm} 3\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
:Zum gleichen Ergebnis würde man mit folgender Rechnung kommen:
+
*Zum gleichen Ergebnis würde man nach folgender Rechnung kommen:
:$$H \hspace{0.1cm} = \hspace{0.1cm} p_{\rm AA}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  ... \\
+
:$$H= p_{\rm AA}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  ... \hspace{0.1cm}= 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 4 + 3 \cdot \frac{1}{16} \cdot {\rm log_2}\hspace{0.1cm} 2
\hspace{0.1cm} = \hspace{0.1cm} 6 \cdot \frac{1}{12} \cdot {\rm ld}\hspace{0.1cm} 4 + 3 \cdot \frac{1}{16} \cdot {\rm ld}\hspace{0.1cm} 2
 
 
  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}
 
  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
[[Datei:P_ID2256__Inf_Z_1_6e.png|right|]]
 
  
:<b>5.</b>&nbsp;&nbsp;Aus nebenstehendem Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität <i>p</i><sub>B</sub> = 0 gelten wird: <b>B</b> kann höchstens zum Starzeitpunkt einmal auftreten. Es liegt also eine binäre Markovkette mit den Symbolen <b>A</b> und <b>C</b> vor. Die Symbolwahrscheinlichkeiten ergeben sich zu:
+
 
:$$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 $$
+
[[Datei:Inf_Z_1_6e_vers2.png|right|frame|Übergangsdiagramm für&nbsp; $p = 1/4$,&nbsp; $q = 0$]]
:$$\Rightarrow \hspace{0.3cm} p_{\rm A} = 1/3 \hspace{0.05cm}, \hspace{0.2cm} p_{\rm C} = 2/3\hspace{0.05cm}.  $$
+
'''(5)'''&nbsp; Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität&nbsp; $p_{\rm B= 0$&nbsp; gelten wird, da&nbsp; $\rm B$&nbsp; höchstens zum Startzeitpunkt einmal auftreten kann.  
:<br>Damit erhält man folgende Wahrscheinlichkeiten:
+
*Es liegt also eine binäre Markovkette mit den Symbolen&nbsp; $\rm A$&nbsp; und&nbsp; $\rm C$&nbsp; vor.  
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} =  \hspace{0.1cm}0\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AA} = 0 \hspace{0.05cm},\\
+
*Die Symbolwahrscheinlichkeiten ergeben sich demzufolge zu:
p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} \hspace{0.1cm} = \hspace{0.1cm}1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CA} =  
+
:$$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 \hspace{0.3cm}
  p_{\rm C} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3 \hspace{0.05cm},\hspace{0.2cm}{\rm ld}\hspace{0.1cm}(1/p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} )= 1\hspace{0.05cm},\\
+
\Rightarrow \hspace{0.3cm} p_{\rm A} = 1/3 \hspace{0.05cm}, \hspace{0.2cm} p_{\rm C} = 2/3\hspace{0.05cm}.  $$
p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AC} =  
+
 
  p_{\rm A} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} = 1/3 \cdot 1 = 1/3 \hspace{0.05cm},\hspace{0.61cm}{\rm ld}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} )= 0\hspace{0.05cm},\\
+
*Damit erhält man folgende Wahrscheinlichkeiten:
p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} \hspace{0.1cm} = \hspace{0.1cm}1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CC} =  
+
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} =  \hspace{0.1cm}0\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AA} = 0 \hspace{0.05cm},$$
  p_{\rm C} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3\hspace{0.05cm},\hspace{0.2cm}{\rm ld}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} )= 1 $$
+
:$$ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CA} =  
:$$\Rightarrow \hspace{0.3cm} H  \hspace{0.1cm} = \hspace{0.1cm} p_{\rm AA}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}}  +p_{\rm CA}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C}}+ p_{\rm AC} \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A}} +  
+
  p_{\rm C} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3 \hspace{0.05cm},\hspace{0.2cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} )= 1\hspace{0.05cm},$$
   p_{\rm CC}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}=
+
:$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} =1\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AC} =  
\\
+
  p_{\rm A} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} = 1/3 \cdot 1 = 1/3 \hspace{0.05cm},\hspace{0.61cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} )= 0\hspace{0.05cm},$$
\hspace{0.1cm} =  \hspace{0.1cm}0 + 1/3 \cdot 1 + 1/3 \cdot 0 + 1/3 \cdot 1
+
:$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CC} =  
 +
  p_{\rm C} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3\hspace{0.05cm},\hspace{0.2cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} )= 1 $$
 +
:$$\Rightarrow \hspace{0.25cm} H  = p_{\rm AA}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}}  +p_{\rm CA}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C}}+ p_{\rm AC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A}} +  
 +
   p_{\rm CC}  \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}=
 +
0 + 1/3 \cdot 1 + 1/3 \cdot 0 + 1/3 \cdot 1
 
  \hspace{0.15cm} \underline {= 0.667 \,{\rm bit/Symbol}}  
 
  \hspace{0.15cm} \underline {= 0.667 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$

Version vom 17. Januar 2020, 16:58 Uhr

Ternäre Markovquelle

Die Grafik zeigt eine Markovquelle mit  $M = 3$  Zuständen  $\rm A$,  $\rm B$  und  $\rm C$.

Für die beiden Parameter dieses Markovprozesses soll gelten:

$$0 \le p \le 0.5 \hspace{0.05cm},\hspace{0.2cm}0 \le q \le 1 \hspace{0.05cm}.$$

Aufgrund der Markoveigenschaft dieser Quelle kann die Entropie auf unterschiedliche Weise ermittelt werden:

  • Man berechnet die beiden ersten Entropienäherungen  $H_1$  und  $H_2$.  Dann gilt für die tatsächliche Entropie:
$$H = 2 \cdot H_{\rm 2} - H_{\rm 1} \hspace{0.05cm}.$$
  • Nach der direkten Berechnungsmethode kann die Entropie aber auch wie folgt geschrieben werden  (insgesamt neun Terme):
$$H = p_{\rm AA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + \ \text{...} \hspace{0.05cm}, \ \text{wobei} \ p_{\rm AA} = p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm},\hspace{0.2cm} p_{\rm AB} = p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm}, \ \text{...}$$





Hinweise:


Fragebogen

1

Für welche Parameter  $p$  und  $q$  ergibt sich die maximale Entropie pro Symbol?

$p \ = \ $

$q\ = \ $

$H_\text{max} \ = \ $

$\ \rm bit/Symbol$

2

Es sei  $p = 1/4$  und  $q = 1$.  Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung?

$H_1 = \ \ $

$\ \rm bit/Symbol$

3

Weiterhin gelte  $p = 1/4$  und  $q = 1$.  Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung?

$H_2 = \ \ $

$\ \rm bit/Symbol$

4

Wie groß ist die tatsächliche Quellenentropie mit  $p = 1/4$  und  $q = 1$?

$H = \ \ $

$\ \rm bit/Symbol$

5

Wie groß ist die tatsächliche Quellenentropie mit  $p = 1/2$  und  $q = 0$?

$H = \ \ $

$\ \rm bit/Symbol$


Musterlösung

(1)  Die maximale Entropie ergibt sich dann, wenn die Symbole  $\rm A$,  $\rm B$  und  $\rm C$  gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:

Übergangsdiagramm für  $p = 1/4$,  $q = 1$
  • $p_{\rm A} = p_{\rm A|A} = p_{\rm A|B} = p_{\rm A|C} = 1/3$,
  • $p_{\rm B} = p_{\rm B|A} = p_{\rm B|B} = p_{\rm B|C} = 1/3$,
  • $p_{\rm C} = p_{\rm C|A} = p_{\rm C|B} = p_{\rm C|C} = 1/3$.


Daraus lassen sich die gesuchten Werte bestimmen:

  • Beispielsweise erhält man aus  $p_{\rm C|C} = 1/3$  den Wert  $p \hspace{0.15cm}\underline{= 1/3}$.
  • Berücksichtigt man noch die Beziehung  $p_{\rm A|A} = p \cdot q$,  so folgt  $q \hspace{0.15cm}\underline{= 1}$.
  • Damit ergibt sich die maximale Entropie  $H_\text{max} ={\rm log_2} \ 3\hspace{0.15cm}\underline{= 1.585\ \rm bit/Symbol}$.


(2)  Mit den Parameterwerten  $p = 1/4$  und  $q = 1$ ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:

  • $p_{\rm A|A} = p_{\rm B|B} = p_{\rm C|C} = 1/4$  (rot markiert),
  • $p_{\rm A|B} = p_{\rm B|C} = p_{\rm C|A} = 1/2$  (grün markiert),
  • $p_{\rm A|C} = p_{\rm B|A} = p_{\rm C|CB} = 1/4$  (blau markiert).


Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind:

$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_1 = {\rm log_2}\hspace{0.1cm} 3 \hspace{0.15cm} \underline {= 1.585 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(3)  Für die zweite Entropienäherung benötigt man  $3^2 = 9$  Verbundwahrscheinlichkeiten.

  • Mit dem Ergebnis aus  (2)  erhält man hierfür:
$$p_{\rm AA} = p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12 \hspace{0.05cm},\hspace{0.5cm} p_{\rm AB} = p_{\rm BC}=p_{\rm CA}=1/6$$
$$\Rightarrow \hspace{0.2cm} H_2 = \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm ld}\hspace{0.1cm} 12 + 3 \cdot \frac{1}{6} \cdot {\rm log_2}\hspace{0.1cm} 6 \right ] = \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 4 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 2 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 = \frac{3}{4} + \frac{{\rm log_2}\hspace{0.1cm} 3}{2} \hspace{0.15cm} \underline {= 1.5425 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(4)  Aufgrund der Markoveigenschaft der Quelle gilt

$$H = 2 \cdot H_2 - H_1 = \big [ {3}/{2} + {\rm log_2}\hspace{0.1cm} 3 \big ] - {\rm log_2}\hspace{0.1cm} 3\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
  • Zum gleichen Ergebnis würde man nach folgender Rechnung kommen:
$$H= p_{\rm AA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm AB} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + ... \hspace{0.1cm}= 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 4 + 3 \cdot \frac{1}{16} \cdot {\rm log_2}\hspace{0.1cm} 2 \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


Übergangsdiagramm für  $p = 1/4$,  $q = 0$

(5)  Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität  $p_{\rm B} = 0$  gelten wird, da  $\rm B$  höchstens zum Startzeitpunkt einmal auftreten kann.

  • Es liegt also eine binäre Markovkette mit den Symbolen  $\rm A$  und  $\rm C$  vor.
  • Die Symbolwahrscheinlichkeiten ergeben sich demzufolge zu:
$$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm A} = 1/3 \hspace{0.05cm}, \hspace{0.2cm} p_{\rm C} = 2/3\hspace{0.05cm}. $$
  • Damit erhält man folgende Wahrscheinlichkeiten:
$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} = \hspace{0.1cm}0\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AA} = 0 \hspace{0.05cm},$$
$$ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CA} = p_{\rm C} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3 \hspace{0.05cm},\hspace{0.2cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} )= 1\hspace{0.05cm},$$
$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} =1\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AC} = p_{\rm A} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} = 1/3 \cdot 1 = 1/3 \hspace{0.05cm},\hspace{0.61cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} )= 0\hspace{0.05cm},$$
$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CC} = p_{\rm C} \cdot p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} = 2/3 \cdot 1/2 = 1/3\hspace{0.05cm},\hspace{0.2cm}{\rm log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} )= 1 $$
$$\Rightarrow \hspace{0.25cm} H = p_{\rm AA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} +p_{\rm CA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C}}+ p_{\rm AC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm CC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}= 0 + 1/3 \cdot 1 + 1/3 \cdot 0 + 1/3 \cdot 1 \hspace{0.15cm} \underline {= 0.667 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$