Aufgaben:Aufgabe 3.11: Auslöschungskanal: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 5: Zeile 5:
 
[[Datei:P_ID2791__Inf_A_3_10.png|right|frame|Auslöschungskanal mit vier Eingängen und fünf Ausgängen]]
 
[[Datei:P_ID2791__Inf_A_3_10.png|right|frame|Auslöschungskanal mit vier Eingängen und fünf Ausgängen]]
 
Betrachtet wird ein Auslöschungskanal mit
 
Betrachtet wird ein Auslöschungskanal mit
* den M Eingängen $x ∈ X = \{1, 2, \ \text{...} \  , M\}$, und
+
* den  $M$  Eingängen  $x ∈ X = \{1,\ 2, \ \text{...} \  ,\ M\}$,  und
* den $M + 1$ Ausgängen $y ∈ Y = \{1, 2, \ \text{...} \  , M, \text{E}\}.$
+
* 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 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:
+
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} = \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}.$$
 
:$${\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:
 
Gesucht werden:
* die Kapazität  $C_{M\rm –EC}$  dieses ''M–ary Erasure Channels'',
+
* die Kapazität  $C_{M\rm –EC}$  dieses  "M–ary Erasure Channels",
* die Kapazität  $C_{\rm BEC}$  des [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channels]] als Sonderfall des obigen Modells,
+
* die Kapazität  $C_{\rm BEC}$  des  [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channels]]  $\rm (BEC)$  als Sonderfall des obigen Modells.
 +
 
 +
 
 +
 
  
  
Zeile 25: Zeile 28:
 
*Die Aufgabe gehört zum  Kapitel  [[Informationstheorie/Anwendung_auf_die_Digitalsignalübertragung|Anwendung auf die Digitalsignalübertragung]].
 
*Die Aufgabe gehört zum  Kapitel  [[Informationstheorie/Anwendung_auf_die_Digitalsignalübertragung|Anwendung auf die Digitalsignalübertragung]].
 
