Aufgabe 1.5: Binäre Markovquelle

Aus LNTwww
Wechseln zu:Navigation, Suche

P ID2250 Inf A 1 5.png
Die Aufgabe A1.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 Hk für k–Tupel berechnen und kann erst dann mit dem Grenzübergang k → ∞ die Quellenentropie ermitteln:
$$H = \lim_{k \rightarrow \infty } H_k \hspace{0.05cm}.$$
Oft tendiert dabei Hk 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) A und B. Dieses ist durch die beiden bedingten Wahrscheinlichkeiten pA|B = p und pB|A = q eindeutig bestimmt. Die bedingten Wahrscheinlichkeiten pA|A und pB|B sowie die Symbolwahrscheinlichkeiten pA und pB lassen sich daraus ermitteln.
Die Entropie der binären Markovkette (mit der Einheit „bit/Symbol”) lautet dann:
$$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}.$$
Bei dieser Gleichung ist zu beachten, dass im Argument des Logarithmus dualis jeweils die bedingten Wahrscheinlichkeiten pA|A, pB|A, ... einzusetzen sind, während für die Gewichtung die Verbundwahrscheinlichkeiten pAA, pAB, ... 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 lassen sich bei einer Markovquelle auch alle weiteren Entropienäherungen (k = 2, 3, ...) direkt berechnen:
$$H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm}.$$
Hinweis: Diese Aufgabe gehört zum Themengebiet von Kapitel 1.2. Mit Ausnahme der Teilaufgabe (6) sei p = 1/4 und q = 1/2.
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 = 1/4,\ q = 1/2:\ p_\text{A|A}$ =

$p_\text{B|B}$ =

2

Wie groß sind die Symbolwahrscheinlichkeiten?

$p = 1/4,\ q = 1/2:\ p_A$ =

$p_B$ =

3

Geben Sie die Entropienäherung erster Ordnung an.

$p = 1/4,\ q = 1/2:\ H_1$ =

$bit/Symbol$

4

Welche Entropie besitzt diese Markovquelle?

$p = 1/4,\ q = 1/2:\ H$ =

$bit/Symbol$

5

Welche Näherungen Hk ergeben sich aufgrund der Markoveigenschaften?

$p = 1/4,\ q = 1/2:\ H_2$ =

$bit/Symbol$
$H_3$ =

$bit/Symbol$
$H_4$ =

$bit/Symbol$

6

Welche Entropie besitzt die Markovquelle mit p = 1/4 und q = 3/4?

$p = 1/4,\ q = 1/2:\ H$ =

$bit/Symbol$


Musterlösung

P ID2757 Inf A 1 5.png
1.  Hier gilt für die Übergangswahrscheinlichkeiten:
$$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}.$$
Nach A sind A und B gleichwahrscheinlich. Nach B tritt B sehr viel häufiger als A auf.
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{2cm}$$
$$ 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 unter (b) 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} \hspace{0.1cm} = \hspace{0.1cm} 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} = \frac{1}{6} \hspace{0.05cm},\\ p_{\rm AB} \hspace{0.1cm} = \hspace{0.1cm} 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} = \frac{1}{6} \hspace{0.05cm},\\ p_{\rm BA} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B} = p \cdot \frac{q}{p+q} = p_{\rm AB} = \frac{1}{6} \hspace{0.05cm},\\ p_{\rm BB} \hspace{0.1cm} = \hspace{0.1cm} 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} = \frac{1}{2} $$
$$\Rightarrow\hspace{0.3cm} H \hspace{0.1cm} = \hspace{0.1cm} 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) = \\ \hspace{0.1cm} = \hspace{0.1cm} 1/6 + 1/6 + 2/6 + 1 - 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 HM = H für die k–Entropienäherung:
$$H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm}.$$
Daraus folgt:
$$H_2 \hspace{0.1cm} = \hspace{0.1cm} \frac{1}{2} \cdot [ 0.918 + 1 \cdot 0.875] \hspace{0.15cm} \underline {= 0.897 \,{\rm bit/Symbol}} \hspace{0.05cm},\\ H_3 \hspace{0.1cm} = \hspace{0.1cm} \frac{1}{3} \cdot [ 0.918 + 2 \cdot 0.875] \hspace{0.15cm} \underline {= 0.889 \,{\rm bit/Symbol}} \hspace{0.05cm},\\ H_4 \hspace{0.1cm} = \hspace{0.1cm} \frac{1}{4} \cdot [ 0.918 + 3 \cdot 0.875] \hspace{0.15cm} \underline {= 0.886 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
P ID2251 Inf A 1 5f.png
6.  Mit dem neuen Parametersatz (p = 1/4, q = 3/4) erhält man für die Symbolwahrscheinlichkeiten: pA = 1/4 und pB = 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 H1:
$$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 H2, H3, H4, ... liefern hier ebenfalls das Ergebnis 0.811 bit/Symbol.