Aufgaben:Aufgabe 1.5Z: Symmetrische Markovquelle: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(10 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_ID2252__Inf_Z_1_5.png|right|]]
+
[[Datei:Inf_Z_1_5_vers2.png|right|frame|Binäres Markovdiagramm]]
:In der Aufgabe A1.5 wurde eine binäre Markovquelle behandelt, bei der die Übergangswahrscheinlichkeiten von <b>A</b> nach <b>B</b> sowie von <b>B</b> nach <b>A</b> unterschiedlich waren. In dieser Aufgabe soll nun gelten:
+
In der&nbsp; [[Aufgaben:1.5_Binäre_Markovquelle|Aufgabe 1.5]]&nbsp; wurde eine binäre Markovquelle behandelt, bei der die Übergangswahrscheinlichkeiten von&nbsp; $\rm A$&nbsp; nach&nbsp; $\rm B$&nbsp; und von&nbsp; $\rm B$&nbsp; nach&nbsp; $\rm A$&nbsp; unterschiedlich waren.  
 +
 
 +
In dieser Aufgabe soll nun gelten:
 
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q \hspace{0.8cm} ( 0 \le q \le 1)
 
:$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q \hspace{0.8cm} ( 0 \le q \le 1)
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
:Alle in der Aufgabe A1.5 angegebenen Gleichungen gelten auch hier:
 
  
:* <b>Entropie:</b>
+
Alle in der Aufgabe 1.5 angegebenen Gleichungen gelten auch hier:
:$$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}} +  p_{\rm BA}  \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm BB}  \cdot  {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
+
 
  \hspace{0.05cm},$$
+
* <b>Entropie:</b>
 +
:$$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}.$$
  
:* <b>Erste Entropienäherung</b>:
+
* <b>Erste Entropienäherung</b>:
:$$H_{\rm 1}  =  p_{\rm A} \cdot {\rm ld}\hspace{0.1cm} \frac{1}{p_{\rm A}} + p_{\rm B} \cdot {\rm ld}\hspace{0.1cm} \frac{1}{p_{\rm B}}  
+
:$$H_{\rm 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.05cm},$$
+
  \hspace{0.05cm}.$$
  
:* <b><i>k</i>&ndash;te Entropienäherung</b> (<i>k</i> = 2, 3, ...):
+
* <b><i>k</i>&ndash;te Entropienäherung</b> $(k = 2, 3, \ \text{...})$:
:$$H_k =  \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H]  
+
:$$H_k =  {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big]  
 
  \hspace{0.05cm},\hspace{0.5cm}H  =  \lim_{k \rightarrow \infty } H_k  \hspace{0.05cm}.$$
 
  \hspace{0.05cm},\hspace{0.5cm}H  =  \lim_{k \rightarrow \infty } H_k  \hspace{0.05cm}.$$
  
:<b>Hinweis:</b> Die Aufgabe bezieht sich auf Kapitel 1.2, Seite 5c. Bei allen Entropien ist die Pseudoeinheit &bdquo;bit/Symbol&rdquo; hinzuzufügen.
+
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''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#Bin.C3.A4rquellen_mit_Markoveigenschaften|Binärquellen mit Markoveigenschaften]].
 +
*Bei allen Entropien ist die Pseudoeinheit &bdquo;bit/Symbol&rdquo; hinzuzufügen.
 +
 +
 
  
  
Zeile 27: Zeile 41:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Berechnen Sie die Symbolwahrscheinlichkeiten.
+
{Berechnen Sie die Symbolwahrscheinlichkeiten für die Übergangswahrscheinlichkeit&nbsp; $q = 1/4$.
 
|type="{}"}
 
