Aufgaben:Aufgabe 1.6Z: Ternäre Markovquelle: Unterschied zwischen den Versionen
Aus LNTwww
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 4: | Zeile 4: | ||
[[Datei:Inf_Z_1_6_vers2.png|right|frame|Ternäre Markovquelle]] | [[Datei:Inf_Z_1_6_vers2.png|right|frame|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: | + | 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}.$$ | :$$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: | Aufgrund der Markoveigenschaft dieser Quelle kann die Entropie auf unterschiedliche Weise ermittelt werden: | ||
| − | *Man berechnet die | + | *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}.$$ | :$$H = 2 \cdot H_{\rm 2} - H_{\rm 1} \hspace{0.05cm}.$$ | ||
| − | *Nach der | + | *Nach der „direkten Berechnungsmethode” kann die Entropie aber auch wie folgt geschrieben werden (insgesamt neun Terme): |
:$$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}} + \ \text{...} | :$$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}} + \ \text{...} | ||
\hspace{0.05cm}, \ | \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} | \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}, \ \text{...}$$ | p_{\rm AB} = p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm}, \ \text{...}$$ | ||
| + | |||
| + | |||
| + | |||
| Zeile 22: | Zeile 27: | ||
''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 31: | Zeile 36: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Für welche Parameter $p$ und $q$ ergibt sich die maximale Entropie pro Symbol? | + | {Für welche Parameter $p$ und $q$ ergibt sich die maximale Entropie pro Symbol? |
|type="{}"} | |type="{}"} | ||
$p \ = \ $ { 0.333 1% } | $p \ = \ $ { 0.333 1% } | ||
| Zeile 38: | Zeile 43: | ||
| − | {Es sei $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung? | + | {Es sei $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die erste Entropienäherung? |
|type="{}"} | |type="{}"} | ||
$H_1 = \ \ $ { 1.585 3% } $\ \rm bit/Symbol$ | $H_1 = \ \ $ { 1.585 3% } $\ \rm bit/Symbol$ | ||
| − | {Weiterhin gelte $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung? | + | {Weiterhin gelte $p = 1/4$ und $q = 1$. Welcher Wert ergibt sich in diesem Fall für die zweite Entropienäherung? |
|type="{}"} | |type="{}"} | ||
$H_2 = \ \ $ { 1.5425 1% } $\ \rm bit/Symbol$ | $H_2 = \ \ $ { 1.5425 1% } $\ \rm bit/Symbol$ | ||
| Zeile 63: | Zeile 68: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | + | '''(1)''' Die maximale Entropie ergibt sich dann, wenn die Symbole $\rm A$, $\rm B$ und $\rm C$ gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten: | |
| − | + | [[Datei:Inf_Z_1_6_vers2.png|right|frame|Übergangsdiagramm für $p = 1/4$, $q = 1$]] | |
| − | '''(1)''' Die maximale Entropie ergibt sich dann, wenn die Symbole $\rm A$, $\rm B$ und $\rm C$ gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten: | ||
* $p_{\rm A} = p_{\rm A|A} = p_{\rm A|B} = p_{\rm A|C} = 1/3$, | * $p_{\rm A} = p_{\rm A|A} = p_{\rm A|B} = p_{\rm A|C} = 1/3$, | ||
* $p_{\rm B} = p_{\rm B|A} = p_{\rm B|B} = p_{\rm B|C} = 1/3$, | * $p_{\rm B} = p_{\rm B|A} = p_{\rm B|B} = p_{\rm B|C} = 1/3$, | ||
| Zeile 72: | Zeile 76: | ||
Daraus lassen sich die gesuchten Werte bestimmen: | Daraus lassen sich die gesuchten Werte bestimmen: | ||
| − | *Beispielsweise erhält man aus $p_{\rm C|C} = 1/3$ | + | *Beispielsweise erhält man aus $p_{\rm C|C} = 1/3$ den Wert $p \hspace{0.15cm}\underline{= 1/3}$. |
| − | *Berücksichtigt man noch die Beziehung $p_{\rm A|A} = p \cdot q$, so folgt $q \hspace{0.15cm}\underline{= 1}$. | + | *Berücksichtigt man noch die Beziehung $p_{\rm A|A} = p \cdot q$, so folgt $q \hspace{0.15cm}\underline{= 1}$. |
| − | * Damit ergibt sich die maximale Entropie $H_\text{max} ={\rm | + | * Damit ergibt sich die maximale Entropie $H_\text{max} ={\rm log_2} \ 3\hspace{0.15cm}\underline{= 1.585\ \rm bit/Symbol}$. |
| + | |||
| + | |||
| + | '''(2)''' Mit den Parameterwerten $p = 1/4$ und $q = 1$ ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist: | ||
| + | * $p_{\rm A|A} = p_{\rm B|B} = p_{\rm C|C} = 1/4$ (rot markiert), | ||
| + | * $p_{\rm A|B} = p_{\rm B|C} = p_{\rm C|A} = 1/2$ (grün markiert), | ||
| + | *$p_{\rm A|C} = p_{\rm B|A} = p_{\rm C|CB} = 1/4$ (blau markiert). | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind: | Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind: | ||
:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3 \hspace{0.3cm} | :$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3 \hspace{0.3cm} | ||
| − | \Rightarrow \hspace{0.3cm} H_1 = {\rm | + | \Rightarrow \hspace{0.3cm} H_1 = {\rm log_2}\hspace{0.1cm} 3 \hspace{0.15cm} \underline {= 1.585 \,{\rm bit/Symbol}} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | '''(3)''' Für die zweite Entropienäherung benötigt man | + | |
| + | |||
| + | '''(3)''' Für die zweite Entropienäherung benötigt man $3^2 = 9$ Verbundwahrscheinlichkeiten. | ||
| + | *Mit dem Ergebnis aus '''(2)''' erhält man hierfür: | ||
:$$p_{\rm AA} = p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12 \hspace{0.05cm},\hspace{0.5cm} | :$$p_{\rm AA} = p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12 \hspace{0.05cm},\hspace{0.5cm} | ||
p_{\rm AB} = p_{\rm BC}=p_{\rm CA}=1/6$$ | p_{\rm AB} = p_{\rm BC}=p_{\rm CA}=1/6$$ | ||
| − | :$$\Rightarrow \hspace{0.2cm} H_2 = \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm | + | :$$\Rightarrow \hspace{0.2cm} H_2 = \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 12 + |
| − | 3 \cdot \frac{1}{6} \cdot {\rm | + | 3 \cdot \frac{1}{6} \cdot {\rm log_2}\hspace{0.1cm} 6 \right ] = \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 4 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 2 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 |
| − | = \frac{3}{4} + \frac{{\rm | + | = \frac{3}{4} + \frac{{\rm log_2}\hspace{0.1cm} 3}{2} \hspace{0.15cm} \underline {= 1.5425 \,{\rm bit/Symbol}} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| + | |||
| + | |||
'''(4)''' Aufgrund der Markoveigenschaft der Quelle gilt | '''(4)''' Aufgrund der Markoveigenschaft der Quelle gilt | ||
| − | :$$H = 2 \cdot H_2 - H_1 = [ {3}/{2} + {\rm | + | :$$H = 2 \cdot H_2 - H_1 = \big [ {3}/{2} + {\rm log_2}\hspace{0.1cm} 3 \big ] - {\rm log_2}\hspace{0.1cm} 3\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} |
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | Zum gleichen Ergebnis würde man | + | *Zum gleichen Ergebnis würde man nach folgender Rechnung kommen: |
| − | :$$H= p_{\rm AA} \cdot {\rm | + | :$$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}} + ... \hspace{0.1cm}= 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 4 + 3 \cdot \frac{1}{16} \cdot {\rm log_2}\hspace{0.1cm} 2 |
\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} | \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | [[Datei:Inf_Z_1_6e_vers2.png|right|Übergangsdiagramm für | + | |
| − | '''(5)''' Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität $p_{\rm B} = 0$ gelten wird, da $\rm B$ höchstens zum | + | [[Datei:Inf_Z_1_6e_vers2.png|right|frame|Übergangsdiagramm für $p = 1/4$, $q = 0$]] |
| + | '''(5)''' Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität $p_{\rm B} = 0$ gelten wird, da $\rm B$ höchstens zum Startzeitpunkt einmal auftreten kann. | ||
| + | *Es liegt also eine binäre Markovkette mit den Symbolen $\rm A$ und $\rm C$ vor. | ||
| + | *Die Symbolwahrscheinlichkeiten ergeben sich demzufolge zu: | ||
:$$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 \hspace{0.3cm} | :$$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 \hspace{0.3cm} | ||
\Rightarrow \hspace{0.3cm} p_{\rm A} = 1/3 \hspace{0.05cm}, \hspace{0.2cm} p_{\rm C} = 2/3\hspace{0.05cm}. $$ | \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: | + | *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}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} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CA} = | :$$ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C} =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 | + | 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 log_2}\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} =1\hspace{0.7cm} \Rightarrow \hspace{0.3cm} p_{\rm AC} = | :$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A} =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 | + | 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 log_2}\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} =1/2\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm CC} = | :$$ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} =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 | + | 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 log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} )= 1 $$ |
| − | :$$\Rightarrow \hspace{0.25cm} H = p_{\rm AA} \cdot {\rm | + | :$$\Rightarrow \hspace{0.25cm} 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 CA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C}}+ p_{\rm AC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A}} + |
| − | p_{\rm CC} \cdot {\rm | + | p_{\rm CC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}= |
0 + 1/3 \cdot 1 + 1/3 \cdot 0 + 1/3 \cdot 1 | 0 + 1/3 \cdot 1 + 1/3 \cdot 0 + 1/3 \cdot 1 | ||
\hspace{0.15cm} \underline {= 0.667 \,{\rm bit/Symbol}} | \hspace{0.15cm} \underline {= 0.667 \,{\rm bit/Symbol}} | ||
Aktuelle Version vom 21. Juni 2021, 15:09 Uhr
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 „direkten Berechnungsmethode” kann die Entropie aber auch wie folgt geschrieben werden (insgesamt neun Terme):
- $$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}} + \ \text{...} \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}, \ \text{...}$$
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 maximale Entropie ergibt sich dann, wenn die Symbole $\rm A$, $\rm B$ und $\rm C$ gleichwahrscheinlich und die Symbole innerhalb der Folge statistisch voneinander unabhängig sind. Dann muss gelten:
Übergangsdiagramm für $p = 1/4$, $q = 1$
- $p_{\rm A} = p_{\rm A|A} = p_{\rm A|B} = p_{\rm A|C} = 1/3$,
- $p_{\rm B} = p_{\rm B|A} = p_{\rm B|B} = p_{\rm B|C} = 1/3$,
- $p_{\rm C} = p_{\rm C|A} = p_{\rm C|B} = p_{\rm C|C} = 1/3$.
Daraus lassen sich die gesuchten Werte bestimmen:
- Beispielsweise erhält man aus $p_{\rm C|C} = 1/3$ den Wert $p \hspace{0.15cm}\underline{= 1/3}$.
- Berücksichtigt man noch die Beziehung $p_{\rm A|A} = p \cdot q$, so folgt $q \hspace{0.15cm}\underline{= 1}$.
- Damit ergibt sich die maximale Entropie $H_\text{max} ={\rm log_2} \ 3\hspace{0.15cm}\underline{= 1.585\ \rm bit/Symbol}$.
(2) Mit den Parameterwerten $p = 1/4$ und $q = 1$ ergibt sich das nebenstehende Übergangsdiagramm, das folgende Symmetrien aufweist:
- $p_{\rm A|A} = p_{\rm B|B} = p_{\rm C|C} = 1/4$ (rot markiert),
- $p_{\rm A|B} = p_{\rm B|C} = p_{\rm C|A} = 1/2$ (grün markiert),
- $p_{\rm A|C} = p_{\rm B|A} = p_{\rm C|CB} = 1/4$ (blau markiert).
Es ist offensichtlich, dass die Symbolwahrscheinlichkeiten alle gleich sind:
- $$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/3 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_1 = {\rm log_2}\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 $3^2 = 9$ Verbundwahrscheinlichkeiten.
- Mit dem Ergebnis aus (2) erhält man hierfür:
- $$p_{\rm AA} = p_{\rm BB}= p_{\rm CC}= p_{\rm AC}=p_{\rm BA}=p_{\rm CB}=1/12 \hspace{0.05cm},\hspace{0.5cm} p_{\rm AB} = p_{\rm BC}=p_{\rm CA}=1/6$$
- $$\Rightarrow \hspace{0.2cm} H_2 = \frac{1}{2} \cdot \left [ 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 12 + 3 \cdot \frac{1}{6} \cdot {\rm log_2}\hspace{0.1cm} 6 \right ] = \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 4 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 2 + \frac{1}{4} \cdot {\rm log_2}\hspace{0.1cm} 3 = \frac{3}{4} + \frac{{\rm log_2}\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 = \big [ {3}/{2} + {\rm log_2}\hspace{0.1cm} 3 \big ] - {\rm log_2}\hspace{0.1cm} 3\hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
- Zum gleichen Ergebnis würde man nach folgender Rechnung kommen:
- $$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}} + ... \hspace{0.1cm}= 6 \cdot \frac{1}{12} \cdot {\rm log_2}\hspace{0.1cm} 4 + 3 \cdot \frac{1}{16} \cdot {\rm log_2}\hspace{0.1cm} 2 \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
Übergangsdiagramm für $p = 1/4$, $q = 0$
(5) Aus dem nebenstehendenm Übergangsdiagramm mit den aktuellen Parametern erkennt man, dass bei Stationarität $p_{\rm B} = 0$ gelten wird, da $\rm B$ höchstens zum Startzeitpunkt einmal auftreten kann.
- Es liegt also eine binäre Markovkette mit den Symbolen $\rm A$ und $\rm C$ vor.
- Die Symbolwahrscheinlichkeiten ergeben sich demzufolge zu:
- $$p_{\rm A} = 0.5 \cdot p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm A} + p_{\rm C} = 1 \hspace{0.3cm} \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} =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 log_2}\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} =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 log_2}\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} =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 log_2}\hspace{0.1cm}(1/p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C} )= 1 $$
- $$\Rightarrow \hspace{0.25cm} 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 CA} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}C}}+ p_{\rm AC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm CC} \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{ p_{\rm C\hspace{0.01cm}|\hspace{0.01cm}C}}= 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}.$$
