Aufgaben:Aufgabe 1.4Z: Entropie der AMI-Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2249__Inf_A_1_4.png|right|frame|Binäres Quellensignal (oben) und ternäres Codersignal (unten)]]
+
[[Datei:P_ID2249__Inf_A_1_4.png|right|frame|Binäres Quellensignal (oben) und <br>ternäres Codersignal (unten)]]
Wir gehen von ähnlichen Voraussetzungen wie in der [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]] aus: &nbsp; Eine Binärquelle liefert die Quellensybolfolge $\langle q_\nu \rangle$  mit $q_\nu \in \{ {\rm L}, {\rm H} \}$, wobei es keine statistischen Bindungen zwischen den einzelnen Folgenelementen gibt.
+
Wir gehen von ähnlichen Voraussetzungen wie in der&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]]&nbsp; aus: &nbsp;  
 +
 
 +
Eine Binärquelle liefert die Quellensybolfolge&nbsp; $\langle q_\nu \rangle$&nbsp; mit&nbsp; $q_\nu \in \{ {\rm L}, {\rm H} \}$, wobei es keine statistischen Bindungen zwischen den einzelnen Folgenelementen gibt.
  
 
Für die Symbolwahrscheinlichkeiten gelte:
 
Für die Symbolwahrscheinlichkeiten gelte:
* $p_{\rm L} =p_{\rm H} = 1/2$ (in den Teilaufgaben 1 und 2),
+
* $p_{\rm L} =p_{\rm H} = 1/2$&nbsp; (in den Teilaufgaben 1 und 2),
* $p_{\rm L} = 1/4, \, p_{\rm H} = 3/4$ (Teilaufgaben 3, 4 und 5),
+
* $p_{\rm L} = 1/4, \, p_{\rm H} = 3/4$&nbsp; (Teilaufgaben 3, 4 und 5),
* $p_{\rm L} = 3/4, \, p_{\rm H} = 1/4$ (Teilaufgabe 6).
+
* $p_{\rm L} = 3/4, \, p_{\rm H} = 1/4$&nbsp; (Teilaufgabe 6).
  
  
Das dargestellte Codersignal $c(t)$ und die zugehö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 dargestellte Codersignal&nbsp; $c(t)$&nbsp; und die zugehö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&nbsp; (<i>Alternate Mark Inversion</i>)&nbsp; 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>&nbsp; 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 für die drei oben genannten Parametersätze der Entscheidungsgehalt $H_0$ sowie die resultierende Entropie $H_{\rm C}$ der Codesymbolfolge $\langle c_\nu \rangle$ bestimmt werden. Die relative Redundanz der Codefolge ergibt sich daraus entsprechend der Gleichung
+
In dieser Aufgabe sollen für die drei oben genannten Parametersätze der Entscheidungsgehalt&nbsp; $H_0$&nbsp; sowie die resultierende Entropie&nbsp; $H_{\rm C}$&nbsp; der Codesymbolfolge&nbsp; $\langle c_\nu \rangle$&nbsp; bestimmt werden.&nbsp; Die relative Redundanz der Codefolge ergibt sich daraus entsprechend der Gleichung
 
:$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}}
 
:$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
 +
 +
 +
  
  
Zeile 26: Zeile 31:
  
 
''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&ndash;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&ndash;Codes]].
 
   
 
   
*Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt $H_0$, der Entropie $H$ (hier gleich $H_{\rm C}$ und den Entropienäherungen:  
+
*Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt&nbsp; $H_0$,&nbsp; der Entropie&nbsp; $H$&nbsp; $($hier gleich&nbsp; $H_{\rm C})$&nbsp; und den Entropienäherungen:  
 
:$$H \le \ \text{...} \  \le H_3 \le H_2 \le H_1 \le H_0  
 
:$$H \le \ \text{...} \  \le H_3 \le H_2 \le H_1 \le H_0  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
*In [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]] wurden für gleichwahrscheinliche Symbole $\rm L$ und $\rm H$ die Entropie&ndash;Näherungen wie folgt berechnet (jeweils in &bdquo;bit/Symbol&rdquo;):  
+
*In&nbsp; [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|Aufgabe 1.4]]&nbsp; wurden für gleichwahrscheinliche Symbole&nbsp; $\rm L$&nbsp; und&nbsp; $\rm H$&nbsp; die Entropie&ndash;Näherungen wie folgt berechnet (jeweils in &bdquo;bit/Symbol&rdquo;):  
 
