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|]]
+
[[Datei:P_ID2249__Inf_A_1_4.png|right|Binäres Quellensignal und ternäres Codersignal]]
:Wir gehen von ähnlichen Voraussetzungen wie in der Aufgabe A1.4 aus: Eine Binärquelle liefert die Quellensybolfolge &#9001;<i>q<sub>&nu;</sub></i>&#9002; mit <i>q<sub>&nu;</sub></i> &#8712; {<b>L</b>, <b>H</b>}, wobei es keine statistischen Bindungen zwischen den einzelnen Folgenelementen gibt.
+
Wir gehen von ähnlichen Voraussetzungen wie in der [[Aufgaben:1.4_Entropienäherungen_für_den_AMI-Code|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:
+
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).
  
:* <i>p</i><sub>L</sub> = <i>p</i><sub>H</sub> = 1/2 (Teilaufgaben 1 und 2),
+
Das dargestellte Codesignal $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:
  
:* <i>p</i><sub>L</sub> = 1/4, <i>p</i><sub>H</sub> = 3/4 (Teilaufgaben 3, 4 und 5),
+
* 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 $\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.
  
:* <i>p</i><sub>L</sub> = 3/4, <i>p</i><sub>H</sub> = 1/4 (Teilaufgabe 6).
+
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
 
 
:Das dargestellte Codesignal <i>c</i>(<i>t</i>) und die zugehörige Symbolfolge &#9001;<i>c<sub>&nu;</sub></i>&#9002; mit <i>c<sub>&nu;</sub></i>&nbsp;&#8712;&nbsp;{<b>P</b>, <b>N</b>, <b>M</b>} ergibt sich aus der AMI&ndash;Codierung (<i>Alternate Mark Inversion</i>) nach folgender Vorschrift:
 
 
 
:* Das Binärsymbol <b>L</b> &#8658; <i>Low</i> wird stets durch das Ternärsymbol <b>N</b> &#8658; <i>Null</i> dargestellt.
 
 
 
:* Das Binärsymbol <b>H</b> &#8658; <i>High</i> wird ebenfalls deterministisch, aber alternierend (daher der Name &bdquo;AMI&rdquo;) durch die Symbole <nobr><b>P</b> &#8658; <i>Plus</i></nobr> und <b>M</b> &#8658; <i>Minus</i> codiert.
 
 
 
:In dieser Aufgabe sollen für die drei oben genannten Parametersätze der Entscheidungsgehalt <i>H</i><sub>0</sub> sowie die resultierende Entropie <i>H</i><sub>C</sub> der Codesymbolfolge &#9001;<i>c<sub>&nu;</sub></i>&#9002; 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}}
 
:$$r_{\rm C} = \frac{H_{\rm 0}-H_{\rm C}}{H_{\rm C}}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>Hinweis:</b> Die Aufgabe gehört zu Kapitel 1.2. Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt <i>H</i><sub>0</sub>, der Entropie <i>H</i> (hier gleich <i>H</i><sub>C</sub>) und den Entropienäherungen:
+
 
:$$H \le ... \le H_3 \le H_2 \le H_1 \le H_0  
+
''Hinweise:''
  \hspace{0.05cm}.$$
+
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
:In Aufgabe A1.4 wurden für gleichwahrscheinliche Symbole <b>L</b> und <b>H</b> die Entropie&ndash;Näherungen wie folgt berechnet (jeweils in bit/Symbol):
+
*Bezug genommen wird insbesondere auf die Seite  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Die_Entropie_des_AMI.E2.80.93Codes|Die Entropie des AMI-Codes]].
:$$H_1 = 1.500\hspace{0.05cm},\hspace{0.2cm} H_2 = 1.375\hspace{0.05cm},\hspace{0.2cm}H_3 = 1.292
+
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
  \hspace{0.05cm}.$$
+
*Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt $H_0$, der Entropie $H$ (hier gleich $H_{\rm C}$ und den Entropienäherungen: &nbsp; $H \le$ ...$ \le H_3 \le H_2 \le H_1 \le H_0  
 +
  \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;): &nbsp; $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}.$
  
  

Version vom 28. April 2017, 16:22 Uhr

Binäres Quellensignal und ternäres Codersignal

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 Codesignal $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:

  • Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.
  • Bezug genommen wird insbesondere auf die Seite Die Entropie des AMI-Codes.
  • Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
  • Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt $H_0$, der Entropie $H$ (hier gleich $H_{\rm C}$ und den Entropienäherungen:   $H \le$ ...$ \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. Wie groß ist die Entropie HC der Codesymbolfolge 〈cν〉?

$p_L = p_H:\ \ H_C$ =

$bit/Ternärsymbol$

2

Wie groß ist die relative Redundanz der Codesymbolfolge?

$p_L = p_H:\ \ r_C$ =

%

3

Für die Binärquelle gelte nun pL = 1/4 und pH = 3/4. Welcher Wert ergibt sich nun für die Entropie der Codesymbolfolge?

$p_L = 1/4:\ \ H_C$ =

$bit/Ternärsymbol$

4

Wie groß ist nun die relative Redundanz der Codesymbolfolge?

$p_L = 1/4:\ \ r_C$ =

%

5

Berechnen Sie die Näherung H1 der Coderentropie für pL = 1/4, pH = 3/4.

$p_L = 1/4:\ \ H_1$ =

$bit/Ternärsymbol$

6

Berechnen Sie die Näherung H1 der Coderentropie für pL = 3/4, pH = 1/4.

$p_L = 3/4:\ \ H_1$ =

$bit/Ternärsymbol$


Musterlösung

1.  Da durch den AMI–Code weder neue Information hinzukommt noch Information verschwindet, ist die Entropie HC der Codesymbolfolge 〈cν〉 gleich der Quellenentropie HQ. 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 H0 =&nbsp log2 (3) = 1.585 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.  Weiter gilt HC = HQ. Wegen den ungleichen Symbolwahrscheinlichkeiten ist nun HQ 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}}$$
$$\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
$$r_{\rm C} = 1 - 0.811/1.585 \hspace{0.15cm} \underline {= 48.8 \,\%} \hspace{0.05cm}.$$
Man kann dieses Ergebnis verallgemeinern:
$$(1-0.488) = (1- 0.189) \cdot (1- 0.369)$$
$$\Rightarrow\hspace{0.3cm} (1-r_{\rm Codefolge}) = (1-r_{\rm Quelle}) \cdot (1- r_{\rm AMI-Code}) \hspace{0.05cm}.$$
5.  Da jedes L auf N abgebildet wird und H alternierend auf M und 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$$
$$\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 Symbolwahrscheinlichkeiten pN = 3/4 sowie pP = pM = 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}.$$
Für pL = 1/4, pH = 3/4 ergibt sich H1 = 1.56 bit/Symbol, bei pL = 3/4, pH = 1/4 dagegen ein deutlich kleinerer Wert: H1 = 1.06 bit/Symbol. 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 Q1 und Q2 mit gleichem Symbolumfang M  ⇒  Entscheidungsgehalt H0 = const., wobei bei der Quelle Q1 die Entropienäherung erster Ordnung 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
  • genügend viele Entropienäherungen H1, H2, H3, ... , berechnen, und
  • daraus (grafisch oder analytisch) den Grenzwert von Hk für k → ∞ bestimmen.
Erst dann ist eine endgültige Aussage über die Entropieverhältnisse möglich.