Exercise 3.11Z: Extremely Asymmetrical Channel

From LNTwww
Revision as of 13:58, 23 March 2021 by Javier (talk | contribs) (Text replacement - "Category:Aufgaben zu Informationstheorie" to "Category:Information Theory: Exercises")

Einseitig verfälschender Kanal

Betrachtet wird der nebenstehend gezeichnete Kanal mit den folgenden Eigenschaften:

  • Das Symbol  $X = 0$  wird immer richtig übertragen und führt stets zum Ergebnis  $Y = 0$.
  • Das Symbol  $X = 1$  wird maximal verfälscht. 


Aus Sicht der Informationstheorie bedeutet dies:

$${\rm Pr}(Y \hspace{-0.05cm} = 0\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 1) ={\rm Pr}(Y \hspace{-0.05cm} = 1\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= 1) = 0.5 \hspace{0.05cm}.$$

Zu bestimmen sind in dieser Aufgabe:

  • die Transinformation  $I(X; Y)$  für  $P_X(0) = p_0 = 0.4$  und  $P_X(1) = p_1 = 0.6$. 
    Es gilt allgemein:
$$ I(X;Y) = H(X) - H(X \hspace{-0.1cm}\mid \hspace{-0.1cm} Y)\hspace{0.05cm}=H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm} =\hspace{-0.15cm} H(X) + H(Y)- H(XY)\hspace{0.05cm},$$
  • die Kanalkapazität:
$$ C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}.$$





Hinweise:


Fragebogen

1

Berechnen Sie die Quellenentropie allgemein und für  $\underline{p_0 = 0.4}$.

$H(X) \ = \ $

$\ \rm bit$

2

Berechnen Sie die Sinkenentropie allgemein und für  $p_0 = 0.4$.

$H(Y) \ = \ $

$\ \rm bit$

3

Berechnen Sie die Verbundentropie allgemein und für  $p_0 = 0.4$.

$H(XY) \ = \ $

$\ \rm bit$

4

Berechnen Sie die Transinformation allgemein und für  $p_0 = 0.4$.

$I(X; Y) \ = \ $

$\ \rm bit$

5

Welche Wahrscheinlichkeit  $p_0^{(*)}$  führt zur Kanalkapazität  $C$?

$p_0^{(*)} \ = \ $

6

Wie groß ist die Kanalkapazität des vorliegenden Kanals?

$C \ = \ $

$\ \rm bit$

7

Wie groß sind die bedingten Entropien mit  $p_0 = p_0^{(*)}$  gemäß Teilaufgabe  (5)?

$H(X|Y) \ = \ $

$\ \rm bit$
$H(Y|X) \ = \ $

$\ \rm bit$


Musterlösung

(1)  Die Quellenentropie ergibt sich entsprechend der binären Entropiefunktion:

$$H(X) = H_{\rm bin}(p_0)= H_{\rm bin}(0.4) \hspace{0.15cm} \underline {=0.971\,{\rm bit}} \hspace{0.05cm}.$$


(2)  Die Wahrscheinlichkeiten der Sinkensymbole sind:

$$P_Y(1) = p_1/2 = (1 - p_0)/2 = 0.3\hspace{0.05cm},\hspace{0.2cm} P_Y(0) = 1-P_Y(1) = p_1/2 = (1 - p_0)/2 = 0.7$$
$$\Rightarrow \hspace{0.3cm} H(Y) = H_{\rm bin}(\frac{1+p_0}{2})= H_{\rm bin}(0.7) \hspace{0.15cm} \underline {=0.881\,{\rm bit}} \hspace{0.05cm}.$$


(3)  Die Verbundwahrscheinlichkeiten  $p_{μκ} = {\rm Pr}\big[(X = μ) ∩ (Y = κ)\big] $ ergeben sich zu:

$$ p_{00} = p_0 \hspace{0.05cm},\hspace{0.3cm} p_{01} = 0 \hspace{0.05cm},\hspace{0.3cm} p_{10} = (1 - p_0)/2 \hspace{0.05cm},\hspace{0.3cm} p_{11} = (1 - p_0)/2$$
$$\Rightarrow \hspace{0.3cm} H(XY) =p_0 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{ p_0} + 2 \cdot \frac{1-p_0}{2} \cdot {\rm log}_2 \hspace{0.1cm} \frac{2}{ 1- p_0} = p_0 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{ p_0} + (1-p_0) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{ 1- p_0} + (1-p_0) \cdot {\rm log}_2 \hspace{0.1cm} (2)$$
$$\Rightarrow \hspace{0.3cm}H(XY) =H_{\rm bin}(p_0) + 1 - p_0 \hspace{0.05cm}.$$
  • Das numerische Ergebnis für  $p_0 = 0.4$  lautet somit:
$$H(XY) = H_{\rm bin}(0.4) + 0.6 = 0.971 + 0.6 \hspace{0.15cm} \underline {=1.571\,{\rm bit}} \hspace{0.05cm}.$$


(4)  Eine (mögliche) Gleichung zur Berechnung der Transinformation lautet:

$$ I(X;Y) = H(X) + H(Y)- H(XY)\hspace{0.05cm}.$$
  • Daraus erhält man mit den Ergebnissen der ersten drei Teilaufgaben:
$$I(X;Y) = H_{\rm bin}(p_0) + H_{\rm bin}(\frac{1+p_0}{2}) - H_{\rm bin}(p_0) -1 + p_0 = H_{\rm bin}(\frac{1+p_0}{2}) -1 + p_0.$$
$$ \Rightarrow \hspace{0.3cm} p_0 = 0.4 {\rm :}\hspace{0.5cm} I(X;Y) = H_{\rm bin}(0.7) - 0.6 = 0.881 - 0.6 \hspace{0.15cm} \underline {=0.281\,{\rm bit}}\hspace{0.05cm}.$$


(5)  Die Kanalkapazität  $C$  ist die Transinformation  $I(X; Y)$  bei bestmöglichen Wahrscheinlichkeiten  $p_0$  und   $p_1$  der Quellensymbole.

  • Nach Differentiation erhält man die Bestimmungsgleichung:
$$\frac{\rm d}{{\rm d}p_0} \hspace{0.1cm} I(X;Y) = \frac{\rm d}{{\rm d}p_0} \hspace{0.1cm} H_{\rm bin}(\frac{1+p_0}{2}) +1 \stackrel{!}{=} 0 \hspace{0.05cm}.$$
  • Mit dem Differentialquotienten der binären Entropiefunktion
$$ \frac{\rm d}{{\rm d}p} \hspace{0.1cm} H_{\rm bin}(p) = {\rm log}_2 \hspace{0.1cm} \frac{1-p}{ p} \hspace{0.05cm},$$
und entsprechendes Nachdifferenzieren erhält man:
$${1}/{2} \cdot {\rm log}_2 \hspace{0.1cm} \frac{(1-p_0)/2}{1- (1-p_0)/2} +1 \stackrel{!}{=} 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {1}/{2} \cdot {\rm log}_2 \hspace{0.1cm} \frac{(1-p_0)/2}{(1+p_0)/2} +1 \stackrel{!}{=} 0$$
$$ \Rightarrow \hspace{0.3cm} {\rm log}_2 \hspace{0.1cm} \frac{1+p_0}{1-p_0} \stackrel{!}{=} 2 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \frac{1+p_0}{1-p_0} \stackrel{!}{=} 4 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_0 \hspace{0.15cm} \underline {=0.6}\hspace{0.05cm}.$$


(6)  Für die Kanalkapazität gilt dementsprechend:

$$C = I(X;Y) \big |_{p_0 \hspace{0.05cm}=\hspace{0.05cm} 0.6} = H_{\rm bin}(0.8) - 0.4 = 0.722 -0.4 \hspace{0.15cm} \underline {=0.322\,{\rm bit}}\hspace{0.05cm}.$$
  • In der Aufgabe A3.14 wird dieses Ergebnis im Vergleich zum BSC–Kanalmodell interpretiert.



(7)  Für die Äquivokation gilt:

$$ H(X \hspace{-0.1cm}\mid \hspace{-0.1cm}Y) = H(X) - I(X;Y) = 0.971 -0.322 \hspace{0.15cm} \underline {=0.649\,{\rm bit}}\hspace{0.05cm}.$$
  • Wegen  $H_{\rm bin}(0.4) = H_{\rm bin}(0.6)$  ergibt sich die gleiche Quellenentropie  $H(X)$  wie in Teilaufgabe  (1).
  • Die Sinkenentropie muss neu berechnet werden.  Mit  $p_0 = 0.6$  erhält man  $H(Y) = H_{\rm bin}(0.8) = 0.722\ \rm bit$.
  • Damit ergibt sich für die Irrelevanz:
$$H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = H(Y) - I(X;Y) = 0.722 -0.322 \hspace{0.15cm} \underline {=0.400\,{\rm bit}}\hspace{0.05cm}.$$