Aufgaben:Aufgabe 3.14: Kanalcodierungstheorem: Unterschied zwischen den Versionen
Aus LNTwww
| (5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
}} | }} | ||
| − | [[Datei:P_ID2817__Inf_A_3_13.png|right|frame|Informationstheoretische Größen von | + | [[Datei:P_ID2817__Inf_A_3_13.png|right|frame|Informationstheoretische Größen von $\rm BSC$– und $\rm EUC–Modell$]] |
| − | [https://de.wikipedia.org/wiki/Claude_Shannon Shannons] Kanalcodierungstheorem besagt, dass über einen | + | [https://de.wikipedia.org/wiki/Claude_Shannon Shannons] Kanalcodierungstheorem besagt, dass über einen „diskreten gedächtnislosen Kanal” (englisch: "Discrete Memoryless Channel", $\rm 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}.$$ | :$$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 Kanalcodierungstheorem soll in dieser Aufgabe numerisch ausgewertet werden, wobei zwei typische Kanalmodelle zu betrachten sind: | ||
| − | * | + | * Das $\rm BSC$–Modell ("Binary Symmetric Channel") mit Verfälschungswahrscheinlichkeit $ε = 0.25$ und der Kanalkapazität $C = 1 - H_{\rm bin}(ε),$ |
| − | * das | + | * das $\rm EUC$–Modell (von "Extremely Unsymmetric Channel"; diese Bezeichnung stammt von uns und ist nicht allgemein üblich) entsprechend der [[Aufgaben:Aufgabe_3.11Z:_Extrem_unsymmetrischer_Kanal|Aufgabe 3.11Z]]. |
| − | Die Grafiken zeigen die numerischen Werte der informationstheoretischen Größen für die beiden | + | Die Grafiken zeigen die numerischen Werte der informationstheoretischen Größen für die beiden Modelle $\rm BSC$ und $\rm EUC$: |
| − | * | + | * Die Quellenentropie $H(X),$ |
| − | * die Äquivokation $H(X|Y),$ | + | * die Äquivokation $H(X|Y),$ |
| − | * die Transinformation $I(X; Y),$ | + | * die Transinformation $I(X; Y),$ |
| − | * die Irrelevanz $H(Y|X),$ und | + | * die Irrelevanz $H(Y|X),$ und |
| − | * die Sinkenentropie $H(Y).$ | + | * die Sinkenentropie $H(Y).$ |
| + | |||
| + | |||
| + | Der Parameter in diesen Tabellen ist $p_0 = {\rm Pr}(X = 0)$ im Bereich zwischen $p_0 = 0.3$ bis $p_0 = 0.7$. <br>Für die zweite Quellensymbolwahrscheinlichkeit gilt: $p_1 = {\rm Pr}(X = 1) =1 - p_0$. | ||
| + | |||
| − | |||
| Zeile 35: | Zeile 38: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Welche Aussagen gelten für uncodierte Übertragung ⇒ $R = 1$, wenn man von $p_0 = p_1 = 0.5$ ausgeht? | + | {Welche Aussagen gelten für uncodierte Übertragung ⇒ $\underline{R = 1}$, wenn man von $p_0 = p_1 = 0.5$ ausgeht? |
|type="()"} | |type="()"} | ||
- Mit BSC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit. | - Mit BSC ergibt sich eine kleinere Bitfehlerwahrscheinlichkeit. | ||
| Zeile 41: | Zeile 44: | ||
+ Beide Modelle führen zur gleichen Bitfehlerwahrscheinlichkeit. | + Beide Modelle führen zur gleichen Bitfehlerwahrscheinlichkeit. | ||
| − | {Lässt sich bei $\underline{R = 1}$ durch andere $p_0$ bzw. $p_1$ das Ergebnis (formal) verbessern? | + | {Lässt sich bei $\underline{R = 1}$ durch andere Werte von $p_0$ bzw. $p_1$ das Ergebnis (formal) verbessern? |
|type="()"} | |type="()"} | ||
- Bei beiden Kanälen. | - Bei beiden Kanälen. | ||
| Zeile 48: | Zeile 51: | ||
- Bei keinem Modell. | - Bei keinem Modell. | ||
| − | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.16}$ fehlerfrei übertragen? | + | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.16}$ fehlerfrei übertragen? |
| − | |type=" | + | |type="()"} |
+ Bei beiden Kanälen. | + Bei beiden Kanälen. | ||
- Beim BSC–Modell. | - Beim BSC–Modell. | ||
| Zeile 55: | Zeile 58: | ||
- Bei keinem Modell. | - Bei keinem Modell. | ||
| − | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.32}$ fehlerfrei übertragen? | + | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.32}$ fehlerfrei übertragen? |
|type="()"} | |type="()"} | ||
- Bei beiden Kanälen. | - Bei beiden Kanälen. | ||
| Zeile 62: | Zeile 65: | ||
- Bei keinem Modell. | - Bei keinem Modell. | ||
| − | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.48}$ fehlerfrei übertragen? | + | {Über welchen Kanal lässt sich mit der Rate $\underline{R = 0.48}$ fehlerfrei übertragen? |
|type="()"} | |type="()"} | ||
- Bei beiden Kanälen. | - Bei beiden Kanälen. | ||
| Zeile 73: | Zeile 76: | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
'''(1)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | '''(1)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | ||
| − | *Die BSC–Fehlerwahrscheinlichkeit ist mit $p_0 = p_1 = 0.5$ bei uncodierter Übertragung ⇒ nbsp; $R = 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}.$$ | :$$ 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: | + | *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}.$$ | :$$ p_{\rm B} = 0.5 \cdot 0 + 0.5 \cdot 0.5=0.25 \hspace{0.05cm}.$$ | ||
| + | |||
'''(2)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | '''(2)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | ||
| − | *Beim BSC–Modell mit der Verfälschungswahrscheinlichkeit $ε = 0.25$ | + | *Beim BSC–Modell mit der Verfälschungswahrscheinlichkeit $ε = 0.25$ ist bei uncodierter Übertragung ⇒ $R = 1$ unabhängig von $p_0$ und $p_1$ die Bitfehlerwahrscheinlichkeit gleich $p_{\rm 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}.$$ | :$$p_{\rm B} = 0.6 \cdot 0 + 0.4 \cdot 0.5=0.2 \hspace{0.05cm}.$$ | ||
| − | *Zu beachten ist jedoch, dass nun die Quellenentropie nicht mehr $H(X) = 1\ \rm (bit)$ beträgt, sondern nur mehr $H(X) = H_{bin} (0.6) = 0.971 \ \rm (bit)$. | + | *Zu beachten ist jedoch, dass nun die Quellenentropie nicht mehr $H(X) = 1\ \rm (bit)$ beträgt, sondern nur mehr $H(X) = H_{bin} (0.6) = 0.971 \ \rm (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: | + | *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}.$$ | :$$ p_{\rm B} = 1 \cdot 0 + 0 \cdot 0.5=0 \hspace{0.05cm}.$$ | ||
| − | :Man überträgt also keinerlei Information, diese aber mit der Bitfehlerwahrscheinlichkeit | + | :Man überträgt also keinerlei Information, diese aber mit der Bitfehlerwahrscheinlichkeit „Null”. |
| + | |||
'''(3)''' Richtig ist der <u>Lösungsvorschlag 1</u>: | '''(3)''' Richtig ist der <u>Lösungsvorschlag 1</u>: | ||
*Aus der Grafik auf der Angabenseite lässt sich für die Kapazitäten der beiden Kanäle ablesen: | *Aus der Grafik auf der Angabenseite lässt sich für die Kapazitäten der beiden Kanäle ablesen: | ||
| − | :$$C_{\rm BSC} = 0.1887 \ \rm {bit/use}, \hspace{0.5cm} | + | :$$C_{\rm BSC} = 0.1887 \ \rm {bit/use}, \hspace{0.5cm}C_{\rm EUC} = 0.3219 \ \rm {bit/use}.$$ |
| − | *Nach dem Kanalcodierungstheorem kann | + | *Nach dem Kanalcodierungstheorem kann bei $R ≤ C$ eine Kanalcodierung gefunden werden, mit der die Fehlerwahrscheinlichkeit zu Null gemacht werden kann. |
| + | *Bei beiden Kanälen trifft diese Bedingung mit der Rate $R = 0.16$ zu. | ||
| + | |||
'''(4)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | '''(4)''' Richtig ist der <u>Lösungsvorschlag 3</u>: | ||
| − | *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).$ | + | *Beim EUC–Modell wird mit $R = 0.32$ und $C = 0.3219$ die notwendige Bedingung $R ≤ C$ für eine fehlerfreie Übertragung erfüllt. |
| − | *Dagegen ergäbe sich für gleichwahrscheinliche Symbole ⇒ nbsp; $P_X(X) = (0.5, 0.5)$ die Transinformation $I(X; Y) = 0.3113$, also ein kleinerer Wert als für die Kanalkapazität $C$, und es gilt auch $I(X; Y) < R$. | + | *Voraussetzung hierfür ist allerdings die Wahrscheinlichkeitsfunktion $P_X(X) = (0.6,\ 0.4).$ |
| − | *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. | + | *Dagegen ergäbe sich für gleichwahrscheinliche Symbole ⇒ $P_X(X) = (0.5,\ 0.5)$ die Transinformation $I(X; Y) = 0.3113$, <br>also ein kleinerer Wert als für die Kanalkapazität $C$, und es gilt auch $I(X; Y) < 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 Teilaufgaben (3) und (4) geht hervor, dass der <u>Lösungsvorschlag 4</u> zutrifft. | + | '''(5)''' Aus der Kommentierung der Teilaufgaben '''(3)''' und '''(4)''' geht hervor, dass der <u>Lösungsvorschlag 4</u> zutrifft. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 24. September 2021, 11:17 Uhr
Informationstheoretische Größen von $\rm BSC$– und $\rm EUC–Modell$
Shannons Kanalcodierungstheorem besagt, dass über einen „diskreten gedächtnislosen Kanal” (englisch: "Discrete Memoryless Channel", $\rm 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 $\rm BSC$–Modell ("Binary Symmetric Channel") mit Verfälschungswahrscheinlichkeit $ε = 0.25$ und der Kanalkapazität $C = 1 - H_{\rm bin}(ε),$
- das $\rm EUC$–Modell (von "Extremely Unsymmetric Channel"; diese Bezeichnung stammt von uns und ist nicht allgemein üblich) entsprechend der Aufgabe 3.11Z.
Die Grafiken zeigen die numerischen Werte der informationstheoretischen Größen für die beiden Modelle $\rm BSC$ und $\rm EUC$:
- Die Quellenentropie $H(X),$
- die Äquivokation $H(X|Y),$
- die Transinformation $I(X; Y),$
- die Irrelevanz $H(Y|X),$ und
- die Sinkenentropie $H(Y).$
Der Parameter in diesen Tabellen ist $p_0 = {\rm Pr}(X = 0)$ im Bereich zwischen $p_0 = 0.3$ bis $p_0 = 0.7$.
Für die zweite Quellensymbolwahrscheinlichkeit gilt: $p_1 = {\rm Pr}(X = 1) =1 - p_0$.
Hinweise:
- Die Aufgabe gehört zum Kapitel Anwendung auf die Digitalsignalübertragung.
- Bezug genommen wird insbesondere auf die Seite Definition und Bedeutung der Kanalkapazität.
Fragebogen
Musterlösung
(1) Richtig ist der Lösungsvorschlag 3:
- 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}.$$
(2) Richtig ist der Lösungsvorschlag 3:
- Beim BSC–Modell mit der Verfälschungswahrscheinlichkeit $ε = 0.25$ ist bei uncodierter Übertragung ⇒ $R = 1$ unabhängig von $p_0$ und $p_1$ die Bitfehlerwahrscheinlichkeit gleich $p_{\rm 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}.$$
- Zu beachten ist jedoch, dass nun die Quellenentropie nicht mehr $H(X) = 1\ \rm (bit)$ beträgt, sondern nur mehr $H(X) = H_{bin} (0.6) = 0.971 \ \rm (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 keinerlei Information, diese aber mit der Bitfehlerwahrscheinlichkeit „Null”.
(3) Richtig ist der Lösungsvorschlag 1:
- Aus der Grafik auf der Angabenseite lässt sich für die Kapazitäten der beiden Kanäle ablesen:
- $$C_{\rm BSC} = 0.1887 \ \rm {bit/use}, \hspace{0.5cm}C_{\rm EUC} = 0.3219 \ \rm {bit/use}.$$
- Nach dem Kanalcodierungstheorem kann bei $R ≤ C$ eine Kanalcodierung gefunden werden, mit der die Fehlerwahrscheinlichkeit zu Null gemacht werden kann.
- Bei beiden Kanälen trifft diese Bedingung mit der Rate $R = 0.16$ zu.
(4) Richtig ist 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$,
also ein kleinerer Wert als für die Kanalkapazität $C$, und es gilt auch $I(X; Y) < 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 Teilaufgaben (3) und (4) geht hervor, dass der Lösungsvorschlag 4 zutrifft.
