Aufgaben:Aufgabe 3.14: Kanalcodierungstheorem: Unterschied zwischen den Versionen

Shannons Kanalcodierungstheorem besagt, dass über einen diskreten gedächtnislosen Kanal (DMC) mit der Coderate $R$ fehlerfrei übertragen werden kann, so lange $R$ nicht größer ist als die Kanalkapazität $$C = \max_{P_X(X)} \hspace{0.15cm} I(X;Y) \hspace{0.05cm}.$$ Das Kanalcodierungstheorem soll in dieser Aufgabe numerisch ausgewertet werden, wobei zwei typische Kanalmodelle zu betrachten sind:

das $\text{BSC–Modell}$ (Binary Symmetric Channel) mit Verfälschungswahrscheinlichkeit $ε = 0.25$ und der Kanalkapazität $C = 1 – H_{bin}(ε),$
das sog. $\text{EUC–Modell}$ (Extremely Unsymmetric Channel) entsprechend der Aufgabe Z3.10 (diese Bezeichnung ist nicht allgemein üblich)

Hinweis: Diese Aufgabe gehört zum Themengebiet von Kapitel 3.3. Die Grafiken zeigen die numerischen Werte der informationstheoretischen Größen für die beiden Kanäle „BSC” und „EUC”:

der Quellenentropie $H(X),$
der Äquivokation $H(X|Y),$
der Transinformation $I(X; Y),$
der Irrelevanz $H(Y|X),$ und
der Sinkenentropie $H(Y).$

Der Parameter in diesen Tabellen ist $p_0 = Pr(X = 0)$ im Bereich von $0.3$ bis $0.7.$ Entsprechend gilt für die Wahrscheinlichkeit des Quellensymbols „1”: $p_1 = 1 – p_0$

Fragebogen

Musterlösung

1. Die BSC–Fehlerwahrscheinlichkeit ist mit $p_0 = p_1 = 0.5$ bei uncodierter Übertragung $(R = 1)$: $$ p_{\rm B} = 0.5 \cdot 0.25 + 0.5 \cdot 0.25=0.25 \hspace{0.05cm}.$$ Entsprechend gilt bei gleichen Randbedingungen für das EUC–Modell: $$ p_{\rm B} = 0.5 \cdot 0 + 0.5 \cdot 0.5=0.25 \hspace{0.05cm}.$$ Richtig ist demnach der Lösungsvorschlag 3.

2. Beim BSC–Modell mit der Verfälschungswahrscheinlichkeit $ε = 0.25$ gilt bei uncodierter Übertragung $(R = 1)$ unabhängig von $p_0$ und $p_1$ für die Bitfehlerwahrscheinlichkeit: $p_B = 0.25$. Dagegen erhält man beim EUC–Modell beispielsweise mit $p_0 = 0.6$ und $p_1 = 0.4$ eine kleinere Bitfehlerwahrscheinlichkeit: $$p_{\rm B} = 0.6 \cdot 0 + 0.4 \cdot 0.5=0.2 \hspace{0.05cm}.$$ Richtig ist demnach der Lösungsvorschlag 3.

Zu beachten ist jedoch, dass nun die Quellenentropie nicht mehr $H(X) = 1 (bit)$ beträgt, sondern nur mehr $H(X) = H_{bin} (0.6) = 0.971 (bit)$. Im Grenzfall $p_0 = 1$ werden nur noch Nullen übertragen und es gilt $H(X) = 0$. Für die Bitfehlerwahrscheinlichkeit gilt dann aber tatsächlich: $$ p_{\rm B} = 1 \cdot 0 + 0 \cdot 0.5=0 \hspace{0.05cm}.$$ Man überträgt also keine Information, diese aber mit der Bitfehlerwahrscheinlichkeit $0$

3.Aus der Grafik auf der Angabenseite lässt sich für die Kapazitäten der beiden Kanäle ablesen:

$C_{BSC} = 0.1887 bit/use,$
$C_{EUC} = 0.3219 bit/use.$

