View source for Aufgaben:Exercise 1.4: Entropy Approximations for the AMI Code


{{quiz-Header|Buchseite=Informationstheorie/Nachrichtenquellen mit Gedächtnis
}}

[[File:P_ID2248__Inf_A_1_4.png|right|frame|Binäres Quellensignal (oben) und <br>ternäres Codersignal (unten)]]
Die Grafik zeigt oben das binäre Quellensignal&nbsp; $q(t)$, das man ebenfalls durch die Symbolfolge&nbsp; $\langle q_\nu \rangle$&nbsp;  mit&nbsp; $q_\nu \in \{ {\rm L}, {\rm H} \}$&nbsp; beschreiben kann.&nbsp; In der gesamten Aufgabe gelte&nbsp; $p_{\rm L} = p_{\rm H} =0.5$.

Das codierte Signal&nbsp; $c(t)$&nbsp; und die dazugehörige Symbolfolge&nbsp; $\langle c_\nu \rangle$&nbsp;  mit&nbsp; $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$&nbsp; ergibt sich aus der AMI&ndash;Codierung (<i>Alternate Mark Inversion</i>) nach folgender Vorschrift:

* Das Binärsymbol&nbsp; $\rm L$ &nbsp;&rArr;&nbsp; <i>Low</i> wird stets durch das Ternärsymbol&nbsp; $\rm N$ &nbsp;&rArr;&nbsp; <i>Null</i>&nbsp; dargestellt.
* Das Binärsymbol&nbsp; $\rm H$ &nbsp;&rArr;&nbsp; <i>High</i>&nbsp; wird ebenfalls deterministisch, aber alternierend (daher der Name &bdquo;AMI&rdquo;) durch die Symbole&nbsp; $\rm P$ &nbsp;&rArr;&nbsp; <i>Plus</i>&nbsp; und&nbsp; $\rm M$ &nbsp;&rArr;&nbsp; <i>Minus</i>&nbsp; codiert.


In dieser Aufgabe sollen die Entropienäherungen für das AMI&ndash;codierte Signal berechnet werden:

* Die Näherung&nbsp; $H_1$&nbsp; bezieht sich nur auf die Symbolwahrscheinlichkeiten&nbsp; $p_{\rm P}$,&nbsp; $p_{\rm N}$&nbsp; und&nbsp; $p_{\rm M}$.

* Die&nbsp; $k$&ndash;te Entropienäherung&nbsp; $(k = 2, 3, \text{...} \ )$&nbsp; kann nach folgender Gleichung ermittelt werden:
:$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{3^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_i^{(k)}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
 \hspace{0.05cm}.$$
:Hierbei bezeichnet&nbsp; $p_i^{(k)}$&nbsp; die&nbsp; $i$&ndash;te Verbundwahrscheinlichkeit eines&nbsp; $k$&ndash;Tupels.








''Hinweise:'' 
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
*Bezug genommen wird insbesondere auf die Seite&nbsp;  [[Information_Theory/Nachrichtenquellen_mit_Gedächtnis#Die_Entropie_des_AMI.E2.80.93Codes|Die Entropie des AMI-Codes]].
*In der&nbsp;  [[Aufgaben:1.4Z_Entropie_der_AMI-Codierung|Aufgabe 1.4Z]]&nbsp; wird die tatsächliche Entropie der Codesymbolfolge&nbsp;  $\langle c_\nu \rangle$&nbsp; zu&nbsp; $H = 1 \; \rm bit/Symbol$&nbsp; berechnet.
*Zu erwarten sind die folgenden Größenrelationen: &nbsp; $H \le$ ...$ \le H_3 \le H_2 \le H_1 \le H_0 
 \hspace{0.05cm}.$
 


===Fragebogen===

<quiz display=simple>
{Wie groß ist der Entscheidungsgehalt des AMI&ndash;Codes?
|type="{}"}
$H_0 \ = \ $  { 1.585 3% } $\ \rm bit/Symbol$


{Berechnen Sie die erste Entropienäherung des AMI&ndash;Codes.
|type="{}"}
$H_1 \ = \ $ { 1.5 3% } $\ \rm bit/Symbol$


{Wie groß ist die Entropienäherung&nbsp; $H_2$, basierend auf Zweiertupel?
|type="{}"}
$H_2  \ = \ $ { 1.375 3% } $\ \rm bit/Symbol$


{Welchen Wert liefert die Entropienäherung&nbsp; $H_3$, basierend auf Dreiertuptel?
|type="{}"}
$H_3 \ = \ $ { 1.292 3% } $\ \rm bit/Symbol$


{Welche Aussagen gelten für die Entropienäherung&nbsp; $H_4$?
|type="[]"}
+ Es muss über&nbsp; $3^4 = 81$&nbsp; Summanden gemittelt werden.
+ Es gilt&nbsp; $1 \; {\rm bit/Symbol} < H_4 < H_3$.
- Nach langer Rechnung erhält man&nbsp; $H_4 = 1.333 \; {\rm bit/Symbol}$.



</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; Der Symbolumfang beträgt&nbsp; $M = 3$.&nbsp; Daraus ergibt sich der Entscheidungsgehalt mit dem&nbsp; <i>Logarithmus dualis</i>&nbsp; zur Basis $2$ &nbsp; &rArr; &nbsp; $\log_2$ bzw $\rm ld$:
:$$H_0  = {\rm log}_2\hspace{0.1cm} M = {\rm log}_2\hspace{0.1cm} (3)   \hspace{0.15cm} \underline { = 1.585 \,{\rm bit/Symbol}} 
 \hspace{0.05cm}.$$



'''(2)'''&nbsp; Die Entropienäherung erster Ordnung berücksichtigt nur die Symbolwahrscheinlichkeiten&nbsp; $p_{\rm P}$,&nbsp; $p_{\rm N}$&nbsp; und&nbsp; $p_{\rm M}$&nbsp; und nicht die statistischen Bindungen innerhalb der Codefolge&nbsp; $\langle c_\nu \rangle$.&nbsp; Damit erhält man:
:$$p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 1/4 \hspace{0.3cm}
\Rightarrow\hspace{0.3cm} H_1  = \frac{1}{2} \cdot {\rm log}_2\hspace{0.1cm} (2) + 
 2 \cdot \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}(4)  \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} 
 \hspace{0.05cm}.$$



'''(3)'''&nbsp; Zunächst müssen hier die&nbsp; $M^2 = 9$&nbsp; Verbundwahrscheinlichkeiten von Zweiertupeln ermittelt werden, im Folgenden gekennzeichnet durch die beiden ersten Codesymbole&nbsp; $c_1$&nbsp; und&nbsp; $c_2$:
* Da beim AMI&ndash;Code weder&nbsp; $\rm P$&nbsp; auf&nbsp; $\rm P$&nbsp; noch&nbsp; $\rm M$&nbsp; auf&nbsp; $\rm M$&nbsp; folgen kann, ist&nbsp; $p_{\rm PP} = p_{\rm MM} =0$.
* Für die Verbundwahrscheinlichkeiten unter der Bedingung&nbsp; $c_2 = \rm N$&nbsp; gilt:
:$$p_{\rm NN} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 = 1/4 \hspace{0.05cm},$$
:$$ p_{\rm MN} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{M}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{M}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$
:$$  p_{\rm PN} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{P}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{P}) = 1/4 \cdot 1/2 = 1/8
 \hspace{0.05cm}.$$
