Exercise 3.11: Erasure Channel

Auslöschungskanal mit vier Eingängen und fünf Ausgängen

Betrachtet wird ein Auslöschungskanal mit

den M Eingängen $x ∈ X = \{1, 2, \ \text{...} \ , M\}$, und
den $M + 1$ Ausgängen $y ∈ Y = \{1, 2, \ \text{...} \ , M, \text{E}\}.$

Die Grafik zeigt das Modell für den Sonderfall $M = 4$. Das Sinkensymbol $y = \text{E}$ berücksichtigt eine Auslöschung (englisch: Erasure ) für den Fall, dass der Empfänger keine hinreichend gesicherte Entscheidung treffen kann.

Die Übergangswahrscheinlichkeiten sind für $1 ≤ μ ≤ M$ wie folgt gegeben:

$${\rm Pr}(Y \hspace{-0.05cm} = \mu\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= \mu) = 1-\lambda \hspace{0.05cm},$$

$${\rm Pr}(Y \hspace{-0.05cm} = {\rm E}\hspace{-0.05cm}\mid \hspace{-0.05cm} X \hspace{-0.05cm}= \mu) = \lambda \hspace{0.05cm}.$$

Gesucht werden:

die Kapazität $C_{M\rm –EC}$ dieses M–ary Erasure Channels,
die Kapazität $C_{\rm BEC}$ des Binary Erasure Channels als Sonderfall des obigen Modells,

Hinweise:

Die Aufgabe gehört zum Kapitel Anwendung auf die Digitalsignalübertragung.
Bezug genommen wird insbesondere auf die Seite Informationstheoretisches Modell der Digitalsignalübertragung.
Im obigen Schaubild sind Auslöschungen (mit Wahrscheinlichkeit $λ$) blau gezeichnet.
„Richtige Übertragungswege” (also von $X = μ$ nach $Y = μ$) sind blau dargestellt ($1 ≤ μ ≤ M$).

Fragebogen

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

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

$H(Y) \ = \ $

$\ \rm bit$

$H(Y|X) \ = \ $

$\ \rm bit$

$M = 4\text{:} \ \ C\ = \ $

$\ \rm bit$

$M = 2\text{:} \ \ C\ = \ $

$\ \rm bit$

	$C_{\rm BEC} = 1 – λ,$
	$C_{\rm BEC} = 1 – H_{\rm bin}(λ).$

Musterlösung

Solution

(1) Richtig ist also der Lösungsvorschlag 2:

Aufgrund der Symmetrie der Übergangswahrscheinlichkeiten $P_{Y|X}(Y|X)$ ist offensichtlich, dass eine Gleichverteilung zur maximalen Transinformation $I(X; Y)$ und damit zur Kanalkapazität $C$ führen wird:

$$ P_X(X) = P_X\big ( \hspace{0.03cm}X\hspace{-0.03cm}=1\hspace{0.03cm}, \hspace{0.03cm} X\hspace{-0.03cm}=2\hspace{0.03cm},\hspace{0.03cm}...\hspace{0.08cm}, X\hspace{-0.03cm}=M\hspace{0.03cm}\big ) = \big [\hspace{0.03cm}1/M\hspace{0.03cm}, \hspace{0.03cm} 1/M\hspace{0.03cm},\hspace{0.03cm}...\hspace{0.08cm}, 1/M\hspace{0.03cm}\big ]\hspace{0.05cm}$$

Im Sonderfall $M = 2$ wäre auch $P_X(X) = (0.5, 0.5)$ richtig.

(2) Zutreffend ist dementsprechend der Lösungsvorschlag 3, also genau $2M$ Verbindungen. Da:

Von jedem Quellensymbol $X = μ$ kommt man sowohl zum Sinkensymbol $Y = μ$ als auch zum Erasure $Y = \text{E}$.

(3) Alle Wahrscheinlichkeiten $Pr(Y = 1), \hspace{0.05cm} \text{...}\hspace{0.05cm} , Pr(Y = M)$ sind gleich groß. Damit erhält man für $μ = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , M$:

$${\rm Pr}(Y \hspace{-0.05cm} = \mu) = ( 1-\lambda)/M \hspace{0.05cm}$$

