Aufgabe 1.6: Nichtbinäre Markovquellen

Aus LNTwww
Wechseln zu:Navigation, Suche

P ID2253 Inf A 1 6.png
Die Grafik zeigt zwei ergodische Markovquellen (MQ):
  • Die Quelle MQ3 ist durch M = 3 Zustände (Symbole) N, M, P gekennzeichnet. Aufgrund der Stationarität haben die Wahrscheinlichkeiten folgende Werte:
$$p_{\rm N} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
  • Bei der Quelle MQ4 ist zusätzlich der Zustand O möglich ⇒ M = 4. Aufgrund der symmetrischen Übergänge sind die stationären Wahrscheinlichkeiten alle gleich:
$$p_{\rm N} = p_{\rm M} = p_{\rm O} = p_{\rm P} = 1/4\hspace{0.05cm}.$$
Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen – und nur bei diesen – durch H1 (Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend) und H2 (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel) gleichzeitig auch
  • die weiteren Entropienäherungen Hk(k = 3, 4, ... ) und
  • die tatsächliche Quellenentropie H
bestimmt sind. Es gelten folgende Bestimmungsgleichungen:
$$H = 2 \cdot H_2 - H_1\hspace{0.05cm},\hspace{0.4cm}H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H] \hspace{0.05cm}.$$
Hinweis: Die Aufgabe gehört zu Kapitel 1.2. Hier finden Sie auch Hinweise zur Berechnung der ersten und zweiten Entropienäherung.


Fragebogen

1

Berechnen Sie die Entropienäherung H1 der Markovquelle MQ3.

$MQ3:\ H_1$ =

$bit/Symbol$

2

Berechnen Sie die Entropienäherung H2 der Markovquelle MQ3.

$MQ3:\ H_2$ =

$bit/Symbol$

3

Wie groß sind die Näherungen H3 und H4 und die Quellenentropie H?

$MQ3:\ H_3$ =

$bit/Symbol$
$H_4$ =

$bit/Symbol$
$H$ =

$bit/Symbol$

4

Berechnen Sie die Entropienäherung H1 der Markovquelle MQ4.

$MQ4:\ H_1$ =

$bit/Symbol$

5

Berechnen Sie die Entropienäherung H2 der Markovquelle MQ4.

$MQ4:\ H_2$ =

$bit/Symbol$

6

Wie groß sind hier die Näherungen H3 und H4 und die Quellenentropie H?

$MQ4:\ H_3$ =

$bit/Symbol$
$H_4$ =

$bit/Symbol$
$H$ =

$bit/Symbol$


Musterlösung

1.  Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben. Daraus lässt sich die Entropienäherung H1 berechnen:
$$H_{\rm 1} = 1/2 \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot 1/4 \cdot {\rm log}_2\hspace{0.1cm}(4 ) \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
2.  Die Verbundwahrscheinlichkeit ist pXY = pX · pY|X, wobei pX die Symbolwahrscheinlichkeit von X angibt und pY|X die bedingte Wahrscheinlichkeit für Y, unter der Voraussetzung, dass vorher X aufgetreten ist. X und Y sind hier Platzhalter für die Symbole N, P, M. Dann gilt:
$$p_{\rm NN} \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot 1/2 = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm PP} = 1/4 \cdot 0 = 0\hspace{0.05cm},\hspace{0.2cm}p_{\rm MM} = 1/4 \cdot 0 = 0 \hspace{0.05cm},\\ p_{\rm NP} \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm PM} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm MN} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\\ p_{\rm NM} \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot 1/4 = 1/8\hspace{0.05cm},\hspace{0.2cm} p_{\rm MP} = 1/4 \cdot 1/2 = 1/8\hspace{0.05cm},\hspace{0.2cm}p_{\rm PN} = 1/4 \cdot 1/2 = 1/8$$
$$\Rightarrow \hspace{0.3cm} H_{\rm 2} = \frac{1}{2} \cdot \left [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \right ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
3.  Da MQ3 Markoveigenschaften aufweist, können aus H1 und H2 alle Entropienäherungen <nobr>Hk (k = 3, 4, ... )</nobr> direkt angegeben werden und auch der Grenzwert H = Hk für k → ∞:
$$H \hspace{0.1cm} = \hspace{0.1cm} 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{1.25cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},\\ H_3 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 2 \cdot H)/3 = (1.5 + 2 \cdot 1.25)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},\\ H_4 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 3 \cdot H)/4 = (1.5 + 3 \cdot 1.25)/4 \hspace{0.15cm} \underline {= 1.3125 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
Die 10. Entropienäherung unterscheidet sich noch immer, wenn auch nur geringfügig (um 2%) vom Endwert H = 1.25 bit/Symbol:
$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10 {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
4.  Entsprechend der Angabe sind hier die Symbole gleichwahrscheinlich. Daraus folgt:
$$H_{\rm 1} = H_{\rm 0} = {\rm log}_2\hspace{0.1cm} (4) \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
5.  Von den M2 = 16 möglichen Zweiertupeln sind acht Kombinationen nicht möglich: NP, NO, PP, PO, OM, ON, MM, MN. Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert 1/8, wie an zwei Beispielen gezeigt werden soll:
$$p_{\rm NN} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\\ p_{\rm MP} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm M} \cdot p_{\rm P\hspace{0.01cm}|\hspace{0.01cm}M} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$
$$\Rightarrow \hspace{0.3cm} H_2 = \frac{1}{2} \cdot \left [ 8 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm} (8) \right ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
6.  Aufgrund der Markoveigenschaft gilt hier:
$$H \hspace{0.1cm} = \hspace{0.1cm} 2 \cdot H_2 - H_1 = 2\cdot 1.5 - 2 \hspace{1.15cm} \underline {= 1 \,{\rm bit/Symbol}}\hspace{0.05cm},\\ H_3 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 2 \cdot H)/3 = (2 + 2 \cdot 1)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},\\ H_4 \hspace{0.1cm} = \hspace{0.1cm} (H_1 + 3 \cdot H)/4 = (2 + 3 \cdot 1)/4 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
Auch hier unterscheidet sich die 10. Näherung noch deutlich vom Endwert, nämlich um 10%:
$$H_{10} = (H_1 + 9 \cdot H)/10 = (2 + 9 \cdot 1)/10 {= 1.1 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$
Eine Abweichung um 2% ergibt sich hier erst für k = 50. Zum Vergleich: Bei der Markovquelle MQ3 wurde diese Annäherung bereits mit k = 10 erreicht.