|type="{}"}
$q = 1/4:\ \ p_A$ = { 0.5 3% }
+
$p_{\rm A} \ = \ $ { 0.5 1% }
$p_B$ = { 0.5 3% }
+
$p_{\rm B} \ = \ $ { 0.5 1% }
  
  
{Berechnen Sie die Quellenentropie <i>H</i>. Welches Ergebnis liefert <i>q</i> = 1/4?
+
{Berechnen Sie die Quellenentropie&nbsp; $H$&nbsp; für&nbsp; $q = 1/4$.
 
|type="{}"}
 
|type="{}"}
$q = 1/4:\ \ H$ = { 0.5 3% } $bit/Symbol$
+
$H \ =$ { 0.811 3% } $\ \rm bit/Symbol$
  
  
{Welche Entropienäherungen erhält man für <i>q</i> = 1/4?
+
{Welche Entropienäherungen erhält man für&nbsp; $q = 1/4$?
 
|type="{}"}
 
|type="{}"}
$q = 1/4:\ \ H_1$ = { 1 3% } $bit/Symbol$
+
$H_1 \ = \ $ { 1 1% } $\ \rm bit/Symbol$
$H_2$ = { 0.906 3% } $bit/Symbol$
+
$H_2 \ = \ $ { 0.906 1% } $\ \rm bit/Symbol$
$H_3$ = { 0.874 3% } $bit/Symbol$
+
$H_3 \ = \ $ { 0.874 1% } $\ \rm bit/Symbol$
  
  
{Bestimmen Sie <i>q</i> derart, dass <i>H</i> maximal wird. Interpretation.
+
{Bestimmen Sie&nbsp; $q$&nbsp; derart, dass&nbsp; $H$&nbsp; maximal wird. Interpretation.
 
|type="{}"}
 
|type="{}"}
$H \rightarrow Maximum:\ \ q$ = { 0.5 3% }
+
$q \ = \ $ { 0.5 3% }
  
  
{Welche Symbolfolgen sind mit <i>q</i> = 0 möglich?
+
{Welche Symbolfolgen sind mit&nbsp; $q = 0$&nbsp; möglich?
 
|type="[]"}
 
|type="[]"}
+ AAAAAA ...
+
+ $\rm AAAAAA$ ...  
+ BBBBBB ...
+
+ $\rm BBBBBB$ ...
- ABABAB ...
+
- $\rm ABABAB$ ...
  
  
{Welche Symbolfolgen sind mit <i>q</i> = 1 möglich?
+
{Welche Symbolfolgen sind mit&nbsp; $q = 1$&nbsp; möglich?
 
|type="[]"}
 
|type="[]"}
- AAAAAA ...
+
- $\rm AAAAAA$ ...  
- BBBBBB ...
+
- $\rm BBBBBB$ ...
+ ABABAB ...
+
+ $\rm ABABAB$ ...
  
  
Zeile 69: Zeile 83:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Bei einer stationären binären Markovquelle erster Ordnung gilt:
+
'''(1)'''&nbsp; Bei einer stationären binären Markovquelle erster Ordnung gilt:
 
:$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} + p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B}
 
:$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} + p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B}
 
  = (1-q) \cdot p_{\rm A} + q \cdot p_{\rm B}$$
 
  = (1-q) \cdot p_{\rm A} + q \cdot p_{\rm B}$$
:$$q \cdot p_{\rm A} = q \cdot p_{\rm B} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}p_{\rm A} = p_{\rm B}\hspace{0.15cm} \underline {= 0.5}  
+
:$$\Rightarrow \hspace{0.3cm}q \cdot p_{\rm A} = q \cdot p_{\rm B} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}p_{\rm A} = p_{\rm B}\hspace{0.15cm} \underline {= 0.5}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>2.</b>&nbsp;&nbsp;Zur Berechnung von <i>H</i> benötigt man alle vier Verbundwahrscheinlichkeiten:
+
 
:$$p_{\rm AA} \hspace{0.1cm} =  \hspace{0.1cm}  p_{\rm A} \cdot  p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot(1-q) = p_{\rm BB}\hspace{0.05cm},\\
+
 
 +
'''(2)'''&nbsp; Zur Berechnung der Entropie&nbsp; $H$&nbsp; benötigt man alle vier Verbundwahrscheinlichkeiten:
 +
:$$p_{\rm AA} \hspace{0.1cm} =  \hspace{0.1cm}  p_{\rm A} \cdot  p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot(1-q) = p_{\rm BB}\hspace{0.05cm},\hspace{1cm}
 
  p_{\rm AB} \hspace{0.1cm} =  \hspace{0.1cm}  p_{\rm A} \cdot  p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot q = p_{\rm BA}\hspace{0.05cm}.$$
 
  p_{\rm AB} \hspace{0.1cm} =  \hspace{0.1cm}  p_{\rm A} \cdot  p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot q = p_{\rm BA}\hspace{0.05cm}.$$
