Aufgabe 1.6Z: Ternäre Markovquelle

Aus LNTwww
Wechseln zu:Navigation, Suche

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 so genannten direkten Berechnungsmethode kann die Entropie aber auch wie folgt berechnet werden (insgesamt 9 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}} + \ldots \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}, \hspace{0.1cm}\ldots$$

Hinweise:

  • Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.
  • Bezug genommen wird insbesondere auf die Seite Nichtbinäre Markovquellen.
  • Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen.
  • Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Hinwis: Die Aufgabe gehört zum Themenkomplex von Kapitel 1.2.


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

Hinweis: Aus Platzgründen verwenden wir in der Musterlösung „ld” anstelle von „log2”.
a)  Die maximale Entropie ergibt sich dann, wenn die Symbole A, B und C gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:
  • pA = pA|A = pA|B = pA|C = 1/3,
  • pB = pB|A = pB|B = pB|C = 1/3,
  • pC = pC|A = pC|B = pC|C = 1/3.
Beispielsweise erhält man aus pC|C = 1/3 der Wert p = 1/3. Berücksichtigt man noch pA|A = q · p, so folgt q = 1. Damit ergibt sich die maximale Entropie Hmax = ld 3 = 1.585 bit/Symbol.
P ID2255 Inf Z 1 6b.png
2.  Mit den Parameterwerten p = 1/4 und q = 1 ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:
  • pA|A = pB|B = pC|C = 1/4 (rot markiert),
  • pA|B = pB|C = pC|A = 1/2 (grün markiert),
  • pA|C = pB|A = pC|B = 1/4 (blau markiert).
Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind:
$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3$$
$$\Rightarrow \hspace{0.3cm} H_1 = {\rm ld}\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 die 32 = 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}.$$
4.  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}} \hspace{0.05cm}.$$
Zum gleichen Ergebnis würde man mit 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}} + ... \\ \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.05cm}.$$
P ID2256 Inf Z 1 6e.png
5.  Aus nebenstehendem Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität pB = 0 gelten wird: B kann höchstens zum Starzeitpunkt einmal auftreten. Es liegt also eine binäre Markovkette mit den Symbolen A und C 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 $$
$$\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} \hspace{0.1cm} = \hspace{0.1cm}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 ld}\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} \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},\\ 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 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 $$
$$\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 CC} \cdot {\rm ld}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}= \\ \hspace{0.1cm} = \hspace{0.1cm}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}.$$