Aufgaben:Aufgabe 1.4: Entropienäherungen für den AMI-Code: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 4: Zeile 4:
  
 
[[Datei:P_ID2248__Inf_A_1_4.png|right|frame|Binäres Quellensignal (oben) und <br>ternäres Codersignal (unten)]]
 
[[Datei: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 $q(t)$, das man ebenfalls durch die Symbolfolge $\langle q_\nu \rangle$  mit $q_\nu \in \{ {\rm L}, {\rm H} \}$ beschreiben kann. In der gesamten Aufgabe gelte $p_{\rm L} = p_{\rm H} =0.5$.
+
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 $c(t)$ und die dazugehörige Symbolfolge $\langle c_\nu \rangle$  mit $c_\nu \in \{{\rm P}, {\rm N}, {\rm M}  \}$ ergibt sich aus der AMI&ndash;Codierung (<i>Alternate Mark Inversion</i>) nach folgender Vorschrift:
+
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 $\rm L$ &nbsp;&rArr;&nbsp; <i>Low</i> wird stets durch das Ternärsymbol $\rm N$ &nbsp;&rArr;&nbsp; <i>Null</i> dargestellt.
+
* 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 $\rm H$ &nbsp;&rArr;&nbsp; <i>High</i> wird ebenfalls deterministisch, aber alternierend (daher der Name &bdquo;AMI&rdquo;) durch die Symbole $\rm P$ &nbsp;&rArr;&nbsp; <i>Plus</i> und $\rm M$ &nbsp;&rArr;&nbsp; <i>Minus</i> codiert.
+
* 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:
 
In dieser Aufgabe sollen die Entropienäherungen für das AMI&ndash;codierte Signal berechnet werden:
  
* Die Näherung $H_1$ bezieht sich nur auf die Symbolwahrscheinlichkeiten $p_{\rm P}$, $p_{\rm N}$ und $p_{\rm M}$.
+
* 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 $k$&ndash;te Entropienäherung $(k = 2, 3, \text{...} \ )$ kann nach folgender Gleichung ermittelt werden:
+
* 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})
 
:$$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}.$$
 
  \hspace{0.05cm}.$$
:Hierbei bezeichnet $p_i^{(k)}$ die $i$&ndash;te Verbundwahrscheinlichkeit eines $k$&ndash;Tupels.
+
:Hierbei bezeichnet&nbsp; $p_i^{(k)}$&nbsp; die&nbsp; $i$&ndash;te Verbundwahrscheinlichkeit eines&nbsp; $k$&ndash;Tupels.
 +
 
 +
 
 +
 
  
  
Zeile 26: Zeile 29:
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
*Bezug genommen wird insbesondere auf die Seite  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Die_Entropie_des_AMI.E2.80.93Codes|Die Entropie des AMI-Codes]].
+
*Bezug genommen wird insbesondere auf die Seite&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Die_Entropie_des_AMI.E2.80.93Codes|Die Entropie des AMI-Codes]].
*In der  [[Aufgaben:1.4Z_Entropie_der_AMI-Codierung|Aufgabe 1.4Z]] wird die tatsächliche Entropie der Codesymbolfolge  $\langle c_\nu \rangle$ zu $H = 1 \; \rm bit/Symbol$ berechnet.
+
*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  
 
*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}.$
 
  \hspace{0.05cm}.$
Zeile 47: Zeile 50:
  
  
{Wie groß ist die Entropienäherung $H_2$, basierend auf Zweiertupel?
+
{Wie groß ist die Entropienäherung&nbsp; $H_2$, basierend auf Zweiertupel?
 
|type="{}"}
 
|type="{}"}
 
$H_2  \ = \ $ { 1.375 3% } $\ \rm bit/Symbol$
 
$H_2  \ = \ $ { 1.375 3% } $\ \rm bit/Symbol$
  
  
{Welchen Wert liefert die Entropienäherung $H_3$, basierend auf Dreiertuptel?
+
{Welchen Wert liefert die Entropienäherung&nbsp; $H_3$, basierend auf Dreiertuptel?
 
|type="{}"}
 
|type="{}"}
 
$H_3 \ = \ $ { 1.292 3% } $\ \rm bit/Symbol$
 
