Aufgaben:Exercise 1.4: Entropy Approximations for the AMI Code

• Return to book

Binary source signal (top) and
ternary encoder signal (bottom)

The graph above shows the binary source signal  $q(t)$, which can also be described by the symbol sequence  $\langle q_\nu \rangle$  with  $q_\nu \in \{ {\rm L}, {\rm H} \}$ .  In the entire task,  $p_{\rm L} = p_{\rm H} =0.5$ applies.

The coded signal  $c(t)$  and the corresponding symbol sequence  $\langle c_\nu \rangle$  with  $c_\nu \in \{{\rm P}, {\rm N}, {\rm M} \}$  results from the AMI coding (Alternate Mark Inversion) according to the following rule:

• The binary symbol  $\rm L$  ⇒  Low is always represented by the ternary symbol  $\rm N$  ⇒  Null .
• The binary symbol  $\rm H$  ⇒  High  is also coded deterministically but alternately (hence the name „AMI”) by the symbols  $\rm P$  ⇒  Plus  and  $\rm M$  ⇒  Minus .

In this task, the entropy approximations for the AMI–coded signal are to be calculated:

• Approximation  $H_1$  refers only to the symbol probabilities  $p_{\rm P}$,  $p_{\rm N}$  and  $p_{\rm M}$.

• The  $k$–th entropy approximation  $(k = 2, 3, \text{...} \ )$  can be determined according to the following equation:

$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{3^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_i^{(k)}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol}) \hspace{0.05cm}.$$

Here,  $p_i^{(k)}$  the  $i$–th composite probability of a  $k$–tuple.

Hints:

• This task belongs to the chapter  Sources with Memory.
• Reference is made in particular to the page  The entropy of the AMI-code.
• In task  Aufgabe 1.4Z  the actual entropy of the code symbol sequence  $\langle c_\nu \rangle$  is calculated to  $H = 1 \; \rm bit/symbol$ .
• The following relations between the units are to be expected:   $H \le$ ...$ \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$

Questions

1

Wie groß ist der Entscheidungsgehalt des AMI–Codes?

$H_0 \ = \ $ $\ \rm bit/Symbol$

2

Berechnen Sie die erste Entropienäherung des AMI–Codes.

$H_1 \ = \ $ $\ \rm bit/Symbol$

3

Wie groß ist die Entropienäherung  $H_2$, basierend auf Zweiertupel?

$H_2 \ = \ $ $\ \rm bit/Symbol$

4

Welchen Wert liefert die Entropienäherung  $H_3$, basierend auf Dreiertuptel?

$H_3 \ = \ $ $\ \rm bit/Symbol$

5

Welche Aussagen gelten für die Entropienäherung  $H_4$?

	Es muss über  $3^4 = 81$  Summanden gemittelt werden.
	Es gilt  $1 \; {\rm bit/Symbol} < H_4 < H_3$.
	Nach langer Rechnung erhält man  $H_4 = 1.333 \; {\rm bit/Symbol}$.

Musterlösung

Solution

(1)  Der Symbolumfang beträgt  $M = 3$.  Daraus ergibt sich der Entscheidungsgehalt mit dem  Logarithmus dualis  zur Basis $2$   ⇒   $\log_2$ bzw $\rm ld$:

$$H_0 = {\rm log}_2\hspace{0.1cm} M = {\rm log}_2\hspace{0.1cm} (3) \hspace{0.15cm} \underline { = 1.585 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

(2)  Die Entropienäherung erster Ordnung berücksichtigt nur die Symbolwahrscheinlichkeiten  $p_{\rm P}$,  $p_{\rm N}$  und  $p_{\rm M}$  und nicht die statistischen Bindungen innerhalb der Codefolge  $\langle c_\nu \rangle$.  Damit erhält man:

$$p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm P} = p_{\rm M} = p_{\rm H}/2 = 1/4 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_1 = \frac{1}{2} \cdot {\rm log}_2\hspace{0.1cm} (2) + 2 \cdot \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}(4) \hspace{0.15cm} \underline {= 1.5 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

(3)  Zunächst müssen hier die  $M^2 = 9$  Verbundwahrscheinlichkeiten von Zweiertupeln ermittelt werden, im Folgenden gekennzeichnet durch die beiden ersten Codesymbole  $c_1$  und  $c_2$:

• Da beim AMI–Code weder  $\rm P$  auf  $\rm P$  noch  $\rm M$  auf  $\rm M$  folgen kann, ist  $p_{\rm PP} = p_{\rm MM} =0$.
• Für die Verbundwahrscheinlichkeiten unter der Bedingung  $c_2 = \rm N$  gilt:

$$p_{\rm NN} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 = 1/4 \hspace{0.05cm},$$

$$ p_{\rm MN} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{M}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{M}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$

$$ p_{\rm PN} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{P}) \cdot {\rm Pr}(c_2 = \mathbf{N}\hspace{0.05cm} | c_1 = \mathbf{P}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$

• Die Verbundwahrscheinlichkeiten der Zweiertupel  $\rm PM$  und  $\rm MP$  lauten:

$$p_{\rm PM} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{P}) \cdot {\rm Pr}(c_2 = \mathbf{M}\hspace{0.05cm} | c_1 = \mathbf{P}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm},$$

$$ p_{\rm MP} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{M}) \cdot {\rm Pr}(c_2 = \mathbf{P}\hspace{0.05cm} | c_1 = \mathbf{M}) = 1/4 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$

• Bei den restlichen Wahrscheinlichkeiten muss zusätzlich berücksichtigt werden, ob beim letzten Mal das Binärsymbol  $\rm H$  mit  $\rm P$  oder mit  $\rm M$  codiert wurde  ⇒  weiterer Faktor  $1/2$:

$$p_{\rm NM} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{M}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 \cdot 1/2= 1/8 \hspace{0.05cm},$$

$$ p_{\rm NP} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}( c_1 = \mathbf{N}) \cdot {\rm Pr}(c_2 = \mathbf{P}\hspace{0.05cm} | c_1 = \mathbf{N}) = 1/2 \cdot 1/2 \cdot 1/2 = 1/8 \hspace{0.05cm}.$$

Damit ist die Entropie  $H_2'$  eines Zweiertupels bzw. dessen Entropie  $H_2$  pro Codesymbol:

$$H_2\hspace{0.01cm}' = \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm} (4) + 6 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}(8) \hspace{0.15cm} {= 2.75 \,{\rm bit/Zweiertupel}}\hspace{0.3cm} \Rightarrow\hspace{0.3cm} H_2 = \frac{H_2\hspace{0.01cm}'}{2} \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

(4)  Die Berechnung von  $H_3$  erfolgt ähnlich wie bei der letzten Teilaufgabe für  $H_2$, nur müssen nun  $3^3 = 27$  Verbundwahrscheinlichkeiten ermittelt werden:

$$p_{\rm NNN} = 1/8\hspace{0.4cm}{\rm (nur \hspace{0.15cm}einmal)} \hspace{0.05cm},$$

$$p_{\rm NMM} = p_{\rm NPP} = p_{\rm MNM} = ... = 0 \hspace{0.4cm}{\rm (ingesamt \hspace{0.15cm}12)} \hspace{0.05cm},$$

$$p_{\rm NNM} = p_{\rm NNP} = p_{\rm PMP} = ... = 1/16 \hspace{0.4cm}{\rm (ingesamt \hspace{0.15cm}14)}$$

$$\Rightarrow\hspace{0.3cm} H_3 = \frac{1}{3} \cdot \left [ \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm} (8) + 14 \cdot \frac{1}{16} \cdot {\rm log}_2\hspace{0.1cm}(16) \right ] \hspace{0.15cm} \underline {= 1.292 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

(5)  Richtig sind die Lösungsvorschläge 1 und 2.

• Falsch ist dagegen die Aussage 3, da  $H_4$  auf jeden Fall kleiner sein muss als  $H_3 = 1.292 \; \rm bit/Symbol$.