:$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292
 
:$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Zeile 44: Zeile 49:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Die Quellensymbole seien gleichwahrscheinlich $(p_{\rm L} =  p_{\rm H}= 1/2)$. Wie groß ist die Entropie $H_{\rm C}$ der Codesymbolfolge $\langle c_\nu \rangle$?
+
{Die Quellensymbole seien gleichwahrscheinlich&nbsp; $(p_{\rm L} =  p_{\rm H}= 1/2)$.&nbsp; Wie groß ist die Entropie&nbsp; $H_{\rm C}$&nbsp; der Codesymbolfolge&nbsp; $\langle c_\nu \rangle$?
 
|type="{}"}
 
|type="{}"}
 
$H_{\rm C} \ = \ $ { 1 3% } $\ \rm bit/Ternärsymbol$
 
$H_{\rm C} \ = \ $ { 1 3% } $\ \rm bit/Ternärsymbol$
Zeile 54: Zeile 59:
  
  
{Für die Binärquelle gelte nun $p_{\rm L}  = 1/4$ &nbsp;und&nbsp; $p_{\rm H}  = 3/4$. Welcher Wert ergibt sich nun für die Entropie der Codesymbolfolge?
+
{Für die Binärquelle gelte nun&nbsp; $p_{\rm L}  = 1/4$ &nbsp;und&nbsp; $p_{\rm H}  = 3/4$.&nbsp; Welcher Wert ergibt sich nun für die Entropie der Codesymbolfolge?
 
|type="{}"}
 
|type="{}"}
 
$H_{\rm C} \ = \ $ { 0.811 3% } $\ \rm bit/Ternärsymbol$
 
$H_{\rm C} \ = \ $ { 0.811 3% } $\ \rm bit/Ternärsymbol$
Zeile 64: Zeile 69:
  
  
{Berechnen Sie die Näherung $H_{\rm 1}$ der Coderentropie für $p_{\rm L} = 1/4$ &nbsp;und&nbsp; $p_{\rm H} = 3/4$.
+
{Berechnen Sie die Näherung&nbsp; $H_{\rm 1}$&nbsp; der Coderentropie für&nbsp; $p_{\rm L} = 1/4$ &nbsp;und&nbsp; $p_{\rm H} = 3/4$.
 
|type="{}"}
 
|type="{}"}
 
$H_{\rm 1} \ = \ $ { 1.56 3% } $\ \rm bit/Ternärsymbol$
 
$H_{\rm 1} \ = \ $ { 1.56 3% } $\ \rm bit/Ternärsymbol$
  
  
{Berechnen Sie die Näherung $H_{\rm 1}$ der Coderentropie für $p_{\rm L} = 3/4$ &nbsp;und&nbsp; $p_{\rm H} = 1/4$.
+
{Berechnen Sie die Näherung&nbsp; $H_{\rm 1}$&nbsp; der Coderentropie für&nbsp; $p_{\rm L} = 3/4$ &nbsp;und&nbsp; $p_{\rm H} = 1/4$.
 
|type="{}"}
 
|type="{}"}
 
$H_{\rm 1} \ = \ $ { 1.06 3% } $\ \rm bit/Ternärsymbol$
 
$H_{\rm 1} \ = \ $ { 1.06 3% } $\ \rm bit/Ternärsymbol$
Zeile 79: Zeile 84:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Da durch den AMI&ndash;Code weder neue Information hinzukommt noch Information verschwindet, ist die Entropie $H_{\rm C}$ der Codesymbolfolge $\langle c_\nu \rangle$ gleich der Quellenentropie $H_{\rm Q}$. Bei gleichwahrscheinlichen und statistisch voneinander unabhängigen Quellensymbolen gilt deshalb:
+
'''(1)'''&nbsp; Da durch den AMI&ndash;Code weder neue Information hinzukommt noch Information verschwindet, ist die Entropie&nbsp; $H_{\rm C}$&nbsp; der Codesymbolfolge&nbsp; $\langle c_\nu \rangle$&nbsp; gleich der Quellenentropie&nbsp; $H_{\rm Q}$.&nbsp;
 +
*Bei gleichwahrscheinlichen und statistisch voneinander unabhängigen Quellensymbolen gilt deshalb:
 