Außerdem kommt man von jedem Quellensymbol $X = 1, \hspace{0.05cm} \text{...}\hspace{0.05cm} , X = M$ auch zum Erasure $Y = \text{E}$:

$${\rm Pr}(Y \hspace{-0.05cm} = {\rm E}) = \lambda \hspace{0.05cm}$$

Die Kontrolle ergibt, dass die Summe aller $M + 1$ Sinkensymbolwahrscheinlichkeiten tatsächlich $1$ ergibt. Daraus folgt für die Sinkenentropie

$$H(Y) = M \cdot \frac{ 1-\lambda }{M} \cdot {\rm log}_2 \hspace{0.1cm} \frac{M}{1 - \lambda} \hspace{0.15cm}+\hspace{0.15cm} \lambda \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{\lambda} \hspace{0.05cm}.$$

Zusammengefasst ergibt dies mit der binären Entropiefunktion:

$$H(Y) = (1-\lambda) \cdot {\rm log}_2 \hspace{0.1cm} M \hspace{0.15cm}+\hspace{0.15cm} H_{\rm bin} (\lambda ) \hspace{0.05cm}$$

und mit $M = 4$ sowie$ λ = 0.2$:

$$H(Y) = 1.6 \,{\rm bit} + H_{\rm bin} (0.2 ) \hspace{0.15cm} \underline {=2.322\,{\rm bit}} \hspace{0.05cm}$$

(4) Für die $2M$ Verbundwahrscheinlichkeiten ⇒ ${\rm Pr} [(X = μ) ∩ (Y = κ)] ≠ 0$ und die zugehörigen bedingten Wahrscheinlichkeiten ⇒ $pκ|μ = {\rm Pr}(Y = κ|X = μ)$ gilt:

Die Kombination $p_{μκ} = (1 – λ)/M$ und $p_{κ|μ} = 1 – λ$ kommt $M$ mal vor.
Die Kombination $p_{μκ} = λ/M$ und $p_{κ|μ} = λ$ kommt ebenfalls $M$ mal vor.

Daraus folgt:

$$ H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) \hspace{-0.15cm} =\hspace{-0.15cm} M \cdot \frac{ 1-\lambda }{M} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \lambda} \hspace{0.15cm}+\hspace{0.15cm}M \cdot \frac{ \lambda }{M} \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{ \lambda} = ( 1-\lambda) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1 - \lambda} \hspace{0.15cm}+\hspace{0.15cm} \lambda \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{ \lambda} = H_{\rm bin} (\lambda)\hspace{0.05cm}.$$

Das Ergebnis ist unabhängig von $M$. Mit $λ = 0.2$ erhält man: $$H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = H_{\rm bin} (0.2 ) \hspace{0.15cm} \underline {=0.722\,{\rm bit}} \hspace{0.05cm}$$

(5) Die Kanalkapazität $C$ ist gleich der maximalen Transinformation $I(X; Y)$, wobei die Maximierung hinsichtlich $P_X(X)$ bereits durch den symmetrischen Ansatz berücksichtigt wurde:

$$ C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) = ( 1-\lambda) \cdot {\rm log}_2 \hspace{0.1cm} M + H_{\rm bin} (\lambda) - H_{\rm bin} (\lambda) = ( 1-\lambda) \cdot {\rm log}_2 \hspace{0.1cm} M \hspace{0.05cm}$$

$$\Rightarrow \hspace{0.3cm} M = 4: \hspace{0.3cm} \underline {C=1.6\,\,{\rm bit}} \hspace{0.05cm}, \hspace{0.8cm} M \hspace{-0.15cm} =\hspace{-0.15cm} 2: \hspace{0.3cm} \underline {C=0.8\,\,{\rm bit}} \hspace{0.05cm}.$$

(6) Der Binary Erasure Channel (BEC) ist ein Sonderfall des hier betrachteten allgemeinen Modells mit $M = 2$:

$$C_{\rm BEC} = 1-\lambda \hspace{0.05cm}$$

Richtig ist somit der Lösungsvorschlag 1. Der zweite Lösungsvorschlag gilt dagegen für den Binary Symmetric Channel (BSC) mit der Verfälschungswahrscheinlichkeit $λ$.