Nach dem Kanalcodierungstheorem kann unter der Bedingung $R ≤ C$ eine Kanalcodierung gefunden werden, mit der die Fehlerwahrscheinlichkeit zu $0$ gemacht werden kann. Bei beiden Kanälen trifft dies mit $R = 0.16$ zu $⇒$ Lösungsvorschlag 1.

4. Richtig ist hier der Lösungsvorschlag 3: Beim EUC–Modell wird mit $R = 0.32$ und $C = 0.3219$ die notwendige Bedingung $R ≤ C$ für eine fehlerfreie Übertragung erfüllt. Voraussetzung hierfür ist allerdings die Wahrscheinlichkeitsfunktion $P_X(X) = (0.6, 0.4).$ Dagegen ergäbe sich für gleichwahrscheinliche Symbole $ ⇒ P_X(X) = (0.5, 0.5)$ die Transinformation $I(X; Y) = 0.3113 < R.$

Man erkennt: Das EUC–Modell bietet mehr Potenzial für die Anwendung einer Kanalcodierung als das BSC–Modell. Hier kann beispielsweise im Code ausgenutzt werden, dass eine gesendete „0” stets fehlerfrei übertragen wird.

5. Aus der Kommentierung der Aufgaben (c) und (d) geht hervor, dass der Lösungsvorschlag 4 zutrifft.

@@ Zeile 23: / Zeile 23: @@
 <quiz display=simple>
