Aufgaben:Aufgabe 1.5: Binäre Markovquelle: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(4 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2250__Inf_A_1_5.png|right|Betrachtetes binäres Markovdiagramm]]
+
[[Datei:P_ID2250__Inf_A_1_5.png|right|frame|Binäres Markovdiagramm]]
Die [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]] hat gezeigt, dass die Berechnung der Entropie bei einer gedächtnisbehafteten Quelle sehr aufwändig sein kann. Man muss dann zunächst (sehr viele) Entropienäherungen $H_k$ für $k$–Tupel berechnen und kann erst  dann mit dem Grenzübergang $k \to \infty$ die Quellenentropie ermitteln:
+
Die  [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]]  hat gezeigt, dass die Berechnung der Entropie bei einer gedächtnisbehafteten Quelle sehr aufwändig sein kann.  Man muss dann zunächst (sehr viele) Entropienäherungen  $H_k$  für  $k$–Tupel berechnen und kann erst  dann die Quellenentropie mit dem Grenzübergang  $k \to \infty$  ermitteln:
 
:$$H  =  \lim_{k \rightarrow \infty } H_k  \hspace{0.05cm}.$$
 
:$$H  =  \lim_{k \rightarrow \infty } H_k  \hspace{0.05cm}.$$
Oft tendiert dabei $H_k$ nur sehr langsam gegen den Grenzwert $H$.
+
Oft tendiert dabei  $H_k$  nur sehr langsam gegen den Grenzwert  $H$.
  
Der Rechengang wird drastisch reduziert, wenn die Nachrichtenquelle Markoveigenschaften besitzt. Die Grafik zeigt das Übergangsdiagramm für eine binäre Markovquelle mit den zwei Zuständen (Symbolen) $\rm A$ und $\rm B$.  
+
Der Rechengang wird drastisch reduziert, wenn die Nachrichtenquelle Markoveigenschaften besitzt.  Die Grafik zeigt das Übergangsdiagramm für eine binäre Markovquelle mit den zwei Zuständen (Symbolen)  $\rm A$  und  $\rm B$.  
*Dieses ist durch die beiden bedingten Wahrscheinlichkeiten $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p$ und $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q$ eindeutig bestimmt.  
+
*Dieses ist durch die beiden bedingten Wahrscheinlichkeiten  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p$  und  $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q$  eindeutig bestimmt.  
*Die bedingten Wahrscheinlichkeiten $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$ und $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}$ sowie die Symbolwahrscheinlichkeiten $p_{\rm A}$ und $p_{\rm B}$ lassen sich daraus ermitteln.
+
*Die anderen  bedingten Wahrscheinlichkeiten  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$  und  $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}$  sowie die (unbedingten) Symbolwahrscheinlichkeiten  $p_{\rm A}$   und  $p_{\rm B}$  lassen sich daraus ermitteln.
  
  
Die Entropie der binären Markovkette (mit der Einheit „bit/Symbol”) lautet dann:
+
Die Entropie der binären Markovkette  (mit der Einheit „bit/Symbol”)  lautet dann:
 
:$$H = H_{\rm M} =  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}} +  p_{\rm BA}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB}  \cdot   
 
:$$H = H_{\rm M} =  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}} +  p_{\rm BA}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB}  \cdot   
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Bei dieser Gleichung ist zu beachten, dass im Argument des <i>Logarithmus dualis</i> jeweils die [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Bedingte_Wahrscheinlichkeit|bedingten Wahrscheinlichkeiten]] $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$, $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$, ... einzusetzen sind, während für die Gewichtung die [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Verbundwahrscheinlichkeiten]] $p_{\rm AA}$, $p_{\rm AB}$, ... zu verwenden sind.
+
Bei dieser Gleichung ist zu beachten, dass im Argument des <i>Logarithmus dualis</i>&nbsp; jeweils die&nbsp; [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Bedingte_Wahrscheinlichkeit|bedingten Wahrscheinlichkeiten]]&nbsp; $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$,&nbsp; $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$, ... &nbsp; einzusetzen sind, während für die Gewichtung die&nbsp; [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Verbundwahrscheinlichkeiten]]&nbsp; $p_{\rm AA}$,&nbsp; $p_{\rm AB}$, ... &nbsp; zu verwenden sind.
  
 
Mit der Entropienäherung erster Ordnung,
 
Mit der Entropienäherung erster Ordnung,
Zeile 23: Zeile 23:
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}}
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}}
 
  \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})\hspace{0.05cm},$$
 
  \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})\hspace{0.05cm},$$
