Exercise 3.10Z: BSC Channel Capacity

Entropien der Kanalmodelle „BC” und „BSC”

Die Kanalkapazität $C$ wurde von Claude E. Shannon als die maximale Transinformation definiert, wobei sich die Maximierung allein auf die Quellenstatistik bezieht:

$$ C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}$$

Beim Binärkanal mit der Wahrscheinlichkeitsfunktion $P_X(X) = [p_0, p_1]$ ist nur ein Parameter optimierbar, beispielsweise $p_0$. Die Wahrscheinlichkeit für eine $1$ ist damit ebenfalls festgelegt: $p_1 = 1 – p_0.$

Die obere Grafik (rot hinterlegt) fasst die Ergebnisse für den unsymmetrischen Binärkanal mit $ε_0 = 0.01$ und $ε_1 = 0.2$ zusammen, der auch im Theorieteil betrachtet wurde. Die Maximierung führt zum Ergebnis $p_0 = 0.55$ ⇒ $p_1 = 0.45$, und man erhält für die Kanalkapazität:

$$C_{\rm BC} = \hspace{-0.05cm} \max_{P_X(X)} \hspace{0.1cm} I(X;Y) \big |_{p_0 \hspace{0.05cm} = \hspace{0.05cm}0.55} \hspace{0.05cm}=\hspace{0.05cm} 0.5779\,{\rm bit} \hspace{0.05cm}.$$

In der unteren Grafik (blaue Hinterlegung) sind die gleichen informationstheoretischen Größen für den symmetrischen Kanal ⇒ Binary Symmetric Channel (BSC) mit den Verfälschungswahrscheinlichkeiten $ε1 = ε2 = ε = 0.1$ angegeben, der auch für die Aufgabe 3.9 vorausgesetzt wurde.

In der vorliegenden Aufgabe sollen Sie für das BSC–Kanalmodell (zunächst für $ε = 0.1$)

die Entropien $H(X)$, $H(Y)$, $H(X|Y)$, $H(Y|X)$ analysieren,
den Quellenparameter $p_0$ hinsichtlich maximaler Transinformation $I(X; Y)$ optimieren,
somit die Kanalkapazität $C(ε)$ bestimmen, sowie
durch Verallgemeinerung eine geschlossene Gleichung für $C(ε)$ angeben.

Hinweise:

Die Aufgabe gehört zum Kapitel Anwendung auf die Digitalsignalübertragung.
Bezug genommen wird insbesondere auf die Seite Kanalkapazität eines Binärkanals.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

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. Aus der Tabelle auf der Angabenseite erkennt man, dass beim BSC–Modell (blaue Hinterlegung) wie auch beim allgemeineren (unsymmetrischen) BC–Modell (rote Hinterlegung) die Äquivokation $H(X|Y)$ von den Quellensymbolwahrscheinlichkeiten $p_0$ und $p_1$ abhängt. Daraus folgt, dass der Lösungsvorschlag 1 nicht richtig sein kann. Dagegen ist die Irrelevanz $H(Y|X)$ unabhängig von der Quellenstatistik, so dass auch der Lösungsvorschlag 3 ausgeschlossen werden kann.

Richtig ist vielmehr der Lösungsvorschlag 2, wie die folgende Rechnung zeigt: $$H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) \hspace{-0.15cm} =\hspace{-0.15cm} p_0 \cdot (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} + p_0 \cdot \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} +$$ $$ \hspace{-0.15cm} p_1 \cdot \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} + p_1 \cdot (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} =$$ $$=\hspace{-0.15cm} (p_0 + p_1) \cdot \left [ \varepsilon \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\varepsilon} + (1 - \varepsilon) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \varepsilon} \right ] \hspace{0.05cm}.$$ Mit $p_0 + p_1 = 1$n und der binären Entropiefunktion $\Rightarrow H_{bin}$ erhält man das vorgeschlagene Ergebnis: $$H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = H_{\rm bin}(\varepsilon)\hspace{0.05cm}$$ Für $ε = 0.1$ ergibt sich $H(Y|X) = 0.4690 bit$. Der gleiche Wert steht für alle $p_0$ in der gegebenen Tabelle. 2. Zutreffend sind hier alle vorgegebenen Lösungsalternativen. Die Kanalkapazität ist definiert als die maximale Transinformation, wobei die Maximierung hinsichtlich $P_X = (p_0, p_1)$ zu erfolgen hat: $$C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}$$ Diese Gleichung gilt allgemein, also auch für den rot hinterlegten unsymmetrischen Binärkanal (BC).

Die Transinformation kann zum Beispiel allgemein wie folgt berechnet werden: $$I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X)\hspace{0.05cm}$$

3.Die Grafik rechts zeigt die binäre Entropiefunktion und rechts die Kanalkapazität. Man erhält:

für $ε = 0$ (fehlerfreier Kanal): $C = 1 (bit) \Rightarrow$ Punkt mit gelber Füllung,
für $ε = 0.1$ (bisher betrachtet): $C = 0.531 (bit) ) \Rightarrow$ Punkt mit grüner Füllung,
für $ε = 0.5$ (vollkommen gestört): $C = 0 (bit) \Rightarrow$ Punkt mit grauer Füllung

4. Aus der Grafik erkennt man, dass aus informationstheoretischer Sicht $ε = 1$ gleich ist wie $ε = 0$ : $$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}1} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0} \hspace{0.15cm} \underline {=1\,{\rm (bit)}} \hspace{0.05cm}$$ Der Kanal nimmt hier nur eine Umbenennung vor. Man spricht von Mapping. Aus jeder $„0”$ wird eine $„1”$ und aus jeder $„1”$ eine $„0”$. Entsprechend gilt: $$C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.9} \hspace{0.05cm}= C_{\rm BSC} \big |_{\hspace{0.05cm}\varepsilon \hspace{0.05cm} = \hspace{0.05cm}0.1} \hspace{0.15cm} \underline {=0.531\,{\rm (bit)}} \hspace{0.05cm}$$