* Die Verbundwahrscheinlichkeiten der Zweiertupel&nbsp; $\rm PM$&nbsp;  und&nbsp; $\rm MP$&nbsp; lauten:
:$$p_{\rm PM} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{P}) \cdot {\rm Pr}(c_2 = \mathbf{M}\hspace{0.05cm} | c_1 = \mathbf{P}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$
:$$ p_{\rm MP} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{M}) \cdot {\rm Pr}(c_2 = \mathbf{P}\hspace{0.05cm} | c_1 = \mathbf{M}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$
* Bei den restlichen Wahrscheinlichkeiten muss zusätzlich berücksichtigt werden, ob beim letzten Mal das Binärsymbol&nbsp; $\rm H$&nbsp; mit&nbsp; $\rm P$&nbsp; oder mit&nbsp; $\rm M$&nbsp; codiert wurde &nbsp;&#8658;&nbsp; weiterer Faktor&nbsp; $1/2$:
:$$p_{\rm NM} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{M}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 \cdot 1/2= 1/8 \hspace{0.05cm},$$
:$$ p_{\rm NP} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{P}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$

Damit ist die Entropie&nbsp; $H_2'$&nbsp; eines Zweiertupels bzw. dessen Entropie&nbsp; $H_2$&nbsp; pro Codesymbol:
:$$H_2\hspace{0.01cm}'  = \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm} (4) + 
 6 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} {= 2.75 \,{\rm bit/Zweiertupel}}\hspace{0.3cm}
\Rightarrow\hspace{0.3cm} H_2  = \frac{H_2\hspace{0.01cm}'}{2}   \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} 
 \hspace{0.05cm}.$$


'''(4)'''&nbsp; Die Berechnung von&nbsp; $H_3$&nbsp;  erfolgt ähnlich wie bei der letzten Teilaufgabe für&nbsp; $H_2$, nur müssen nun&nbsp; $3^3 = 27$&nbsp; Verbundwahrscheinlichkeiten ermittelt werden:
:$$p_{\rm NNN} = 1/8\hspace{0.4cm}{\rm (nur \hspace{0.15cm}einmal)}
 \hspace{0.05cm},$$
:$$p_{\rm NMM} = p_{\rm NPP} = p_{\rm MNM}  = ... = 0 \hspace{0.4cm}{\rm (ingesamt \hspace{0.15cm}12)}
 \hspace{0.05cm},$$
:$$p_{\rm NNM} = p_{\rm NNP} = p_{\rm PMP}  = ... = 1/16 \hspace{0.4cm}{\rm (ingesamt \hspace{0.15cm}14)}$$
:$$\Rightarrow\hspace{0.3cm} H_3  = \frac{1}{3} \cdot \left [ 
 \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm} (8) + 
 14 \cdot \frac{1}{16} \cdot {\rm log}_2\hspace{0.1cm}(16)
 \right ]  \hspace{0.15cm} \underline {= 1.292 \,{\rm bit/Symbol}} 
 \hspace{0.05cm}.$$


'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2</u>. 
*Falsch ist dagegen die Aussage 3, da&nbsp; $H_4$&nbsp; auf jeden Fall kleiner sein muss als&nbsp; $H_3 = 1.292 \; \rm bit/Symbol$.
{{ML-Fuß}}



[[Category:Information Theory: Exercises|^1.2 Nachrichtenquellen mit Gedächtnis^]]