:Setzt man diese Werte in die gegebene Entropie&ndash;Gleichung ein, so erhält man
+
*Setzt man diese Werte in die gegebene Entropie&ndash;Gleichung ein, so erhält man
:$$H  \hspace{0.1cm} = \hspace{0.1cm}  2 \cdot \frac{1}{2} \cdot(1-q) \cdot  
+
:$$H  = 2 \cdot \frac{1}{2} \cdot(1-q) \cdot  
 
{\rm log}_2\hspace{0.1cm} \frac{1}{1-q} + 2 \cdot \frac{1}{2} \cdot q \cdot  
 
{\rm log}_2\hspace{0.1cm} \frac{1}{1-q} + 2 \cdot \frac{1}{2} \cdot q \cdot  
{\rm log}_2\hspace{0.1cm} \frac{1}{q} = \\
+
{\rm log}_2\hspace{0.1cm} \frac{1}{q} =  q \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{q} + (1-q) \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{1-q} = H_{\rm bin}(q) \hspace{0.05cm}.$$
\hspace{0.1cm} =  \hspace{0.1cm}  q \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{q} + (1-q) \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{1-q} = H_{\rm bin}(q) \hspace{0.05cm}.$$
+
*Der gesuchte Zahlenwert ist&nbsp; $H = H_{\rm bin} (0.25) \hspace{0.15cm}\underline{= 0.811 \, \rm bit/Symbol}$.
:Der gesuchte Zahlenwert ist <i>H</i> = <i>H</i><sub>bin</sub> (0.25) <u>= 0.811 bit/Symbol</u>.
+
 
 +
 
  
:<b>3.</b>&nbsp;&nbsp;Bei gleichwahrscheinlichen Binärsymbolen ist <i>H</i><sub>1</sub> <u>= 1 bit/Symbol</u>. Mit der für Markovquellen gültigen Gleichung gilt weiter:
+
'''(3)'''&nbsp; Bei gleichwahrscheinlichen Binärsymbolen ist&nbsp; $H_1 \hspace{0.15cm}\underline{= 1 \, \rm bit/Symbol}$.&nbsp;
:$$H_2 \hspace{0.1cm} =  \hspace{0.1cm}  \frac{1}{2} \cdot [ H_1 +  H] \hspace{0.15cm} \underline {= 0.906 \,{\rm bit/Symbol}}  
+
*Mit der für Markovquellen gültigen Gleichung gilt weiter:
  \hspace{0.05cm},\\
+
:$$H_2 \hspace{0.1cm} =  \hspace{0.1cm}  {1}/{2} \cdot \big[ H_1 +  H \big] \hspace{0.15cm} \underline {= 0.906 \,{\rm bit/Symbol}}  
H_3 \hspace{0.1cm} =  \hspace{0.1cm} \frac{1}{3} \cdot [ H_1 + 2  H] \hspace{0.15cm} \underline {= 0.874 \,{\rm bit/Symbol}}  
+
  \hspace{0.05cm},$$
 +