$H_3 \ = \ $ { 1.292 3% } $\ \rm bit/Symbol$
  
  
{Welche Aussagen gelten für die Entropienäherung $H_4$?
+
{Welche Aussagen gelten für die Entropienäherung&nbsp; $H_4$?
 
|type="[]"}
 
|type="[]"}
+ Es muss über $3^4 = 81$ Summanden gemittelt werden.
+
+ Es muss über&nbsp; $3^4 = 81$&nbsp; Summanden gemittelt werden.
+ Es gilt $1 \; {\rm bit/Symbol} < H_4 < H_3$.
+
+ Es gilt&nbsp; $1 \; {\rm bit/Symbol} < H_4 < H_3$.
- Nach langer Rechnung erhält man $H_4 = 1.333 \; {\rm bit/Symbol}$.
+
- Nach langer Rechnung erhält man&nbsp; $H_4 = 1.333 \; {\rm bit/Symbol}$.
  
  
Zeile 69: Zeile 72:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Der Symbolumfang beträgt $M = 3$. Daraus ergibt sich der Entscheidungsgehalt mit dem <i>Logarithmus dualis</i> zur Basis 2 &nbsp; &rArr; &nbsp; $\log_2$ bzw $\rm ld$:
+
'''(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}}  
 
:$$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}.$$
 
  \hspace{0.05cm}.$$
  
  
'''(2)'''&nbsp; Die Entropienäherung erster Ordnung berücksichtigt nur die Symbolwahrscheinlichkeiten $p_{\rm P}$, $p_{\rm N}$ und $p_{\rm M}$ und nicht die statistischen Bindungen innerhalb der Codefolge $\langle c_\nu \rangle$. Damit erhält man:
+
 
 +
'''(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}
 
:$$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) +  
 
\Rightarrow\hspace{0.3cm} H_1  = \frac{1}{2} \cdot {\rm log}_2\hspace{0.1cm} (2) +  
Zeile 81: Zeile 85:
  
  
'''(3)'''&nbsp; Zunächst müssen hier die $M^2 = 9$ Verbundwahrscheinlichkeiten von Zweiertupeln ermittelt werden, im Folgenden gekennzeichnet durch die beiden ersten Codesymbole $c_1$ und $c_2$:
+
 
* Da beim AMI&ndash;Code weder $\rm P$ auf $\rm P$ noch $\rm M$ auf $\rm M$ folgen kann, ist $p_{\rm PP} = p_{\rm MM} =0$.
+
'''(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$:
* Für die Verbundwahrscheinlichkeiten unter der Bedingung $c_2 = \rm N$ gilt:
+
* 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 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 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
 
:$$  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}.$$
 
  \hspace{0.05cm}.$$
* Die Verbundwahrscheinlichkeiten der Zweiertupel $\rm PM$  und $\rm MP$ lauten:
+
* 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 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}.$$
 
:$$ 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 $\rm H$ mit $\rm P$ oder mit $\rm M$ codiert wurde &nbsp;&#8658;&nbsp; weiterer Faktor $1/2$:
+
* 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 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}.$$
 
:$$ 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 $H_2'$ eines Zweiertupels bzw. dessen Entropie $H_2$ pro Codesymbol:
+
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) +  
 
:$$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}
 
  6 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} {= 2.75 \,{\rm bit/Zweiertupel}}\hspace{0.3cm}
Zeile 102: Zeile 107:
  
  
'''(4)'''&nbsp; Die Berechnung von $H_3$  erfolgt ähnlich wie bei der letzten Teilaufgabe für $H_2$, nur müssen nun $3^3 = 27$ Verbundwahrscheinlichkeiten ermittelt werden:
+
'''(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)}
 
:$$p_{\rm NNN} = 1/8\hspace{0.4cm}{\rm (nur \hspace{0.15cm}einmal)}
 
  \hspace{0.05cm},$$
 
  \hspace{0.05cm},$$
Zeile 116: Zeile 121:
  
 
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2</u>.  
 
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2</u>.  
*Falsch ist dagegen die Aussage 3, da $H_4$ auf jeden Fall kleiner sein muss als $H_3 = 1.292 \; \rm bit/Symbol$.
+
*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ß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 16. Januar 2020, 19:07 Uhr

Binäres Quellensignal (oben) und
ternäres Codersignal (unten)