*Bezug genommen wird insbesondere auf die Seite     [[Informationstheorie/Anwendung_auf_die_Digitalsignalübertragung#Informationstheoretisches_Modell_der_Digitalsignal.C3.BCbertragung|Informationstheoretisches Modell der Digitalsignalübertragung]].
 
*Bezug genommen wird insbesondere auf die Seite     [[Informationstheorie/Anwendung_auf_die_Digitalsignalübertragung#Informationstheoretisches_Modell_der_Digitalsignal.C3.BCbertragung|Informationstheoretisches Modell der Digitalsignalübertragung]].
*Im obigen Schaubild sind Auslöschungen (mit Wahrscheinlichkeit $λ$) blau gezeichnet.
+
*Im obigen Schaubild sind Auslöschungen  $($mit Wahrscheinlichkeit  )$  blau gezeichnet.
* „Richtige Übertragungswege” (also von $X = μ$ nach $Y = μ$) sind blau dargestellt  ($1 ≤ μ ≤ M$).
+
* „Richtige Übertragungswege”  $($also von  $X = μ$  nach  $Y = μ)$  sind rot dargestellt  $(1 ≤ μ ≤ M)$.
 
   
 
   
  
Zeile 34: Zeile 37:
  
 
<quiz display=simple>
 
<quiz display=simple>
{ Welches $P_X(X)$ ist zur Kanalkapazitätsberechnung allgemein anzusetzen?
+
{ Welches&nbsp; $P_X(X)$&nbsp; ist zur Kanalkapazitätsberechnung allgemein anzusetzen?
 
|type="[]"}
 
|type="[]"}
 
- $P_X(X) = (0.5, \  0.5),$
 
- $P_X(X) = (0.5, \  0.5),$
+ $P_X(X) = (1/M, 1/M, \ \text{...} \ , 1/M),$
+
+ $P_X(X) = (1/M,\ 1/M, \ \text{...} \ ,\ 1/M),$
- $P_X(X) = (0.1, 0.2, 0.3, 0.4).$
+
- $P_X(X) = (0.1,\ 0.2,\ 0.3,\ 0.4).$
  
{Wie viele Wahrscheinlichkeiten $p_{μκ} = {\rm Pr}\big[(X = μ) ∩ (Y = κ)\big]$ sind ungleich Null?
+
{Wie viele Wahrscheinlichkeiten&nbsp; $p_{μκ} = {\rm Pr}\big[(X = μ) ∩ (Y = κ)\big]$&nbsp; sind ungleich Null?
|type="[]"}
+
|type="()"}
- Genau $M · (M + 1)$,
+
- Genau&nbsp; $M · (M + 1)$,
- Genau $M$,
+
- Genau&nbsp; $M$,
+ Genau $2 · M$.
+
+ Genau&nbsp; $2 · M$.
  
  
Zeile 51: Zeile 54:
 
$H(Y) \ = \ $  { 2.322 3% } $\ \rm bit$
 
$H(Y) \ = \ $  { 2.322 3% } $\ \rm bit$
  
{Berechnen Sie die Irrelevanz. Welcher Wert ergibt sich für &nbsp;$M = 4$&nbsp; und &nbsp;$λ = 0.2$?
+
{Berechnen Sie die Irrelevanz.&nbsp; Welcher Wert ergibt sich für &nbsp;$M = 4$&nbsp; und &nbsp;$λ = 0.2$?
 
|type="{}"}
 
|type="{}"}
 
$H(Y|X) \ = \ $ { 0.722 3% } $\ \rm bit$
 
$H(Y|X) \ = \ $ { 0.722 3% } $\ \rm bit$
Zeile 61: Zeile 64:
  
 
{Wie lautet die Kanalkapazität des BEC–Kanals in kompakter Form?  
 
{Wie lautet die Kanalkapazität des BEC–Kanals in kompakter Form?  
|type="[]"}
+
|type="()"}
 
+ $C_{\rm BEC} = 1 - λ,$
 
+ $C_{\rm BEC} = 1 - λ,$
 
- $C_{\rm BEC} = 1 - H_{\rm bin}(λ).$
 
- $C_{\rm BEC} = 1 - H_{\rm bin}(λ).$
Zeile 72: Zeile 75:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  Richtig ist also der <u>Lösungsvorschlag 2:</u>
+
'''(1)'''&nbsp;  Richtig ist der <u>Lösungsvorschlag 2:</u>
* 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:
+
* Aufgrund der Symmetrie der Übergangswahrscheinlichkeiten&nbsp; $P_{Y|X}(Y|X)$&nbsp; ist offensichtlich, dass eine Gleichverteilung zur maximalen Transinformation&nbsp; $I(X; Y)$&nbsp; und damit zur Kanalkapazität&nbsp; $C$&nbsp; führen wird:
:$$ P_X(X) = P_X\big ( \hspace{0.03cm}X\hspace{-0.03cm}=1\hspace{0.03cm}, \hspace{0.08cm} X\hspace{-0.03cm}=2\hspace{0.03cm},\hspace{0.08cm}\text{...}\hspace{0.08cm}, X\hspace{-0.03cm}=M\hspace{0.03cm}\big ) = \big [\hspace{0.03cm}1/M\hspace{0.03cm}, \hspace{0.08cm} 1/M\hspace{0.03cm},\hspace{0.03cm}\text{...}\hspace{0.08cm},\hspace{0.08cm} 1/M\hspace{0.03cm}\big ]\hspace{0.05cm}$$
+
:$$ P_X(X) = P_X\big ( \hspace{0.03cm}X\hspace{-0.03cm}=1\hspace{0.03cm}, \hspace{0.08cm} X\hspace{-0.03cm}=2\hspace{0.03cm},\hspace{0.08cm}\text{...}\hspace{0.08cm}, X\hspace{-0.03cm}=M\hspace{0.03cm}\big ) = \big [\hspace{0.03cm}1/M\hspace{0.03cm}, \hspace{0.08cm} 1/M\hspace{0.03cm},\hspace{0.03cm}\text{...}\hspace{0.08cm},\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.
+
*Im Sonderfall&nbsp; $M = 2$&nbsp; wäre auch&nbsp; $P_X(X) = (0.5, \ 0.5)$&nbsp; richtig.
  
  
  
'''(2)'''&nbsp;  Zutreffend ist dementsprechend der <u>Lösungsvorschlag 3</u>, also genau $2M$ Verbindungen. Da:
+
'''(2)'''&nbsp;  Zutreffend ist der <u>Lösungsvorschlag 3</u>, also genau&nbsp; $2M$&nbsp; Verbindungen.&nbsp; Da:
*Von jedem Quellensymbol $X = μ$ kommt man sowohl zum Sinkensymbol $Y = μ$ als auch zum Erasure $Y = \text{E}$.
+
*Von jedem Quellensymbol&nbsp; $X = μ$&nbsp; kommt man sowohl zum Sinkensymbol&nbsp; $Y = μ$&nbsp; als auch zum Erasure&nbsp; $Y = \text{E}$.
  
 
   
 
   
  
'''(3)'''&nbsp;  Alle Wahrscheinlichkeiten $Pr(Y = 1), \hspace{0.05cm} \text{...}\hspace{0.05cm} , \hspace{0.08cm}Pr(Y = M)$ sind gleich groß. Damit erhält man für $μ = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \hspace{0.08cm} M$:
+
'''(3)'''&nbsp;  Alle Wahrscheinlichkeiten&nbsp; ${\rm Pr}(Y = 1), \hspace{0.05cm} \text{...}\hspace{0.05cm} , \hspace{0.08cm}{\rm Pr}(Y = M)$&nbsp; sind gleich groß.&nbsp; Damit erhält man für&nbsp; $μ = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \hspace{0.08cm} M$:
:$${\rm Pr}(Y \hspace{-0.05cm} = \mu) = ( 1-\lambda)/M \hspace{0.05cm}$$
+
:$${\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}$:
+
*Außerdem kommt man von jedem Quellensymbol&nbsp; $X = 1, \hspace{0.05cm} \text{...}\hspace{0.05cm}  , X = M$&nbsp; auch zum Erasure&nbsp; $Y = \text{E}$:
:$${\rm Pr}(Y \hspace{-0.05cm} = {\rm E}) = \lambda \hspace{0.05cm}$$
+
:$${\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
+
*Die Kontrolle ergibt, dass die Summe aller&nbsp; $M + 1$&nbsp; Sinkensymbolwahrscheinlichkeiten tatsächlich&nbsp; $1$&nbsp; ergibt.&nbsp;
 +
*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}.$$
 
:$$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:
 
*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}$$
 
:$$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$&nbsp; &nbsp;sowie&nbsp; $ λ = 0.2$:
+
:und mit&nbsp; $M = 4$&nbsp; &nbsp;sowie&nbsp; $ λ = 0.2$:
 
:$$H(Y) = 1.6 \,{\rm bit} + H_{\rm bin} (0.2 ) \hspace{0.15cm} \underline {=2.322\,{\rm bit}} \hspace{0.05cm}.$$
 
:$$H(Y) = 1.6 \,{\rm bit} + H_{\rm bin} (0.2 ) \hspace{0.15cm} \underline {=2.322\,{\rm bit}} \hspace{0.05cm}.$$
  
  
'''(4)'''&nbsp;  Für die $2M$ Verbundwahrscheinlichkeiten &nbsp; &rArr; &nbsp; ${\rm Pr} \big[(X = μ) ∩ (Y = κ)\big] ≠ 0$ und die bedingten Wahrscheinlichkeiten &nbsp; &rArr; &nbsp;  $pκ|μ = {\rm Pr}(Y = κ|X = μ)$ gilt:
+
 
* Die Kombination $p_{μκ} = (1 – λ)/M$  &nbsp;und&nbsp;  $p_{κ|μ} = 1 – λ$ kommt $M$ mal vor.
+
'''(4)'''&nbsp;  Die&nbsp; $2M$&nbsp; Verbundwahrscheinlichkeiten
* Die Kombination $p_{μκ} = λ/M$  &nbsp;und&nbsp;  $p_{κ|μ} = λ$ kommt ebenfalls $M$ mal vor.
+
:$${\rm Pr} \big[(X = μ) ∩ (Y = κ)\big] ≠ 0$$
 +
:und die bedingten Wahrscheinlichkeiten  
 +
:$$pκ|μ = {\rm Pr}(Y = κ|X = μ)$$
 +
:zeigen folgende Eigenschaften:  
 +
#&nbsp; Die Kombination&nbsp; $p_{μκ} = (1 – λ)/M$  &nbsp;und&nbsp;  $p_{κ|μ} = 1 – λ$&nbsp; kommt&nbsp; $M$&nbsp; mal vor.
 +
#&nbsp; Die Kombination&nbsp; $p_{μκ} = λ/M$  &nbsp;und&nbsp;  $p_{κ|μ} = λ$&nbsp; kommt ebenfalls $M$ mal vor.
  
  
 
Daraus folgt:
 
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}.$$
+
:$$ H(Y \hspace{-0.15cm}\mid \hspace{-0.15cm} X) \hspace{-0.01cm}  =\hspace{-0.01cm} 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:
+
*Das Ergebnis ist unabhängig von&nbsp; $M$.&nbsp; Mit&nbsp; $λ = 0.2$&nbsp; 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}.$$
 
:$$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)'''&nbsp;  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:
+
'''(5)'''&nbsp;  Die Kanalkapazität&nbsp; $C$&nbsp; ist gleich der maximalen Transinformation&nbsp; $I(X; Y)$,&nbsp; wobei die Maximierung hinsichtlich&nbsp; $P_X(X)$&nbsp; 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}$$
 
:$$ 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}
+
:$$\Rightarrow \hspace{0.3cm} M = 4\text{:} \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}.$$
+
M = 2\text{:} \hspace{0.3cm} \underline {C=0.8\,\,{\rm bit}} \hspace{0.05cm}.$$
 +
 
  
  
'''(6)'''&nbsp;  Der ''Binary Erasure Channel'' (BEC) ist ein Sonderfall des hier betrachteten allgemeinen Modells mit $M = 2$:
+
'''(6)'''&nbsp;  Der&nbsp; "Binary Erasure Channel"&nbsp; $\rm (BEC)$&nbsp; ist ein Sonderfall des hier betrachteten allgemeinen Modells mit&nbsp; $M = 2$:
:$$C_{\rm BEC} = 1-\lambda \hspace{0.05cm}$$
+
:$$C_{\rm BEC} = 1-\lambda \hspace{0.05cm}.$$
 
*Richtig ist somit der <u>Lösungsvorschlag 1</u>.  
 
*Richtig ist somit der <u>Lösungsvorschlag 1</u>.  
*Der zweite Lösungsvorschlag gilt dagegen für den ''Binary Symmetric Channel'' (BSC) mit der Verfälschungswahrscheinlichkeit $λ$.
+
*Der zweite Lösungsvorschlag gilt dagegen für den&nbsp; "Binary Symmetric Channel"&nbsp; $\rm (BSC)$&nbsp; mit der Verfälschungswahrscheinlichkeit&nbsp; $λ$.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 22. September 2021, 12:31 Uhr

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  $\rm (BEC)$  als Sonderfall des obigen Modells.





Hinweise:



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, \ \text{...} \ ,\ 1/M),$
$P_X(X) = (0.1,\ 0.2,\ 0.3,\ 0.4).$

2

Wie viele Wahrscheinlichkeiten  $p_{μκ} = {\rm Pr}\big[(X = μ) ∩ (Y = κ)\big]$  sind ungleich Null?

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

3

Wie groß ist die Sinkenentropie allgemein und für  $M = 4$  und  $λ = 0.2$?

$H(Y) \ = \ $

$\ \rm bit$

4

Berechnen Sie die Irrelevanz.  Welcher Wert ergibt sich für  $M = 4$  und  $λ = 0.2$?

$H(Y|X) \ = \ $

$\ \rm bit$

5

Wie groß ist die Kanalkapazität  $C$  in Abhängigkeit von  $M$?

$M = 4\text{:} \hspace{0.5cm} C\ = \ $

$\ \rm bit$
$M = 2\text{:} \hspace{0.5cm} C\ = \ $

$\ \rm bit$

6

Wie lautet die Kanalkapazität des BEC–Kanals in kompakter Form?

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


Musterlösung

(1)  Richtig ist 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.08cm} X\hspace{-0.03cm}=2\hspace{0.03cm},\hspace{0.08cm}\text{...}\hspace{0.08cm}, X\hspace{-0.03cm}=M\hspace{0.03cm}\big ) = \big [\hspace{0.03cm}1/M\hspace{0.03cm}, \hspace{0.08cm} 1/M\hspace{0.03cm},\hspace{0.03cm}\text{...}\hspace{0.08cm},\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 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  ${\rm Pr}(Y = 1), \hspace{0.05cm} \text{...}\hspace{0.05cm} , \hspace{0.08cm}{\rm Pr}(Y = M)$  sind gleich groß.  Damit erhält man für  $μ = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \hspace{0.08cm} 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)  Die  $2M$  Verbundwahrscheinlichkeiten

$${\rm Pr} \big[(X = μ) ∩ (Y = κ)\big] ≠ 0$$
und die bedingten Wahrscheinlichkeiten
$$pκ|μ = {\rm Pr}(Y = κ|X = μ)$$
zeigen folgende Eigenschaften:
  1.   Die Kombination  $p_{μκ} = (1 – λ)/M$  und  $p_{κ|μ} = 1 – λ$  kommt  $M$  mal vor.
  2.   Die Kombination  $p_{μκ} = λ/M$  und  $p_{κ|μ} = λ$  kommt ebenfalls $M$ mal vor.


Daraus folgt:

$$ H(Y \hspace{-0.15cm}\mid \hspace{-0.15cm} X) \hspace{-0.01cm} =\hspace{-0.01cm} 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\text{:} \hspace{0.3cm} \underline {C=1.6\,\,{\rm bit}} \hspace{0.05cm}, \hspace{0.8cm} M = 2\text{:} \hspace{0.3cm} \underline {C=0.8\,\,{\rm bit}} \hspace{0.05cm}.$$


(6)  Der  "Binary Erasure Channel"  $\rm (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"  $\rm (BSC)$  mit der Verfälschungswahrscheinlichkeit  $λ$.