Exercise 1.4Z: Entropy of the AMI Code

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:

p_L = p_H = 1/2 (Teilaufgaben 1 und 2),

p_L = 1/4, p_H = 3/4 (Teilaufgaben 3, 4 und 5),

p_L = 3/4, p_H = 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 L ⇒ Low wird stets durch das Ternärsymbol N ⇒ Null dargestellt.

Das Binärsymbol H ⇒ High wird ebenfalls deterministisch, aber alternierend (daher der Name „AMI”) durch die Symbole <nobr>P ⇒ Plus</nobr> und M ⇒ Minus codiert.

In dieser Aufgabe sollen für die drei oben genannten Parametersätze der Entscheidungsgehalt H₀ sowie die resultierende Entropie H_C 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 H₀, der Entropie H (hier gleich H_C) 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

$p_L = p_H:\ \ H_C$ =

$bit/Ternärsymbol$

$p_L = p_H:\ \ r_C$ =

%

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

$bit/Ternärsymbol$

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

%

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

$bit/Ternärsymbol$

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

$bit/Ternärsymbol$

Musterlösung

Solution

1. Da durch den AMI–Code weder neue Information hinzukommt noch Information verschwindet, ist die Entropie H_C der Codesymbolfolge 〈c_ν〉 gleich der Quellenentropie H_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₀ =&nbsp log₂ (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 H_C = H_Q. Wegen den ungleichen Symbolwahrscheinlichkeiten ist nun H_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}}$$

$$\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 p_N = 3/4 sowie p_P = p_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}.$$

Für p_L = 1/4, p_H = 3/4 ergibt sich H₁ = 1.56 bit/Symbol, bei p_L = 3/4, p_H = 1/4 dagegen ein deutlich kleinerer Wert: H₁ = 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 H₀ = 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 H₁, H₂, H₃, ... , berechnen, und

daraus (grafisch oder analytisch) den Grenzwert von H_k für k → ∞ bestimmen.

Erst dann ist eine endgültige Aussage über die Entropieverhältnisse möglich.