sowie der oben angegebenen (tatsächlichen) Entropie $H = H_{\rm M}$ lassen sich bei einer Markovquelle auch alle weiteren Entropienäherungen ($k = 2,, 3$, ...) direkt berechnen:
+
sowie der oben angegebenen (tatsächlichen) Entropie&nbsp; $H = H_{\rm M}$&nbsp; lassen sich bei einer Markovquelle auch alle weiteren Entropienäherungen&nbsp; $(k = 2,, 3, \text{...})$&nbsp; direkt angeben:
:$$H_k =  \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}]  
+
:$$H_k =  \frac{1}{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M} \big ]  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
 +
 +
 +
 +
 +
 +
  
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
*Bezug genommen wird insbesondere auch auf die beiden Seiten  [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Schnittmenge]] und [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Bedingte_Wahrscheinlichkeit|Bedingte Wahrscheinlichkeit]].
+
*Bezug genommen wird insbesondere auch auf die beiden Seiten&nbsp;   [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Schnittmenge]]&nbsp; und&nbsp; [[Stochastische_Signaltheorie/Statistische_Abhängigkeit_und_Unabhängigkeit#Bedingte_Wahrscheinlichkeit|Bedingte Wahrscheinlichkeit]].
*Mit Ausnahme der Teilaufgabe (6) gelte stets  $p = 1/4$ und $q = 1/2$.
+
*Mit Ausnahme der Teilaufgabe&nbsp; '''(6)'''&nbsp; gelte stets&nbsp; $p = 1/4$ &nbsp;und&nbsp; $q = 1/2$.
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
 
*Für die (ergodischen) Symbolwahrscheinlichkeiten einer Markovkette erster Ordnung gilt:
 
*Für die (ergodischen) Symbolwahrscheinlichkeiten einer Markovkette erster Ordnung gilt:
 
:$$ p_{\rm A}  = \frac {p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}
 
:$$ p_{\rm A}  = \frac {p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}
Zeile 38: Zeile 44:
 
p_{\rm B}  = \frac {p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 
p_{\rm B}  = \frac {p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 
{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}  \hspace{0.05cm}.$$
 
{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}  \hspace{0.05cm}.$$
 +
 +
  
  
Zeile 43: Zeile 51:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Geben Sie die Übergangswahrscheinlichkeiten für $p = 1/4$ und $q = 1/2$ an.
+
{Geben Sie die Übergangswahrscheinlichkeiten für &nbsp;$p = 1/4$ &nbsp;und&nbsp; $q = 1/2$ an.
 
|type="{}"}
 
|type="{}"}
$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \ = $  { 0.5 3% }
+
$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \ = \ $  { 0.5 3% }
$p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \ = $ { 0.75 3% }
+
$p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \ = $ { 0.75 3% }
  
  
{Wie groß sind die Symbolwahrscheinlichkeiten? Es gelte weiterhin $p = 1/4$ und $q = 1/2$.  
+
{Wie groß sind die (unbedingten) Symbolwahrscheinlichkeiten?&nbsp; Es gelte weiterhin &nbsp;$p = 1/4$ &nbsp;und&nbsp; $q = 1/2$.  
 
|type="{}"}
 
|type="{}"}
$p_{\rm A} \ = $  { 0.333 3% }
+
$p_{\rm A} \ = $  { 0.333 3% }
$p_{\rm B} \ = ${ 0.667 3% }
+
$p_{\rm B} \ = ${ 0.667 3% }
  
  
 
{Geben Sie die dazugehörige Entropienäherung erster Ordnung an.
 
{Geben Sie die dazugehörige Entropienäherung erster Ordnung an.
 
|type="{}"}
 
|type="{}"}
$H_1  \ = $ { 0.918 1% } $\ \rm bit/Symbol$
+
$H_1  \ = \ $ { 0.918 1% } $\ \rm bit/Symbol$
  
  
{Welche Entropie $H = H_{\rm M}$ besitzt diese Markovquelle mit $p = 1/4$ und $q = 1/2$?
+
{Welche Entropie&nbsp; $H = H_{\rm M}$&nbsp; besitzt diese Markovquelle mit &nbsp;$p = 1/4$ &nbsp;und&nbsp; $q = 1/2$?
 
|type="{}"}
 
|type="{}"}
$H \  =$ { 0.875 1% } $\ \rm bit/Symbol$
+
$H \  = \ $ { 0.875 1% } $\ \rm bit/Symbol$
  
  
{Welche Näherungen $H_k$ ergeben sich aufgrund der Markoveigenschaften?
+
{Welche Entropienäherungen&nbsp; $H_k$&nbsp; ergeben sich aufgrund der Markoveigenschaften?
 
|type="{}"}
 
|type="{}"}
$H_2 \  =$ { 0.897 0.5% } $\ \rm bit/Symbol$
+
$H_2 \  = \ $ { 0.897 0.5% } $\ \rm bit/Symbol$
$H_3 \  =$ { 0.889 0.5% } $\ \rm bit/Symbol$
+
$H_3 \  = \ $ { 0.889 0.5% } $\ \rm bit/Symbol$
$H_4 \  =$ { 0.886 0.5% } $\ \rm bit/Symbol$
+
$H_4 \  = \ $ { 0.886 0.5% } $\ \rm bit/Symbol$
  
  
{Welche Entropie $H = H_{\rm M}$ besitzt die Markovquelle mit $p = 1/4$ und $q = 3/4$?
+
{Welche Entropie&nbsp; $H = H_{\rm M}$&nbsp; besitzt die Markovquelle mit &nbsp;$p = 1/4$ &nbsp;und&nbsp; $q = 3/4$?
 
|type="{}"}
 
|type="{}"}
$H \  =$  { 0.811 1% } $\ \rm bit/Symbol$
+
$H \  = \ $  { 0.811 1% } $\ \rm bit/Symbol$
  
  
Zeile 82: Zeile 90:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[Datei:Inf_A_1_5a_vers2.png|right|Markovdiagramm für die Teilaufgaben (1), ... , (5)]]
+
[[Datei:Inf_A_1_5a_vers2.png|right|frame|Markovdiagramm für die Teilaufgaben&nbsp; '''(1)''', ... ,&nbsp; '''(5)''']]
Nach $\rm A$ sind $\rm A$ und $\rm B$ gleichwahrscheinlich. Nach $\rm B$  tritt $\rm B$ sehr viel häufiger als $\rm A$ auf. Für die Übergangswahrscheinlichkeiten gilt:
+
Nach&nbsp; $\rm A$&nbsp; sind&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$&nbsp; gleichwahrscheinlich.&nbsp; Nach&nbsp; $\rm B$&nbsp; tritt&nbsp; $\rm B$&nbsp; sehr viel häufiger als&nbsp; $\rm A$&nbsp; auf.&nbsp; Für die Übergangswahrscheinlichkeiten gilt:
 
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} =  \hspace{0.1cm} 1 - p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}= 1 - q \hspace{0.15cm} \underline {= 0.5} \hspace{0.05cm},$$
 
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} =  \hspace{0.1cm} 1 - p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}= 1 - q \hspace{0.15cm} \underline {= 0.5} \hspace{0.05cm},$$
 