:$$ H_3 \hspace{0.1cm} =  \hspace{0.1cm} {1}/{3} \cdot \big[ H_1 + 2  H \big] \hspace{0.15cm} \underline {= 0.874 \,{\rm bit/Symbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>4.</b>&nbsp;&nbsp;Das Maximum der binären Entropiefunktion ergibt sich für <i>q</i> <u>= 0.5</u>. Damit beträgt die maximale Entropie <i>H</i> = 1 bit/Symbol. Man erkennt aus der Beziehung <i>H</i> = <i>H</i><sub>1</sub> und aus dem vorne abgebildeten Übergangsdiagramm, dass <i>q</i> = 0.5 statistisch unabhängige Symbole zur Folge hat:
+
 
 +
 
 +
'''(4)'''&nbsp; Das Maximum der binären Entropiefunktion ergibt sich für&nbsp; $q\hspace{0.15cm}\underline{= 0.5}$.
 +
*Damit beträgt die maximale Entropie&nbsp; $H = 1 \, \rm bit/Symbol$.  
 +
*Man erkennt aus der Beziehung&nbsp; $H = H_1$&nbsp; und aus dem vorne abgebildeten Übergangsdiagramm, dass&nbsp; $q = 0.5$&nbsp; statistisch unabhängige Symbole zur Folge hat:
 
:$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = 0.5
 
:$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = 0.5
 
  \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}= 0.5
 
  \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}= 0.5
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>5.</b>&nbsp;&nbsp;Richtig sind die <u>Lösungsvorschläge 1 und 2</u>. Die Symbolfolge ergibt sich entweder zu <b>AAAAAA</b>... oder zu <b>BBBBBB</b>..., je nachdem, welches Symbol als Startwert vorgegeben wurde. Die Entropie einer solchen Quelle ist <i>H</i> = <i>H</i><sub>bin</sub>(0) = 0.
 
  
:<b>6.</b>&nbsp;&nbsp;Nun kann weder <b>A</b> direkt auf <b>A</b> noch <b>B</b> direkt auf <b>B</b> folgen. Es ergibt sich eine alternierende Folge, je nach Startwert die Folge <b>ABABAB</b>... oder <b>BABABA</b>... &#8658;&nbsp;&nbsp; <u>Lösungsvorschlag 3</u>. Diese Quelle hat in beiden Fällen ebenfalls die Entropie <i>H</i> = 0 = <i>H</i><sub>bin</sub>(1).
+
 
 +
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2</u>:
 +
*Die Symbolfolge ergibt sich entweder zu &nbsp;$\rm AAAAAA$ ... &nbsp;oder zu &nbsp;$\rm BBBBBB$ ... , je nachdem, welches Symbol als Startwert vorgegeben wurde.
 +
*Die Entropie einer solchen Quelle ist stets &nbsp;$H = H_{\rm bin}(0) = 0$.
 +
 
 +
 
 +
 
 +
 
 +
'''(6)'''&nbsp; Richtig ist nur der <u>Lösungsvorschlag 3</u>:
 +
*Nun kann weder&nbsp; $\rm A$&nbsp; direkt auf&nbsp; $\rm A$&nbsp; noch&nbsp; $\rm B$&nbsp; direkt auf&nbsp; $\rm B$&nbsp; folgen.  
 +
*Es ergibt sich stets eine alternierende Folge, je nach Startwert die Folge &nbsp;$\rm ABABAB$ ... &nbsp;oder&nbsp; $\rm BABABA$... .  
 +
*Diese Quelle hat in beiden Fällen ebenfalls die Entropie&nbsp; $H = H_{\rm bin}(1) = 0$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 17. Januar 2020, 16:19 Uhr

Binäres Markovdiagramm

In der  Aufgabe 1.5  wurde eine binäre Markovquelle behandelt, bei der die Übergangswahrscheinlichkeiten von  $\rm A$  nach  $\rm B$  und von  $\rm B$  nach  $\rm A$  unterschiedlich waren.

In dieser Aufgabe soll nun gelten:

$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q \hspace{0.8cm} ( 0 \le q \le 1) \hspace{0.05cm}.$$

Alle in der Aufgabe 1.5 angegebenen Gleichungen gelten auch hier:

  • Entropie:
$$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}.$$
  • Erste Entropienäherung:
$$H_{\rm 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.05cm}.$$
  • k–te Entropienäherung $(k = 2, 3, \ \text{...})$:
$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big] \hspace{0.05cm},\hspace{0.5cm}H = \lim_{k \rightarrow \infty } H_k \hspace{0.05cm}.$$




Hinweise:



Fragebogen

1

Berechnen Sie die Symbolwahrscheinlichkeiten für die Übergangswahrscheinlichkeit  $q = 1/4$.

$p_{\rm A} \ = \ $

$p_{\rm B} \ = \ $

2

Berechnen Sie die Quellenentropie  $H$  für  $q = 1/4$.

$H \ =$

$\ \rm bit/Symbol$

3

Welche Entropienäherungen erhält man für  $q = 1/4$?

$H_1 \ = \ $

