Exercise 1.4Z: Entropy of the AMI Code

From LNTwww
Revision as of 11:26, 1 December 2016 by Markus (talk | contribs)

P ID2249 Inf A 1 4.png
Wir gehen von ähnlichen Voraussetzungen wie in der Aufgabe A1.4 aus: Eine Binärquelle liefert die Quellensybolfolge 〈qν〉 mit qν ∈ {L, H}, wobei es keine statistischen Bindungen zwischen den einzelnen Folgenelementen gibt.
Für die Symbolwahrscheinlichkeiten gelte:
  • pL = pH = 1/2 (Teilaufgaben 1 und 2),
  • pL = 1/4, pH = 3/4 (Teilaufgaben 3, 4 und 5),
  • pL = 3/4, pH = 1/4 (Teilaufgabe 6).
Das dargestellte Codesignal c(t) und die zugehörige Symbolfolge 〈cν〉 mit cν ∈ {P, N, M} ergibt sich aus der AMI–Codierung (Alternate Mark Inversion) nach folgender Vorschrift:
  • Das Binärsymbol LLow wird stets durch das Ternärsymbol NNull dargestellt.
  • Das Binärsymbol HHigh wird ebenfalls deterministisch, aber alternierend (daher der Name „AMI”) durch die Symbole <nobr>PPlus</nobr> und MMinus codiert.
In dieser Aufgabe sollen für die drei oben genannten Parametersätze der Entscheidungsgehalt H0 sowie die resultierende Entropie HC der Codesymbolfolge 〈cν〉 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}.$$
Hinweis: Die Aufgabe gehört zu Kapitel 1.2. Allgemein bestehen folgende Relationen zwischen dem Entscheidungsgehalt H0, der Entropie H (hier gleich HC) und den Entropienäherungen:
$$H \le ... \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$
In Aufgabe A1.4 wurden für gleichwahrscheinliche Symbole L und 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.