:$$ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.1cm} =  \hspace{0.1cm} 1 - p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}= 1 - p \hspace{0.15cm} \underline {= 0.75} \hspace{0.05cm}.$$
 
:$$ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.1cm} =  \hspace{0.1cm} 1 - p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}= 1 - p \hspace{0.15cm} \underline {= 0.75} \hspace{0.05cm}.$$
 +
 +
  
 
'''(2)'''&nbsp; Entsprechend den angegebenen Gleichungen gilt:
 
'''(2)'''&nbsp; Entsprechend den angegebenen Gleichungen gilt:
 
:$$p_{\rm A}= \frac{p}{p+q} = \frac{0.25}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.333} \hspace{0.05cm}, \hspace{0.5cm}
 
:$$p_{\rm A}= \frac{p}{p+q} = \frac{0.25}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.333} \hspace{0.05cm}, \hspace{0.5cm}
 
p_{\rm B} = \frac{q}{p+q} = \frac{0.50}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.667}  \hspace{0.05cm}.$$
 
p_{\rm B} = \frac{q}{p+q} = \frac{0.50}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.667}  \hspace{0.05cm}.$$
 +
 +
  
 
'''(3)'''&nbsp; Mit den in der letzten Teilaufgabe berechneten Wahrscheinlichkeiten gilt:
 
