Aufgaben:Aufgabe 1.4: Entropienäherungen für den AMI-Code: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Nachrichtenquellen mit Gedächtnis
+
{{quiz-Header|Buchseite=Informationstheorie/Nachrichtenquellen mit Gedächtnis
 
}}
 
}}
  

Version vom 1. Dezember 2016, 11:26 Uhr

P ID2248 Inf A 1 4.png
Die Grafik zeigt oben das binäre Quellensignal q(t), das man ebenfalls durch die Symbolfolge 〈qν〉 mit qν ∈ {LH} beschreiben kann. In der gesamten Aufgabe gelte pL = pH = 0.5.
Das codierte Signal c(t) und die dazugehörige Symbolfolge 〈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 die Entropienäherungen für das AMI–codierte Signal berechnet werden:
  • Die Näherung H1 bezieht sich nur auf die Symbolwahrscheinlichkeiten pP, pN und pM.
  • Die k–te Entropienäherung (k = 2, 3, ... ) kann nach folgender Gleichung ermittelt werden:
$$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}.$$
Hierbei bezeichnet pi(k) die i–te Verbundwahrscheinlichkeit eines k–Tupels.
Hinweis: Die Aufgabe gehört zu Kapitel 1.2. In der Aufgabe Z1.4 wird die tatsächliche Entropie der Codesymbolfolge 〈cν〉 zu H = 1 bit/Symbol berechnet. Zu erwarten sind die folgenden Größenrelationen:
$$H \le ... \le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$


Fragebogen

1

Wie groß ist der Entscheidungsgehalt des AMI–Codes?

$H_0$ =

$bit/Symbol$

2

Berechnen Sie die erste Entropienäherung.

$H_1$ =

$bit/Symbol$

3

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

$H_2$ =

$bit/Symbol$

4

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

$H_3$ =

$bit/Symbol$

5

Welche Aussagen gelten für die Entropienäherung H4?

Es muss über 34 = 81 Summanden gemittelt werden.
Es gilt 1 bit/Symbol < H4 < H3.
Nach langer Rechnung erhält man H4 = 1.333 bit/Symbol.


Musterlösung

1.  Der Symbolumfang beträgt M = 3. Daraus ergibt sich der Entscheidungsgehalt mit dem Logarithmus dualis zur Basis 2 (log2 oder „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 pP, pN und pM und nicht die statistischen Bindungen innerhalb der Codefolge 〈cν〉. 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$$
$$\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 M2 = 9 Verbundwahrscheinlichkeiten von Zweiertupeln ermittelt werden, im Folgenden gekennzeichnet durch die beiden ersten Codesymbole c1 und c2:
  • Da beim AMI–Code weder P auf P noch M auf M folgen kann, ist pPP = pMM = 0.
  • Für die Verbundwahrscheinlichkeiten unter der Bedingung c2 = 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 „PM” und „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 H mit P oder mit 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 H2' eines Zweiertupels bzw. dessen Entropie H2 pro Codesymbol:
$$H_2' = \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}}$$
$$\Rightarrow\hspace{0.3cm} H_2 = \frac{H_2'}{2} \hspace{0.15cm} \underline {= 1.375 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$
4.  Die Berechnung von H3 erfolgt ähnlich wie bei der letzten Teilaufgabe für H2, nur müssen nun 33 = 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 H4 auf jeden Fall kleiner sein muss als H3 = 1.292 bit/Symbol.