Exercise 3.11Z: Extremely Asymmetrical Channel

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:

Die Aufgabe gehört zum Kapitel Anwendung auf die Digitalsignalübertragung.
Bezug genommen wird insbesondere auf die Seite Kanalkapazität eines Binärkanals.
In der Aufgabe 3.14 sollen die hier gefundenen Ergebnisse im Vergleich zum BSC–Kanal interpretiert werden.

Fragebogen

$H(X) \ = \ $

$\ \rm bit$

$H(Y) \ = \ $

$\ \rm bit$

$H(XY) \ = \ $

$\ \rm bit$

$I(X; Y) \ = \ $

$\ \rm bit$

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

$C \ = \ $

$\ \rm bit$

$H(X|Y) \ = \ $

$\ \rm bit$

$H(Y|X) \ = \ $

$\ \rm bit$

Musterlösung

Solution

(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$, und 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}.$$