'''(3)'''&nbsp; Mit den in der letzten Teilaufgabe berechneten Wahrscheinlichkeiten gilt:
Zeile 96: Zeile 108:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(4)'''&nbsp; Die Entropie der Markovquelle lautet entsprechend der Angabe
+
 
 +
 
 +
'''(4)'''&nbsp; Die Entropie der Markovquelle lautet entsprechend der Angabe:
 
:$$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}} +  p_{\rm BA}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB}  \cdot   
 
:$$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}} +  p_{\rm BA}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB}  \cdot   
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 
{\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Für die Verbundwahrscheinlichkeiten gilt:
+
*Für die Verbundwahrscheinlichkeiten gilt:
 
:$$p_{\rm AA} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} = (1-q) \cdot \frac{p}{p+q} =
 
:$$p_{\rm AA} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} = (1-q) \cdot \frac{p}{p+q} =
 
  \frac{1/2 \cdot 1/4}{3/4} =  {1}/{6} \hspace{0.05cm},$$
 
  \frac{1/2 \cdot 1/4}{3/4} =  {1}/{6} \hspace{0.05cm},$$
Zeile 114: Zeile 128:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(5)'''&nbsp; Allgemein gilt mit $H_{\rm M} = H$ für die $k$&ndash;Entropienäherung: $H_k =  {1}/{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}]  \hspace{0.05cm}.$ Daraus folgt:
+
 
 +
 
 +
'''(5)'''&nbsp; Allgemein gilt mit&nbsp; $H_{\rm M} = H$&nbsp; für die&nbsp; $k$&ndash;te Entropienäherung: &nbsp;
 +
:$$H_k =  {1}/{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}]  \hspace{0.05cm}.$$
 +
*Daraus folgt:
 
:$$H_2 =  {1}/{2} \cdot [ 0.918 + 1  \cdot 0.875] \hspace{0.15cm} \underline {= 0.897 \,{\rm bit/Symbol}}  
 
:$$H_2 =  {1}/{2} \cdot [ 0.918 + 1  \cdot 0.875] \hspace{0.15cm} \underline {= 0.897 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm},$$
 
  \hspace{0.05cm},$$
Zeile 122: Zeile 140:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
[[Datei:Inf_A_1_5f_vers2.png|right|Markovdiagramm zur Teilaufgaben (6)]]
+
 
'''(6)'''&nbsp; Mit dem neuen Parametersatz ($p = 1/4, q = 3/4$) erhält man für die Symbolwahrscheinlichkeiten: $ p_{\rm A} =  1/4$ und $ p_{\rm B} =  3/4$. Dieser Sonderfall führt demnach zu statistisch unabhängigen Symbolen:
+
[[Datei:Inf_A_1_5f_vers2.png|right|frame|Markovdiagramm zur Teilaufgabe&nbsp; '''(6)''']]
 +
'''(6)'''&nbsp; Mit dem neuen Parametersatz&nbsp; $(p = 1/4, q = 3/4)$&nbsp; erhält man für die Symbolwahrscheinlichkeiten:  
 +
:$$ p_{\rm A} =  1/4, \ p_{\rm B} =  3/4.$$  
 +
 
 +
*Dieser Sonderfall führt demnach zu statistisch unabhängigen Symbolen:
 
:$$ p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
 
:$$ p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
 
  \hspace{0.05cm}, \hspace{0.2cm} p_{\rm B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}
 
  \hspace{0.05cm}, \hspace{0.2cm} p_{\rm B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Damit ist die Entropie $H$ identisch mit der Entropienäherung $H_1$:
+
*Damit ist die Entropie&nbsp; $H$&nbsp; identisch mit der Entropienäherung&nbsp; $H_1$:
 
:$$H = H_{\rm 1}  =  1/4 \cdot {\rm log}_2\hspace{0.01cm} (4) + 3/4 \cdot {\rm log}_2\hspace{0.01cm} (4/3) =
 
:$$H = H_{\rm 1}  =  1/4 \cdot {\rm log}_2\hspace{0.01cm} (4) + 3/4 \cdot {\rm log}_2\hspace{0.01cm} (4/3) =
 
  2 - 0.75 \cdot {\rm log}_2\hspace{0.01cm} (3) \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/Symbol}}  
 
  2 - 0.75 \cdot {\rm log}_2\hspace{0.01cm} (3) \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Die Entropienäherungen $H_2$, $H_3$, $H_4$, ... liefern hier ebenfalls das Ergebnis $0.811 \, \rm bit/Symbol$.