:$$H_{\rm Q}    {= 1 \,{\rm bit/Bin\ddot{a}rsymbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C}    \hspace{0.15cm} \underline {= 1 \,{\rm bit/Tern\ddot{a}rsymbol}}  
 
:$$H_{\rm Q}    {= 1 \,{\rm bit/Bin\ddot{a}rsymbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C}    \hspace{0.15cm} \underline {= 1 \,{\rm bit/Tern\ddot{a}rsymbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(2)'''&nbsp; Der Entscheidungsgehalt einer ternären Quelle beträgt $H_0 = \log_2 \; (3) = 1.585\; \rm bit/Symbol$. Damit ergibt sich für die relative Redundanz
+
 
 +
 
 +
'''(2)'''&nbsp; Der Entscheidungsgehalt einer ternären Quelle beträgt&nbsp; $H_0 = \log_2 \; (3) = 1.585\; \rm bit/Symbol$.&nbsp;
 +
* Damit ergibt sich für die relative Redundanz
 
:$$r_{\rm C} =1 -{H_{\rm C}/H_{\rm 0}}=1-1/{\rm log}_2\hspace{0.05cm}(3)  
 
:$$r_{\rm C} =1 -{H_{\rm C}/H_{\rm 0}}=1-1/{\rm log}_2\hspace{0.05cm}(3)  
 
  \hspace{0.15cm} \underline {= 36.9  \,\%}
 
  \hspace{0.15cm} \underline {= 36.9  \,\%}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(3)'''&nbsp; Es gilt weiter $H_{\rm C} = H_{\rm Q}$. Wegen den ungleichen Symbolwahrscheinlichkeiten ist aber nun $H_{\rm Q}$ kleiner:
+
 
 +
 
 +
'''(3)'''&nbsp; Es gilt weiter&nbsp; $H_{\rm C} = H_{\rm Q}$.&nbsp; Wegen den ungleichen Symbolwahrscheinlichkeiten ist aber nun&nbsp; $H_{\rm Q}$&nbsp; kleiner:
 
:$$H_{\rm Q}  =  \frac{1}{4} \cdot {\rm log}_2\hspace{0.05cm} (4) + \frac{3}{4} \cdot  
 
:$$H_{\rm Q}  =  \frac{1}{4} \cdot {\rm log}_2\hspace{0.05cm} (4) + \frac{3}{4} \cdot  
 
{\rm log}_2\hspace{0.1cm} (4/3)
 
{\rm log}_2\hspace{0.1cm} (4/3)
Zeile 95: Zeile 106:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(4)'''&nbsp; In Analogie zur Teilaufgabe (2) gilt nun $r_{\rm C} = 1 -  0.811/1.585
+
 
 +
 
 +
'''(4)'''&nbsp; In Analogie zur Teilaufgabe&nbsp; '''(2)'''&nbsp; gilt nun&nbsp; $r_{\rm C} = 1 -  0.811/1.585
 
  \hspace{0.15cm} \underline {= 48.8  \,\%}
 
  \hspace{0.15cm} \underline {= 48.8  \,\%}
 
  \hspace{0.05cm}.$
 
  \hspace{0.05cm}.$
Man kann dieses Ergebnis verallgemeinern. Es gilt nämlich :
+
*Man kann dieses Ergebnis verallgemeinern. Es gilt nämlich:
 
:$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)\hspace{0.3cm}
 
:$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)\hspace{0.3cm}
 
\Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge})  = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code})
 
\Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge})  = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code})
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(5)'''&nbsp; Da jedes $\rm L$ auf $\rm N$ abgebildet wird und $\rm H$ alternierend auf $\rm M$ und $\rm P$, gilt
+
 
 +
 
 +
'''(5)'''&nbsp; Da jedes&nbsp; $\rm L$&nbsp; auf&nbsp; $\rm N$&nbsp; abgebildet wird und&nbsp; $\rm H$&nbsp; alternierend auf&nbsp; $\rm M$&nbsp; und&nbsp; $\rm P$, gilt
 
:$$p_{\rm N} = p_{\rm L} = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 3/8\hspace{0.3cm}  
 
:$$p_{\rm N} = p_{\rm L} = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 3/8\hspace{0.3cm}  
 
\Rightarrow\hspace{0.3cm} H_1  = {1}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4) +  
 
\Rightarrow\hspace{0.3cm} H_1  = {1}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4) +  
Zeile 109: Zeile 124:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
'''(6)'''&nbsp; Nun ergeben sich die Auftrittswahrscheinlichkeiten der Ternärsymbole zu  $p_{\rm N} = 3/4$ sowie $p_{\rm P} = p_{\rm M} =1/8$. Somit gilt:
+
 
 +
'''(6)'''&nbsp; Nun ergeben sich die Auftrittswahrscheinlichkeiten der Ternärsymbole zu&nbsp; $p_{\rm N} = 3/4$&nbsp; sowie&nbsp; $p_{\rm P} = p_{\rm M} =1/8$.&nbsp; Somit gilt:
 
:$$H_1  = {3}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4/3) +  
 
:$$H_1  = {3}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4/3) +  
 
  2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} \underline {= 1.06 \,{\rm bit/Tern\ddot{a}rsymbol}}  
 
  2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8)  \hspace{0.15cm} \underline {= 1.06 \,{\rm bit/Tern\ddot{a}rsymbol}}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
