Aufgaben:Exercise 3.10Z: BSC Channel Capacity

• Return to book

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

1

Welches $P_X(X)$ ist zur Kanalkapazitätsberechnung allgemein anzusetzen?

	$P_X(X) = (0.5, 0.5)$
	$P_X(X) = (1/M, 1/M, ... , 1/M)$
	$P_X(X) = (0.1, 0.2, 0.3, 0.4)$

2

Wie viele Wahrscheinlichkeiten $p_{μκ} = Pr[(X = μ) ∩ (Y = κ)]$ sind $≠ 0$?

	Genau $M · (M + 1)$
	Genau $M$
	Genau $2 · M$

3

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

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

4

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

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

5

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

$H(XY) \ = \ $ $\ \rm bit$

6

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

$I(X; Y) \ = \ $ $\ \rm bit$

7

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

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

8

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

$C \ = \ $ $\ \rm bit$

9

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

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}$$