Aufgaben:Exercise 1.5: Binary Markov Source

• Return to book

Betrachtetes binäres Markovdiagramm

Die Aufgabe 1.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 $H_k$ für $k$–Tupel berechnen und kann erst dann mit dem Grenzübergang $k \to \infty$ die Quellenentropie ermitteln:

$$H = \lim_{k \rightarrow \infty } H_k \hspace{0.05cm}.$$

Oft tendiert dabei $H_k$ 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) $\rm A$ und $\rm B$.

• Dieses ist durch die beiden bedingten Wahrscheinlichkeiten $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} = p$ und $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} = q$ eindeutig bestimmt.
• Die bedingten Wahrscheinlichkeiten $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$ und $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}$ sowie die Symbolwahrscheinlichkeiten $p_{\rm A}$ und $p_{\rm B}$ lassen sich daraus ermitteln.

Die Entropie der binären Markovkette (mit der Einheit „bit/Symbol”) lautet dann:

$$H = H_{\rm M} = 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 $p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}$, $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$, ... einzusetzen sind, während für die Gewichtung die Verbundwahrscheinlichkeiten $p_{\rm AA}$, $p_{\rm AB}$, ... 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 = H_{\rm M}$ 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}.$$

Hinweise:

• Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.
• Bezug genommen wird insbesondere auch auf die beiden Seiten Schnittmenge und Bedingte Wahrscheinlichkeit.
• Mit Ausnahme der Teilaufgabe (6) gelte stets $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_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \ = $

$p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \ = $

2 Wie groß sind die Symbolwahrscheinlichkeiten? Es gelte weiterhin $p = 1/4$ und $q = 1/2$.

$p_{\rm A} \ = $

$p_{\rm B} \ = $

3 Geben Sie die dazugehörige Entropienäherung erster Ordnung an.

$H_1 \ = $ $\ \rm bit/Symbol$

4 Welche Entropie $H = H_{\rm M}$ besitzt diese Markovquelle mit $p = 1/4$ und $q = 1/2$?

$H \ =$ $\ \rm bit/Symbol$

5 Welche Näherungen $H_k$ ergeben sich aufgrund der Markoveigenschaften?

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

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

$H_4 \ =$ $\ \rm bit/Symbol$

6 Welche Entropie $H = H_{\rm M}$ besitzt die Markovquelle mit $p = 1/4$ und $q = 3/4$?

$H \ =$ $\ \rm bit/Symbol$

Musterlösung

Solution

Markovdiagramm für die Teilaufgaben (1), ... , (5)

Nach $\rm A$ sind $\rm A$ und $\rm B$ gleichwahrscheinlich. Nach $\rm B$ tritt $\rm B$ sehr viel häufiger als $\rm A$ auf. Für die Übergangswahrscheinlichkeiten gilt:

$$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}.$$

(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{0.5cm}

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 in der letzten Teilaufgabe 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} = 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} =  {1}/{6} \hspace{0.05cm},$$

$$ p_{\rm AB} = 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} =  {1}/{6} \hspace{0.05cm},$$

$$ p_{\rm BA} = p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot p_{\rm B} = p \cdot \frac{q}{p+q} =

p_{\rm AB} =  {1}/{6} \hspace{0.05cm},$$

$$ p_{\rm BB} = 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} =  {1}/{2} $$

$$\Rightarrow\hspace{0.3cm} H = 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) =

10/6 - 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 $H_{\rm M} = H$ für die $k$–Entropienäherung: $H_k = {1}/{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm}.$ Daraus folgt:

$$H_2 = {1}/{2} \cdot [ 0.918 + 1 \cdot 0.875] \hspace{0.15cm} \underline {= 0.897 \,{\rm bit/Symbol}}

\hspace{0.05cm},$$

$$ H_3 = {1}/{3} \cdot [ 0.918 + 2 \cdot 0.875] \hspace{0.15cm} \underline {= 0.889 \,{\rm bit/Symbol}}

\hspace{0.05cm},$$

$$ H_4 = {1}/{4} \cdot [ 0.918 + 3 \cdot 0.875] \hspace{0.15cm} \underline {= 0.886 \,{\rm bit/Symbol}}

\hspace{0.05cm}.$$

Markovdiagramm zur Teilaufgaben (6)

(6)  Mit dem neuen Parametersatz ($p = 1/4, q = 3/4$) erhält man für die Symbolwahrscheinlichkeiten: $ p_{\rm A} = 1/4$ und $ p_{\rm B} = 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 $H_1$:

$$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 $H_2$, $H_3$, $H_4$, ... liefern hier ebenfalls das Ergebnis $0.811 \, \rm bit/Symbol$.