<br>''Interpretation:''
+
 
*Für $p_{\rm L} = 1/4, \ p_{\rm H} = 3/4$ ergibt sich $H_1 = 1.56 \; \rm bit/Symbol$.  
+
''Interpretation:''
*Für $p_{\rm L} = 3/4, \ p_{\rm H} = 1/4$  ergibt sich dagegen mit $H_1 = 1.06 \; \rm bit/Symbol$ ein deutlich kleinerer Wert.
+
*Für&nbsp; $p_{\rm L} = 1/4, \ p_{\rm H} = 3/4$&nbsp; ergibt sich&nbsp; $H_1 = 1.56 \; \rm bit/Symbol$.  
 +
*Für&nbsp; $p_{\rm L} = 3/4, \ p_{\rm H} = 1/4$&nbsp; ergibt sich dagegen mit&nbsp; $H_1 = 1.06 \; \rm bit/Symbol$&nbsp; ein deutlich kleinerer Wert.
 
*Für beide Parameterkombinationen gilt aber gleichermaßen:
 
*Für beide Parameterkombinationen gilt aber gleichermaßen:
 
:$$H_0  = 1.585 \,{\rm bit/Symbol}\hspace{0.05cm},\hspace{0.2cm}H_{\rm C} =  
 
:$$H_0  = 1.585 \,{\rm bit/Symbol}\hspace{0.05cm},\hspace{0.2cm}H_{\rm C} =  
 
  \lim_{k \rightarrow \infty } H_k = 0.811 \,{\rm bit/Symbol}
 
  \lim_{k \rightarrow \infty } H_k = 0.811 \,{\rm bit/Symbol}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
 +
Daraus folgt: <br>
 +
*Betrachtet man zwei Nachrichtenquellen&nbsp; $\rm Q1$&nbsp; und&nbsp; $\rm Q2$&nbsp; mit gleichem Symbolumfang&nbsp; $M$ &nbsp; &#8658; &nbsp; Entscheidungsgehalt&nbsp; $H_0 = \rm const.$, wobei bei der Quelle&nbsp; $\rm Q1$&nbsp; die Entropienäherung erster Ordnung&nbsp; $(H_1)$&nbsp; deutlich größer ist als bei der Quelle&nbsp; $\rm Q2$, so kann man daraus noch lange nicht schließen, dass die Entropie von&nbsp; $\rm Q1$&nbsp; tatsächlich größer ist als die Entropie von $\rm Q2$.&nbsp;
 +
*Vielmehr muss man für beide Quellen
 +
:* genügend viele Entropienäherungen&nbsp; $H_1$,&nbsp; $H_2$,&nbsp; $H_3$,&nbsp; ...  berechnen, und
 +
:* daraus (grafisch oder analytisch) den Grenzwert von&nbsp; $H_k$&nbsp; für&nbsp; $k \to \infty$&nbsp; bestimmen.
  
Daraus folgt: <br>Betrachtet man zwei Nachrichtenquellen '''Q1''' und '''Q2''' mit gleichem Symbolumfang $M$ &nbsp;&#8658;&nbsp; Entscheidungsgehalt&nbsp; $H_0 = \rm const.$, wobei bei der Quelle '''Q1''' die Entropienäherung erster Ordnung $(H_1)$ deutlich größer ist als bei der Quelle '''Q2''', so kann man daraus noch lange nicht schließen, dass die Entropie von '''Q1''' tatsächlich größer ist als die Entropie von '''Q2'''. Vielmehr muss man für beide Quellen
+
*Erst dann ist eine endgültige Aussage über die Entropieverhältnisse möglich.
* genügend viele Entropienäherungen $H_1$, $H_2$, $H_3$, ...  berechnen, und
 