+
*Die Entropienäherungen&nbsp; $H_2$,&nbsp; $H_3$,&nbsp; $H_4$,&nbsp; ... &nbsp;liefern hier ebenfalls das Ergebnis&nbsp; $0.811 \, \rm bit/Symbol$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 17. Januar 2020, 15:59 Uhr

Binäres Markovdiagramm

Die  Aufgabe 1.4  hat gezeigt, dass die Berechnung der Entropie bei einer gedächtnisbehafteten Quelle sehr aufwändig sein kann.  Man muss dann zunächst (sehr viele) Entropienäherungen  $H_k$  für  $k$–Tupel berechnen und kann erst dann die Quellenentropie mit dem Grenzübergang  $k \to \infty$  ermitteln:

$$H = \lim_{k \rightarrow \infty } H_k \hspace{0.05cm}.$$

Oft tendiert dabei  $H_k$  nur sehr langsam gegen den Grenzwert  $H$.

Der Rechengang wird drastisch reduziert, wenn die Nachrichtenquelle Markoveigenschaften besitzt.  Die Grafik zeigt das Übergangsdiagramm für eine binäre Markovquelle mit den zwei Zuständen (Symbolen)  $\rm A$  und  $\rm B$.

  • Dieses ist durch die beiden bedingten Wahrscheinlichkeiten  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p$  und  $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q$  eindeutig bestimmt.
  • Die anderen bedingten Wahrscheinlichkeiten  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$  und  $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}$  sowie die (unbedingten) Symbolwahrscheinlichkeiten  $p_{\rm A}$   und  $p_{\rm B}$  lassen sich daraus ermitteln.


Die Entropie der binären Markovkette  (mit der Einheit „bit/Symbol”)  lautet dann:

$$H = H_{\rm M} = 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}} + p_{\rm BA} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.$$

Bei dieser Gleichung ist zu beachten, dass im Argument des Logarithmus dualis  jeweils die  bedingten Wahrscheinlichkeiten  $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$,  $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$, ...   einzusetzen sind, während für die Gewichtung die  Verbundwahrscheinlichkeiten  $p_{\rm AA}$,  $p_{\rm AB}$, ...   zu verwenden sind.

Mit der Entropienäherung erster Ordnung,

$$H_1 = p_{\rm A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}} + p_{\rm B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})\hspace{0.05cm},$$

sowie der oben angegebenen (tatsächlichen) Entropie  $H = H_{\rm M}$  lassen sich bei einer Markovquelle auch alle weiteren Entropienäherungen  $(k = 2,, 3, \text{...})$  direkt angeben:

$$H_k = \frac{1}{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M} \big ] \hspace{0.05cm}.$$





Hinweise:

  • Für die (ergodischen) Symbolwahrscheinlichkeiten einer Markovkette erster Ordnung gilt:
$$ p_{\rm A} = \frac {p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} { p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}, \hspace{0.3cm} p_{\rm B} = \frac {p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} { p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}.$$



Fragebogen

1

Geben Sie die Übergangswahrscheinlichkeiten für  $p = 1/4$  und  $q = 1/2$ an.

$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \ = \ $

$p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \ = \ $

2

Wie groß sind die (unbedingten) Symbolwahrscheinlichkeiten?  Es gelte weiterhin  $p = 1/4$  und  $q = 1/2$.

$p_{\rm A} \ = \ $

$p_{\rm B} \ = \ $

3

Geben Sie die dazugehörige Entropienäherung erster Ordnung an.

$H_1 \ = \ $

$\ \rm bit/Symbol$

4

Welche Entropie  $H = H_{\rm M}$  besitzt diese Markovquelle mit  $p = 1/4$  und  $q = 1/2$?

$H \ = \ $

$\ \rm bit/Symbol$

5

Welche Entropienäherungen  $H_k$  ergeben sich aufgrund der Markoveigenschaften?

$H_2 \ = \ $

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

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

$\ \rm bit/Symbol$

6

Welche Entropie  $H = H_{\rm M}$  besitzt die Markovquelle mit  $p = 1/4$  und  $q = 3/4$?

$H \ = \ $

$\ \rm bit/Symbol$


Musterlösung

Markovdiagramm für die Teilaufgaben  (1), ... ,  (5)

Nach  $\rm A$  sind  $\rm A$  und  $\rm B$  gleichwahrscheinlich.  Nach  $\rm B$  tritt  $\rm B$  sehr viel häufiger als  $\rm A$  auf.  Für die Übergangswahrscheinlichkeiten gilt:

$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.1cm} = \hspace{0.1cm} 1 - p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}= 1 - q \hspace{0.15cm} \underline {= 0.5} \hspace{0.05cm},$$
$$ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.1cm} = \hspace{0.1cm} 1 - p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}= 1 - p \hspace{0.15cm} \underline {= 0.75} \hspace{0.05cm}.$$


(2)  Entsprechend den angegebenen Gleichungen gilt:

$$p_{\rm A}= \frac{p}{p+q} = \frac{0.25}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.333} \hspace{0.05cm}, \hspace{0.5cm} p_{\rm B} = \frac{q}{p+q} = \frac{0.50}{0.25 + 0.50} \hspace{0.15cm} \underline {= 0.667} \hspace{0.05cm}.$$


(3)  Mit den in der letzten Teilaufgabe berechneten Wahrscheinlichkeiten gilt:

$$H_{\rm 1} = H_{\rm bin}(p_{\rm A}) = 1/3 \cdot {\rm log}_2\hspace{0.01cm} (3) + 2/3 \cdot {\rm log}_2\hspace{0.01cm} (1.5) = 1.585 - 2/3\hspace{0.15cm} \underline {= 0.918 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(4)  Die Entropie der Markovquelle lautet entsprechend der Angabe:

$$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}} + p_{\rm BA} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.$$
  • Für die Verbundwahrscheinlichkeiten gilt:
$$p_{\rm AA} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} = (1-q) \cdot \frac{p}{p+q} = \frac{1/2 \cdot 1/4}{3/4} = {1}/{6} \hspace{0.05cm},$$
$$ p_{\rm AB} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} = q \cdot \frac{p}{p+q} = \frac{1/2 \cdot 1/4}{3/4} = {1}/{6} \hspace{0.05cm},$$
$$ p_{\rm BA} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B} = p \cdot \frac{q}{p+q} = p_{\rm AB} = {1}/{6} \hspace{0.05cm},$$
$$ p_{\rm BB} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B} = (1-p) \cdot \frac{q}{p+q} = \frac{3/4 \cdot 1/2}{3/4} = {1}/{2} $$
$$\Rightarrow\hspace{0.3cm} H = 1/6 \cdot {\rm log}_2\hspace{0.01cm} (2) + 1/6 \cdot {\rm log}_2\hspace{0.01cm} (2) + 1/6 \cdot {\rm log}_2\hspace{0.01cm} (4) + 1/2 \cdot {\rm log}_2\hspace{0.1cm} (4/3) = 10/6 - 1/2 \cdot {\rm log}_2\hspace{0.01cm} (3) \hspace{0.15cm} \underline {= 0.875 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(5)  Allgemein gilt mit  $H_{\rm M} = H$  für die  $k$–te Entropienäherung:  

$$H_k = {1}/{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm}.$$
  • Daraus folgt:
$$H_2 = {1}/{2} \cdot [ 0.918 + 1 \cdot 0.875] \hspace{0.15cm} \underline {= 0.897 \,{\rm bit/Symbol}} \hspace{0.05cm},$$
$$ H_3 = {1}/{3} \cdot [ 0.918 + 2 \cdot 0.875] \hspace{0.15cm} \underline {= 0.889 \,{\rm bit/Symbol}} \hspace{0.05cm},$$
$$ H_4 = {1}/{4} \cdot [ 0.918 + 3 \cdot 0.875] \hspace{0.15cm} \underline {= 0.886 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


Markovdiagramm zur Teilaufgabe  (6)

(6)  Mit dem neuen Parametersatz  $(p = 1/4, q = 3/4)$  erhält man für die Symbolwahrscheinlichkeiten:

$$ p_{\rm A} = 1/4, \ p_{\rm B} = 3/4.$$
  • Dieser Sonderfall führt demnach zu statistisch unabhängigen Symbolen:
$$ p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.05cm}, \hspace{0.2cm} p_{\rm B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.05cm}.$$
  • Damit ist die Entropie  $H$  identisch mit der Entropienäherung  $H_1$:
$$H = H_{\rm 1} = 1/4 \cdot {\rm log}_2\hspace{0.01cm} (4) + 3/4 \cdot {\rm log}_2\hspace{0.01cm} (4/3) = 2 - 0.75 \cdot {\rm log}_2\hspace{0.01cm} (3) \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
  • Die Entropienäherungen  $H_2$,  $H_3$,  $H_4$,  ...  liefern hier ebenfalls das Ergebnis  $0.811 \, \rm bit/Symbol$.