$\ \rm bit/Symbol$
$H_2 \ = \ $

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

$\ \rm bit/Symbol$

4

Bestimmen Sie  $q$  derart, dass  $H$  maximal wird. Interpretation.

$q \ = \ $

5

Welche Symbolfolgen sind mit  $q = 0$  möglich?

$\rm AAAAAA$ ...
$\rm BBBBBB$ ...
$\rm ABABAB$ ...

6

Welche Symbolfolgen sind mit  $q = 1$  möglich?

$\rm AAAAAA$ ...
$\rm BBBBBB$ ...
$\rm ABABAB$ ...


Musterlösung

(1)  Bei einer stationären binären Markovquelle erster Ordnung gilt:

$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot p_{\rm A} + p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B} = (1-q) \cdot p_{\rm A} + q \cdot p_{\rm B}$$
$$\Rightarrow \hspace{0.3cm}q \cdot p_{\rm A} = q \cdot p_{\rm B} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}p_{\rm A} = p_{\rm B}\hspace{0.15cm} \underline {= 0.5} \hspace{0.05cm}.$$


(2)  Zur Berechnung der Entropie  $H$  benötigt man alle vier Verbundwahrscheinlichkeiten:

$$p_{\rm AA} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot(1-q) = p_{\rm BB}\hspace{0.05cm},\hspace{1cm} p_{\rm AB} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = 1/2 \cdot q = p_{\rm BA}\hspace{0.05cm}.$$
  • Setzt man diese Werte in die gegebene Entropie–Gleichung ein, so erhält man
$$H = 2 \cdot \frac{1}{2} \cdot(1-q) \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{1-q} + 2 \cdot \frac{1}{2} \cdot q \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{q} = q \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{q} + (1-q) \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{1-q} = H_{\rm bin}(q) \hspace{0.05cm}.$$
  • Der gesuchte Zahlenwert ist  $H = H_{\rm bin} (0.25) \hspace{0.15cm}\underline{= 0.811 \, \rm bit/Symbol}$.


(3)  Bei gleichwahrscheinlichen Binärsymbolen ist  $H_1 \hspace{0.15cm}\underline{= 1 \, \rm bit/Symbol}$. 

  • Mit der für Markovquellen gültigen Gleichung gilt weiter:
$$H_2 \hspace{0.1cm} = \hspace{0.1cm} {1}/{2} \cdot \big[ H_1 + H \big] \hspace{0.15cm} \underline {= 0.906 \,{\rm bit/Symbol}} \hspace{0.05cm},$$
$$ H_3 \hspace{0.1cm} = \hspace{0.1cm} {1}/{3} \cdot \big[ H_1 + 2 H \big] \hspace{0.15cm} \underline {= 0.874 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$


(4)  Das Maximum der binären Entropiefunktion ergibt sich für  $q\hspace{0.15cm}\underline{= 0.5}$.

  • Damit beträgt die maximale Entropie  $H = 1 \, \rm bit/Symbol$.
  • Man erkennt aus der Beziehung  $H = H_1$  und aus dem vorne abgebildeten Übergangsdiagramm, dass  $q = 0.5$  statistisch unabhängige Symbole zur Folge hat:
$$p_{\rm A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = 0.5 \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}= 0.5 \hspace{0.05cm}.$$


(5)  Richtig sind die Lösungsvorschläge 1 und 2:

  • Die Symbolfolge ergibt sich entweder zu  $\rm AAAAAA$ ...  oder zu  $\rm BBBBBB$ ... , je nachdem, welches Symbol als Startwert vorgegeben wurde.
  • Die Entropie einer solchen Quelle ist stets  $H = H_{\rm bin}(0) = 0$.



(6)  Richtig ist nur der Lösungsvorschlag 3:

  • Nun kann weder  $\rm A$  direkt auf  $\rm A$  noch  $\rm B$  direkt auf  $\rm B$  folgen.
  • Es ergibt sich stets eine alternierende Folge, je nach Startwert die Folge  $\rm ABABAB$ ...  oder  $\rm BABABA$... .
  • Diese Quelle hat in beiden Fällen ebenfalls die Entropie  $H = H_{\rm bin}(1) = 0$.