* daraus (grafisch oder analytisch) den Grenzwert von $H_k$ für $k \to \infty$ bestimmen.
 
 
 
Erst dann ist eine endgültige Aussage über die Entropieverhältnisse möglich.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 16. Januar 2020, 18:30 Uhr

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

Wir gehen von ähnlichen Voraussetzungen wie in der  Aufgabe 1.4  aus:  

Eine Binärquelle liefert die Quellensybolfolge  $\langle q_\nu \rangle$  mit  $q_\nu \in \{ {\rm L}, {\rm H} \}$, wobei es keine statistischen Bindungen zwischen den einzelnen Folgenelementen gibt.

Für die Symbolwahrscheinlichkeiten gelte:

  • $p_{\rm L} =p_{\rm H} = 1/2$  (in den Teilaufgaben 1 und 2),
  • $p_{\rm L} = 1/4, \, p_{\rm H} = 3/4$  (Teilaufgaben 3, 4 und 5),
  • $p_{\rm L} = 3/4, \, p_{\rm H} = 1/4$  (Teilaufgabe 6).


Das dargestellte Codersignal  $c(t)$  und die zugehö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 für die drei oben genannten Parametersätze der Entscheidungsgehalt  $H_0$  sowie die resultierende Entropie  $H_{\rm C}$  der Codesymbolfolge  $\langle c_\nu \rangle$  bestimmt werden.  Die relative Redundanz der Codefolge ergibt sich daraus entsprechend der Gleichung

$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}} \hspace{0.05cm}.$$




Hinweise:

  • Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt  $H_0$,  der Entropie  $H$  $($hier gleich  $H_{\rm C})$  und den Entropienäherungen:
$$H \le \ \text{...} \ \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$
  • In  Aufgabe 1.4  wurden für gleichwahrscheinliche Symbole  $\rm L$  und  $\rm H$  die Entropie–Näherungen wie folgt berechnet (jeweils in „bit/Symbol”):
$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292 \hspace{0.05cm}.$$




Fragebogen

1

Die Quellensymbole seien gleichwahrscheinlich  $(p_{\rm L} = p_{\rm H}= 1/2)$.  Wie groß ist die Entropie  $H_{\rm C}$  der Codesymbolfolge  $\langle c_\nu \rangle$?

$H_{\rm C} \ = \ $

$\ \rm bit/Ternärsymbol$

2

Wie groß ist die relative Redundanz der Codesymbolfolge?

$r_{\rm C} \ = \ $

$\ \rm \%$

3

Für die Binärquelle gelte nun  $p_{\rm L} = 1/4$  und  $p_{\rm H} = 3/4$.  Welcher Wert ergibt sich nun für die Entropie der Codesymbolfolge?

$H_{\rm C} \ = \ $

$\ \rm bit/Ternärsymbol$

4

Wie groß ist nun die relative Redundanz der Codesymbolfolge?

$r_{\rm C} \ = \ $

$\ \rm \%$

5

Berechnen Sie die Näherung  $H_{\rm 1}$  der Coderentropie für  $p_{\rm L} = 1/4$  und  $p_{\rm H} = 3/4$.

$H_{\rm 1} \ = \ $

$\ \rm bit/Ternärsymbol$

6

Berechnen Sie die Näherung  $H_{\rm 1}$  der Coderentropie für  $p_{\rm L} = 3/4$  und  $p_{\rm H} = 1/4$.

$H_{\rm 1} \ = \ $

$\ \rm bit/Ternärsymbol$


Musterlösung

(1)  Da durch den AMI–Code weder neue Information hinzukommt noch Information verschwindet, ist die Entropie  $H_{\rm C}$  der Codesymbolfolge  $\langle c_\nu \rangle$  gleich der Quellenentropie  $H_{\rm Q}$. 

  • Bei gleichwahrscheinlichen und statistisch voneinander unabhängigen Quellensymbolen gilt deshalb:
$$H_{\rm Q} {= 1 \,{\rm bit/Bin\ddot{a}rsymbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C} \hspace{0.15cm} \underline {= 1 \,{\rm bit/Tern\ddot{a}rsymbol}} \hspace{0.05cm}.$$


(2)  Der Entscheidungsgehalt einer ternären Quelle beträgt  $H_0 = \log_2 \; (3) = 1.585\; \rm bit/Symbol$. 

  • Damit ergibt sich für die relative Redundanz
$$r_{\rm C} =1 -{H_{\rm C}/H_{\rm 0}}=1-1/{\rm log}_2\hspace{0.05cm}(3) \hspace{0.15cm} \underline {= 36.9 \,\%} \hspace{0.05cm}.$$


(3)  Es gilt weiter  $H_{\rm C} = H_{\rm Q}$.  Wegen den ungleichen Symbolwahrscheinlichkeiten ist aber nun  $H_{\rm Q}$  kleiner:

$$H_{\rm Q} = \frac{1}{4} \cdot {\rm log}_2\hspace{0.05cm} (4) + \frac{3}{4} \cdot {\rm log}_2\hspace{0.1cm} (4/3) {= 0.811 \,{\rm bit/Bin\ddot{a}rsymbol}} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_{\rm C} = H_{\rm Q} \hspace{0.15cm} \underline {= 0.811 \,{\rm bit/Tern\ddot{a}rsymbol}} \hspace{0.05cm}.$$


(4)  In Analogie zur Teilaufgabe  (2)  gilt nun  $r_{\rm C} = 1 - 0.811/1.585 \hspace{0.15cm} \underline {= 48.8 \,\%} \hspace{0.05cm}.$

  • Man kann dieses Ergebnis verallgemeinern. Es gilt nämlich:
$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge}) = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code}) \hspace{0.05cm}.$$


(5)  Da jedes  $\rm L$  auf  $\rm N$  abgebildet wird und  $\rm H$  alternierend auf  $\rm M$  und  $\rm P$, gilt

$$p_{\rm N} = p_{\rm L} = 1/4\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 3/8\hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_1 = {1}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4) + 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8/3) \hspace{0.15cm} \underline {= 1.56 \,{\rm bit/Tern\ddot{a}rsymbol}} \hspace{0.05cm}.$$


(6)  Nun ergeben sich die Auftrittswahrscheinlichkeiten der Ternärsymbole zu  $p_{\rm N} = 3/4$  sowie  $p_{\rm P} = p_{\rm M} =1/8$.  Somit gilt:

$$H_1 = {3}/{4} \cdot {\rm log}_2\hspace{0.1cm} (4/3) + 2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}(8) \hspace{0.15cm} \underline {= 1.06 \,{\rm bit/Tern\ddot{a}rsymbol}} \hspace{0.05cm}.$$

Interpretation:

  • Für  $p_{\rm L} = 1/4, \ p_{\rm H} = 3/4$  ergibt sich  $H_1 = 1.56 \; \rm bit/Symbol$.
  • Für  $p_{\rm L} = 3/4, \ p_{\rm H} = 1/4$  ergibt sich dagegen mit  $H_1 = 1.06 \; \rm bit/Symbol$  ein deutlich kleinerer Wert.
  • Für beide Parameterkombinationen gilt aber gleichermaßen:
$$H_0 = 1.585 \,{\rm bit/Symbol}\hspace{0.05cm},\hspace{0.2cm}H_{\rm C} = \lim_{k \rightarrow \infty } H_k = 0.811 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

Daraus folgt:

  • Betrachtet man zwei Nachrichtenquellen  $\rm Q1$  und  $\rm Q2$  mit gleichem Symbolumfang  $M$   ⇒   Entscheidungsgehalt  $H_0 = \rm const.$, wobei bei der Quelle  $\rm Q1$  die Entropienäherung erster Ordnung  $(H_1)$  deutlich größer ist als bei der Quelle  $\rm Q2$, so kann man daraus noch lange nicht schließen, dass die Entropie von  $\rm Q1$  tatsächlich größer ist als die Entropie von $\rm Q2$. 
  • Vielmehr muss man für beide Quellen
  • genügend viele Entropienäherungen  $H_1$,  $H_2$,  $H_3$,  ... berechnen, und
  • daraus (grafisch oder analytisch) den Grenzwert von  $H_k$  für  $k \to \infty$  bestimmen.
  • Erst dann ist eine endgültige Aussage über die Entropieverhältnisse möglich.