-{Multiple-Choice Frage
+{Welche Aussagen gelten für uncodierte Übertragung $(R = 1)$, wenn man von $p_0 = p_1 = 0.5$ ausgeht?
 |type="[]"}
-- Falsch
+- Mit BSC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit.
-+ Richtig
+- Mit EUC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit.
++ Beide Modelle führen zur gleichen Bitfehlerwahrscheinlichkeit.
-{Input-Box Frage
+{Lässt sich bei $R = 1$ durch andere $p_0$, $p_1$ das Ergebnis (formal) verbessern?
-|type="{}"}
+|type="[]"}
-$\alpha$ = { 0.3 }
+- Bei beiden Kanälen.
+- Beim BSC–Modell.
++ Beim EUC–Modell.
+- Bei keinem Modell.
+{Über welchen Kanal lässt sich mit der Rate $R = 0.16$ fehlerfrei übertragen?
+|type="[]"}
++ Bei beiden Kanälen.
+- Beim BSC–Modell.
+- Beim EUC–Modell.
+- Bei keinem Modell.
+{Über welchen Kanal lässt sich mit der Rate $R = 0.32$ fehlerfrei übertragen?
+|type="[]"}
+- Bei beiden Kanälen.
+- Beim BSC–Modell.
++ Beim EUC–Modell.
+- Bei keinem Modell.
+{Über welchen Kanal lässt sich mit der Rate $R = 0.48$ fehlerfrei übertragen?
+|type="[]"}
+- Bei beiden Kanälen.
+- Beim BSC–Modell.
+- Beim EUC–Modell.
++ Bei keinem Modell.
 </quiz>
 ===Musterlösung===
 {{ML-Kopf}}
-'''1.'''
+'''1.''' Die BSC–Fehlerwahrscheinlichkeit ist mit $p_0 = p_1 = 0.5$ bei uncodierter Übertragung $(R = 1)$:
-'''2.'''
+$$ p_{\rm B} = 0.5 \cdot 0.25 + 0.5 \cdot 0.25=0.25 \hspace{0.05cm}.$$
-'''3.'''
+Entsprechend gilt bei gleichen Randbedingungen für das EUC–Modell:
-'''4.'''
+$$ p_{\rm B} = 0.5 \cdot 0 + 0.5 \cdot 0.5=0.25 \hspace{0.05cm}.$$
-'''5.'''
+Richtig ist demnach der Lösungsvorschlag 3.
-'''6.'''
-'''7.'''
+'''2.'''  Beim BSC–Modell mit der Verfälschungswahrscheinlichkeit $ε = 0.25$ gilt bei uncodierter Übertragung $(R = 1)$ unabhängig von $p_0$ und $p_1$ für die Bitfehlerwahrscheinlichkeit: $p_B = 0.25$. Dagegen erhält man beim EUC–Modell beispielsweise mit $p_0 = 0.6$ und $p_1 = 0.4$ eine  kleinere Bitfehlerwahrscheinlichkeit:
+$$p_{\rm B} = 0.6 \cdot 0 + 0.4 \cdot 0.5=0.2 \hspace{0.05cm}.$$
+Richtig ist demnach der Lösungsvorschlag 3.
+Zu beachten ist jedoch, dass nun die Quellenentropie nicht mehr $H(X) = 1 (bit)$ beträgt, sondern nur mehr $H(X) = H_{bin} (0.6) = 0.971 (bit)$. Im Grenzfall $p_0 = 1$ werden nur noch Nullen übertragen und es gilt $H(X) = 0$. Für die Bitfehlerwahrscheinlichkeit gilt dann aber tatsächlich:
+$$ p_{\rm B} = 1 \cdot 0 + 0 \cdot 0.5=0 \hspace{0.05cm}.$$
+Man überträgt also keine Information, diese aber mit der Bitfehlerwahrscheinlichkeit $0$
+'''3.'''Aus der Grafik auf der Angabenseite lässt sich für die Kapazitäten der beiden Kanäle ablesen:
+:* $C_{BSC} = 0.1887 bit/use,$
+:* $C_{EUC} = 0.3219 bit/use.$
+Nach dem Kanalcodierungstheorem kann unter der Bedingung $R ≤ C$ eine Kanalcodierung gefunden werden, mit der die Fehlerwahrscheinlichkeit zu $0$ gemacht werden kann. Bei beiden Kanälen trifft dies mit $R = 0.16$ zu  $⇒$  Lösungsvorschlag 1.
+'''4.''' Richtig ist hier der Lösungsvorschlag 3: Beim EUC–Modell wird mit $R = 0.32$ und $C = 0.3219$ die notwendige Bedingung $R ≤ C$ für eine fehlerfreie Übertragung erfüllt. Voraussetzung hierfür ist allerdings die Wahrscheinlichkeitsfunktion $P_X(X) = (0.6, 0.4).$ Dagegen ergäbe sich für gleichwahrscheinliche Symbole $ ⇒  P_X(X) = (0.5, 0.5)$ die Transinformation $I(X; Y) = 0.3113 < R.$
+Man erkennt: Das EUC–Modell bietet mehr Potenzial für die Anwendung einer Kanalcodierung als das BSC–Modell. Hier kann beispielsweise im Code ausgenutzt werden, dass eine gesendete „0” stets fehlerfrei übertragen wird.
+'''5.''' Aus der Kommentierung der Aufgaben (c) und (d) geht hervor, dass der Lösungsvorschlag 4 zutrifft.
 {{ML-Fuß}}

	Bei beiden Kanälen.
	Beim BSC–Modell.
	Beim EUC–Modell.
	Bei keinem Modell.

	Bei beiden Kanälen.
	Beim BSC–Modell.
	Beim EUC–Modell.
	Bei keinem Modell.

	Bei beiden Kanälen.
	Beim BSC–Modell.
	Beim EUC–Modell.
	Bei keinem Modell.

	Bei beiden Kanälen.
	Beim BSC–Modell.
	Beim EUC–Modell.
	Bei keinem Modell.

	Mit BSC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit.
	Mit EUC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit.
	Beide Modelle führen zur gleichen Bitfehlerwahrscheinlichkeit.

Aufgaben:Aufgabe 3.14: Kanalcodierungstheorem: Unterschied zwischen den Versionen

Version vom 28. November 2016, 23:56 Uhr

Fragebogen

Musterlösung

Musterlösung