Exercise 1.5Z: Symmetrical Markov Source

From LNTwww
Revision as of 11:26, 1 December 2016 by Markus (talk | contribs)

P ID2252 Inf Z 1 5.png
In der Aufgabe A1.5 wurde eine binäre Markovquelle behandelt, bei der die Übergangswahrscheinlichkeiten von A nach B sowie von B nach 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 A1.5 angegebenen Gleichungen gelten auch hier:
  • Entropie:
$$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},$$
  • Erste Entropienäherung:
$$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}} \hspace{0.05cm},$$
  • k–te Entropienäherung (k = 2, 3, ...):
$$H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H] \hspace{0.05cm},\hspace{0.5cm}H = \lim_{k \rightarrow \infty } H_k \hspace{0.05cm}.$$
Hinweis: Die Aufgabe bezieht sich auf Kapitel 1.2, Seite 5c. Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen.


Fragebogen

1

Berechnen Sie die Symbolwahrscheinlichkeiten.

$q = 1/4:\ \ p_A$ =

$p_B$ =

2

Berechnen Sie die Quellenentropie H. Welches Ergebnis liefert q = 1/4?

$q = 1/4:\ \ H$ =

$bit/Symbol$

3

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

$q = 1/4:\ \ H_1$ =

$bit/Symbol$
$H_2$ =

$bit/Symbol$
$H_3$ =

$bit/Symbol$

4

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

$H \rightarrow Maximum:\ \ q$ =

5

Welche Symbolfolgen sind mit q = 0 möglich?

AAAAAA ...
BBBBBB ...
ABABAB ...

6

Welche Symbolfolgen sind mit q = 1 möglich?

AAAAAA ...
BBBBBB ...
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}$$
$$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 von 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},\\ 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 \hspace{0.1cm} = \hspace{0.1cm} 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} = \\ \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 H = Hbin (0.25) = 0.811 bit/Symbol.
3.  Bei gleichwahrscheinlichen Binärsymbolen ist H1 = 1 bit/Symbol. Mit der für Markovquellen gültigen Gleichung gilt weiter:
$$H_2 \hspace{0.1cm} = \hspace{0.1cm} \frac{1}{2} \cdot [ H_1 + H] \hspace{0.15cm} \underline {= 0.906 \,{\rm bit/Symbol}} \hspace{0.05cm},\\ 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}.$$
4.  Das Maximum der binären Entropiefunktion ergibt sich für q = 0.5. Damit beträgt die maximale Entropie H = 1 bit/Symbol. Man erkennt aus der Beziehung H = H1 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 AAAAAA... oder zu BBBBBB..., je nachdem, welches Symbol als Startwert vorgegeben wurde. Die Entropie einer solchen Quelle ist H = Hbin(0) = 0.
6.  Nun kann weder A direkt auf A noch B direkt auf B folgen. Es ergibt sich eine alternierende Folge, je nach Startwert die Folge ABABAB... oder BABABA... ⇒   Lösungsvorschlag 3. Diese Quelle hat in beiden Fällen ebenfalls die Entropie H = 0 = Hbin(1).