Die Grafik zeigt oben das binäre Quellensignal  $q(t)$, das man ebenfalls durch die Symbolfolge  $\langle q_\nu \rangle$  mit  $q_\nu \in \{ {\rm L}, {\rm H} \}$  beschreiben kann.  In der gesamten Aufgabe gelte  $p_{\rm L} = p_{\rm H} =0.5$.

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

  • Das Binärsymbol  $\rm L$  ⇒  Low wird stets durch das Ternärsymbol  $\rm N$  ⇒  Null  dargestellt.
  • Das Binärsymbol  $\rm H$  ⇒  High  wird ebenfalls deterministisch, aber alternierend (daher der Name „AMI”) durch die Symbole  $\rm P$  ⇒  Plus  und  $\rm M$  ⇒  Minus  codiert.


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

  • Die Näherung  $H_1$  bezieht sich nur auf die Symbolwahrscheinlichkeiten  $p_{\rm P}$,  $p_{\rm N}$  und  $p_{\rm M}$.
  • Die  $k$–te Entropienäherung  $(k = 2, 3, \text{...} \ )$  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  $p_i^{(k)}$  die  $i$–te Verbundwahrscheinlichkeit eines  $k$–Tupels.





Hinweise:

  • Die Aufgabe gehört zum Kapitel  Nachrichtenquellen mit Gedächtnis.
  • Bezug genommen wird insbesondere auf die Seite  Die Entropie des AMI-Codes.
  • In der  Aufgabe 1.4Z  wird die tatsächliche Entropie der Codesymbolfolge  $\langle c_\nu \rangle$  zu  $H = 1 \; \rm bit/Symbol$  berechnet.
  • Zu erwarten sind die folgenden Größenrelationen:   $H \le$ ...$ \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$


Fragebogen

1

Wie groß ist der Entscheidungsgehalt des AMI–Codes?

$H_0 \ = \ $

$\ \rm bit/Symbol$

2

Berechnen Sie die erste Entropienäherung des AMI–Codes.

$H_1 \ = \ $

$\ \rm bit/Symbol$

3

Wie groß ist die Entropienäherung  $H_2$, basierend auf Zweiertupel?

$H_2 \ = \ $

$\ \rm bit/Symbol$

4

Welchen Wert liefert die Entropienäherung  $H_3$, basierend auf Dreiertuptel?

$H_3 \ = \ $

$\ \rm bit/Symbol$

5

Welche Aussagen gelten für die Entropienäherung  $H_4$?

Es muss über  $3^4 = 81$  Summanden gemittelt werden.
Es gilt  $1 \; {\rm bit/Symbol} < H_4 < H_3$.
Nach langer Rechnung erhält man  $H_4 = 1.333 \; {\rm bit/Symbol}$.


Musterlösung

(1)  Der Symbolumfang beträgt  $M = 3$.  Daraus ergibt sich der Entscheidungsgehalt mit dem  Logarithmus dualis  zur Basis $2$   ⇒   $\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)  Die Entropienäherung erster Ordnung berücksichtigt nur die Symbolwahrscheinlichkeiten  $p_{\rm P}$,  $p_{\rm N}$  und  $p_{\rm M}$  und nicht die statistischen Bindungen innerhalb der Codefolge  $\langle c_\nu \rangle$.  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)  Zunächst müssen hier die  $M^2 = 9$  Verbundwahrscheinlichkeiten von Zweiertupeln ermittelt werden, im Folgenden gekennzeichnet durch die beiden ersten Codesymbole  $c_1$  und  $c_2$:

  • Da beim AMI–Code weder  $\rm P$  auf  $\rm P$  noch  $\rm M$  auf  $\rm M$  folgen kann, ist  $p_{\rm PP} = p_{\rm MM} =0$.
  • Für die Verbundwahrscheinlichkeiten unter der Bedingung  $c_2 = \rm N$  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  $\rm PM$  und  $\rm MP$  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  $\rm H$  mit  $\rm P$  oder mit  $\rm M$  codiert wurde  ⇒  weiterer Faktor  $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  $H_2'$  eines Zweiertupels bzw. dessen Entropie  $H_2$  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)  Die Berechnung von  $H_3$  erfolgt ähnlich wie bei der letzten Teilaufgabe für  $H_2$, nur müssen nun  $3^3 = 27$  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)  Richtig sind die Lösungsvorschläge 1 und 2.

  • Falsch ist dagegen die Aussage 3, da  $H_4$  auf jeden Fall kleiner sein muss als  $H_3 = 1.292 \; \rm bit/Symbol$.