Aufgaben:Aufgabe 1.6: Nichtbinäre Markovquellen: Unterschied zwischen den Versionen
Aus LNTwww
K (Guenter verschob die Seite 1.6 Nichtbinäre Markovquellen nach Aufgabe 1.6: Nichtbinäre Markovquellen) |
|||
| (8 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
}} | }} | ||
| − | [[Datei:P_ID2253__Inf_A_1_6.png|right|Markovquellen mit < | + | [[Datei:P_ID2253__Inf_A_1_6.png|right|frame|Markovquellen mit <br>$M = 3$ und $M = 4$]] |
| − | Die Grafik zeigt zwei ergodische Markovquellen (MQ): | + | Die Grafik zeigt zwei ergodische Markovquellen $\rm (MQ)$: |
| − | * Die Quelle | + | * Die Quelle $\rm MQ3$ ist durch $M = 3$ Zustände (Symbole) $\rm N$, $\rm M$, $\rm 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}.$$ | :$$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 | + | * Bei der Quelle $\rm MQ4$ ist zusätzlich der Zustand $\rm 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}.$$ | :$$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 | Informationstheoretisch sind Markovquellen von besonderer Bedeutung, da bei diesen – und nur bei diesen – durch | ||
| − | * $H_1$ (Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und | + | * $H_1$ (erste Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und |
| − | * $H_2$ (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel) | + | * $H_2$ (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel) |
| + | |||
gleichzeitig auch bestimmt sind: | gleichzeitig auch bestimmt sind: | ||
| − | * die weiteren Entropienäherungen $H_k$ mit $k = 3, 4$, ... und | + | * die weiteren Entropienäherungen $H_k$ mit $k = 3, \ 4$, ... und |
| − | * die tatsächliche Quellenentropie $H$. | + | * die tatsächliche Quellenentropie $H$. |
Es gelten folgende Bestimmungsgleichungen: | Es gelten folgende Bestimmungsgleichungen: | ||
| − | :$$H = 2 \cdot H_2 - H_1\hspace{0.05cm}, | + | :$$H = H_{k \to \infty}=2 \cdot H_2 - H_1\hspace{0.05cm},$$ |
| + | :$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ] | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
''Hinweise:'' | ''Hinweise:'' | ||
| − | *Die Aufgabe gehört zum Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]]. | + | *Die Aufgabe gehört zum Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]]. |
| − | *Bezug genommen wird insbesondere auf die Seite [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]]. | + | *Bezug genommen wird insbesondere auf die Seite [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Nichtbin.C3.A4re_Markovquellen|Nichtbinäre Markovquellen]]. |
*Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen. | *Bei allen Entropien ist die Pseudoeinheit „bit/Symbol” hinzuzufügen. | ||
| − | + | ||
| Zeile 37: | Zeile 45: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Berechnen Sie die Entropienäherung $H_1$ der Markovquelle | + | {Berechnen Sie die Entropienäherung $H_1$ der Markovquelle $\rm MQ3$. |
|type="{}"} | |type="{}"} | ||
| − | $H_1 \ = $ { 1.5 3% } $\ \rm bit/Symbol$ | + | $H_1 \ = \ $ { 1.5 3% } $\ \rm bit/Symbol$ |
| − | {Berechnen Sie die Entropienäherung $H_2$ der Markovquelle | + | {Berechnen Sie die Entropienäherung $H_2$ der Markovquelle $\rm MQ3$. |
|type="{}"} | |type="{}"} | ||
| − | $H_2 \ = $ { 1.375 3% } $\ \rm bit/Symbol$ | + | $H_2 \ = \ $ { 1.375 3% } $\ \rm bit/Symbol$ |
| − | {Wie groß sind für | + | {Wie groß sind für $\rm MQ3$ die tatsächliche Quellenentropie $H= H_{k \to \infty}$ und die Näherungen $H_3$ und $H_4$? |
|type="{}"} | |type="{}"} | ||
| − | $H \ = $ { 1.25 3% } $\ \rm bit/Symbol$ | + | $H \ = \ $ { 1.25 3% } $\ \rm bit/Symbol$ |
| − | $H_3 \ = $ { 1.333 3% } $\ \rm bit/Symbol$ | + | $H_3 \ = \ $ { 1.333 3% } $\ \rm bit/Symbol$ |
| − | $H_4 \ = $ { 1.3125 3% } $\ \rm bit/Symbol$ | + | $H_4 \ = \ $ { 1.3125 3% } $\ \rm bit/Symbol$ |
| − | {Berechnen Sie die Entropienäherung $H_1$ der Markovquelle | + | {Berechnen Sie die Entropienäherung $H_1$ der Markovquelle $\rm MQ4$. |
|type="{}"} | |type="{}"} | ||
| − | $H_1 \ = $ { 2 3% } $\ \rm bit/Symbol$ | + | $H_1 \ = \ $ { 2 3% } $\ \rm bit/Symbol$ |
| − | {Berechnen Sie die Entropienäherung $H_2$ der Markovquelle | + | {Berechnen Sie die Entropienäherung $H_2$ der Markovquelle $\rm MQ4$. |
|type="{}"} | |type="{}"} | ||
| − | $H_2 \ = $ { 1.5 3% } $\ \rm bit/Symbol$ | + | $H_2 \ = \ $ { 1.5 3% } $\ \rm bit/Symbol$ |
| − | {Wie groß sind für | + | {Wie groß sind für $\rm MQ4$ die tatsächliche Quellenentropie $H= H_{k \to \infty}$ und die Näherungen $H_3$ und $H_4$? |
|type="{}"} | |type="{}"} | ||
| − | $H \ = $ { 1 3% } $\ \rm bit/Symbol$ | + | $H \ = \ $ { 1 3% } $\ \rm bit/Symbol$ |
| − | $H_3 \ = $ { 1.333 3% } $\ \rm bit/Symbol$ | + | $H_3 \ = \ $ { 1.333 3% } $\ \rm bit/Symbol$ |
| − | $H_4 \ = $ { 1.25 3% } $\ \rm bit/Symbol$ | + | $H_4 \ = \ $ { 1.25 3% } $\ \rm bit/Symbol$ |
| Zeile 75: | Zeile 83: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben. Daraus lässt sich die Entropienäherung $H_1$ berechnen: | + | '''(1)''' Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben. |
| + | *Daraus lässt sich die Entropienäherung $H_1$ 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}} | :$$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}.$$ | \hspace{0.05cm}.$$ | ||
| − | |||
| − | $\rm X$ und $\rm Y$ sind hier Platzhalter für die Symbole $\rm N$, $\rm P$ und $\rm M$. Dann gilt: | + | |
| + | '''(2)''' Die Verbundwahrscheinlichkeit ist $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$, wobei $p_{\rm X}$ die Symbolwahrscheinlichkeit von $\rm X$ angibt und $p_{\rm Y|X}$ die bedingte Wahrscheinlichkeit für $\rm Y$, unter der Voraussetzung, dass vorher $\rm X$ aufgetreten ist. | ||
| + | |||
| + | *$\rm X$ und $\rm Y$ sind hier Platzhalter für die Symbole $\rm N$, $\rm P$ und $\rm M$. Dann gilt: | ||
:$$p_{\rm NN} = 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 NN} = 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} = 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 NP} = 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} = 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$$ | :$$ p_{\rm NM} = 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} = {1}/{2} \cdot \ | + | :$$\Rightarrow \hspace{0.3cm} H_{\rm 2} = {1}/{2} \cdot \big [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | '''(3)''' | + | |
| + | |||
| + | '''(3)''' $\rm MQ3$ weist Markoveigenschaften auf. | ||
| + | * Deshalb können aus $H_1$ und $H_2$ alle Näherungen $H_3$, $H_4$, ... und auch der Grenzwert $H =H_\infty$ für $k \to \infty$ angegeben werden: | ||
:$$H = 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm},$$ | :$$H = 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \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_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 = (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}.$$ | :$$ H_4 = (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 | + | *Die zehnte Entropienäherung unterscheidet sich noch immer vom Endwert $H = 1.25 \, \rm bit/Symbol$, wenn auch nur geringfügig $($um $2\%)$ : |
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (1.5 + 9 \cdot 1.25)/10 {= 1.275 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$ | :$$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 bei | + | |
| + | |||
| + | '''(4)''' Entsprechend der Angabe sind bei $\rm MQ4$ die $M = 4$ 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}} | :$$H_{\rm 1} = H_{\rm 0} = {\rm log}_2\hspace{0.1cm} (4) \hspace{0.15cm} \underline {= 2 \,{\rm bit/Symbol}} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | '''(5)''' Von den $M^2 = 16$ möglichen Zweiertupeln sind acht Kombinationen nicht möglich: | + | |
| + | |||
| + | '''(5)''' Von den $M^2 = 16$ möglichen Zweiertupeln sind nun acht Kombinationen nicht möglich: | ||
:$$\rm NP, NO, PP, PO, OM, ON, MM, MN.$$ | :$$\rm NP, NO, PP, PO, OM, ON, MM, MN.$$ | ||
| − | Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert $1/8$, wie an zwei Beispielen gezeigt wird: | + | *Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert $1/8$, wie an zwei Beispielen gezeigt wird: |
| − | :$$p_{\rm NN} = 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 NN} = p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\hspace{0.5cm} |
| − | + | p_{\rm MP} = 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 = {1}/{2} \cdot \ | + | :$$\Rightarrow \hspace{0.3cm} H_2 = {1}/{2} \cdot \big [ 8 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| + | |||
| + | |||
'''(6)''' Aufgrund der Markoveigenschaft gilt hier: | '''(6)''' Aufgrund der Markoveigenschaft gilt hier: | ||
| Zeile 112: | Zeile 133: | ||
:$$ H_3 = (H_1 + 2 \cdot H)/3 = (2 + 2 \cdot 1)/3 \hspace{0.15cm} \underline {= 1.333 \,{\rm bit/Symbol}}\hspace{0.05cm},$$ | :$$ H_3 = (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 = (H_1 + 3 \cdot H)/4 = (2 + 3 \cdot 1)/4 \hspace{0.15cm} \underline {= 1.250 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$ | :$$ H_4 = (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 | + | *Auch hier unterscheidet sich die zehnte Näherung noch deutlich vom Endwert, nämlich sogar um $10\%$: |
:$$H_{10} = (H_1 + 9 \cdot H)/10 = (2 + 9 \cdot 1)/10 {= 1.1 \,{\rm bit/Symbol}}\hspace{0.05cm}.$$ | :$$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 | + | *Eine Abweichung um nur $2\%$ ergibt sich hier erst für $k = 50$. Zum Vergleich: Bei der Markovquelle $\rm MQ3$ wurde diese Annäherung bereits mit $k = 10$ erreicht. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 21. Juni 2021, 14:54 Uhr
Markovquellen mit
$M = 3$ und $M = 4$
$M = 3$ und $M = 4$
Die Grafik zeigt zwei ergodische Markovquellen $\rm (MQ)$:
- Die Quelle $\rm MQ3$ ist durch $M = 3$ Zustände (Symbole) $\rm N$, $\rm M$, $\rm 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 $\rm MQ4$ ist zusätzlich der Zustand $\rm 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
- $H_1$ (erste Entropienäherung, nur auf den Symbolwahrscheinlichkeiten basierend), und
- $H_2$ (zweite Entropienäherung, berechenbar mit den Verbundwahrscheinlichkeiten für alle Zweiertupel)
gleichzeitig auch bestimmt sind:
- die weiteren Entropienäherungen $H_k$ mit $k = 3, \ 4$, ... und
- die tatsächliche Quellenentropie $H$.
Es gelten folgende Bestimmungsgleichungen:
- $$H = H_{k \to \infty}=2 \cdot H_2 - H_1\hspace{0.05cm},$$
- $$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H \big ] \hspace{0.05cm}.$$
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.
Fragebogen
Musterlösung
(1) Die Symbolwahrscheinlichkeiten der ternären Markovquelle sind gegeben.
- Daraus lässt sich die Entropienäherung $H_1$ 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 $p_{\rm XY} = p_{\rm X} \cdot p_{\rm Y|X}$, wobei $p_{\rm X}$ die Symbolwahrscheinlichkeit von $\rm X$ angibt und $p_{\rm Y|X}$ die bedingte Wahrscheinlichkeit für $\rm Y$, unter der Voraussetzung, dass vorher $\rm X$ aufgetreten ist.
- $\rm X$ und $\rm Y$ sind hier Platzhalter für die Symbole $\rm N$, $\rm P$ und $\rm M$. Dann gilt:
- $$p_{\rm NN} = 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} = 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} = 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} = {1}/{2} \cdot \big [ 1/4 \cdot {\rm log}_2\hspace{0.1cm}( 4) + 6 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
(3) $\rm MQ3$ weist Markoveigenschaften auf.
- Deshalb können aus $H_1$ und $H_2$ alle Näherungen $H_3$, $H_4$, ... und auch der Grenzwert $H =H_\infty$ für $k \to \infty$ angegeben werden:
- $$H = 2 \cdot H_2 - H_1 = 2\cdot 1.375 - 1.5 \hspace{0.15cm} \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 = (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 zehnte Entropienäherung unterscheidet sich noch immer vom Endwert $H = 1.25 \, \rm bit/Symbol$, wenn auch nur geringfügig $($um $2\%)$ :
- $$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 bei $\rm MQ4$ die $M = 4$ 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 $M^2 = 16$ möglichen Zweiertupeln sind nun acht Kombinationen nicht möglich:
- $$\rm NP, NO, PP, PO, OM, ON, MM, MN.$$
- Die acht weiteren Kombinationen (Zweiertupel) ergeben jeweils den Verbundwahrscheinlichkeitswert $1/8$, wie an zwei Beispielen gezeigt wird:
- $$p_{\rm NN} = p_{\rm N} \cdot p_{\rm N\hspace{0.01cm}|\hspace{0.01cm}N} = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},\hspace{0.5cm} p_{\rm MP} = 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 = {1}/{2} \cdot \big [ 8 \cdot 1/8 \cdot {\rm log}_2\hspace{0.1cm} (8) \big ] \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
(6) Aufgrund der Markoveigenschaft gilt hier:
- $$H = 2 \cdot H_2 - H_1 = 2\cdot 1.5 - 2 \hspace{0.15cm} \underline {= 1 \,{\rm bit/Symbol}}\hspace{0.05cm},$$
- $$ H_3 = (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 = (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 zehnte Näherung noch deutlich vom Endwert, nämlich sogar 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 nur $2\%$ ergibt sich hier erst für $k = 50$. Zum Vergleich: Bei der Markovquelle $\rm MQ3$ wurde diese Annäherung bereits mit $k = 10$ erreicht.
