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

Aus LNTwww
Wechseln zu:Navigation, Suche
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$

Version vom 16. Januar 2020, 18:18 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.