Aufgaben:Aufgabe 3.11: Auslöschungskanal: Unterschied zwischen den Versionen
Safwen (Diskussion | Beiträge) |
Safwen (Diskussion | Beiträge) |
||
| Zeile 24: | Zeile 24: | ||
{ Welches $P_X(X)$ ist zur Kanalkapazitätsberechnung allgemein anzusetzen? | { Welches $P_X(X)$ ist zur Kanalkapazitätsberechnung allgemein anzusetzen? | ||
|type="[]"} | |type="[]"} | ||
| − | - | + | - $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)$ | ||
| + | {Wie viele Wahrscheinlichkeiten $p_{μκ} = Pr[(X = μ) ∩ (Y = κ)]$ sind $≠ 0$? | ||
| + | |type="[]"} | ||
| + | - Genau $M · (M + 1)$ | ||
| + | - Genau $M$ | ||
| + | + Genau $2 · M$ | ||
| − | { | + | |
| + | {Wie groß ist die Sinkenentropie allgemein und für $M = 4$ und $λ = 0.2$? | ||
| + | |type="{}"} | ||
| + | $ M = 4, λ = 0.2: H(Y)$ = { 2.322 3% } $bit$ | ||
| + | |||
| + | {Berechnen Sie die Irrelevanz. Welcher Wert ergibt sich für $M = 4, λ = 0.2$? | ||
|type="{}"} | |type="{}"} | ||
| − | $ | + | $M = 4, λ = 0.2: H(Y|X)$ = { 0.722 3% } $bit$ |
| + | |||
| + | {Wie groß ist die Kanalkapazität in Abhängigkeit von $M$? | ||
| + | |type="{}"} | ||
| + | $M = 4: C$ = { 1.6 3 % } $bit$ | ||
| + | $M = 2: C$ = { 0.8 3% } $bit$ | ||
| + | |||
| + | {Wie lautet die Kanalkapazität des BEC–Kanals in kompakter Form? | ||
| + | |type="[]"} | ||
| + | + $C_{BEC} = 1 – λ$ | ||
| + | - $C_{BEC} = 1 – Hbin(λ)$ | ||
| + | |||
| Zeile 38: | Zeile 60: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''1.''' | + | '''1.''' 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: |
| − | '''2.''' | + | $$ 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}$$ |
| − | '''3.''' | + | Richtig ist also der ''Lösungsvorschlag 2.'' Im Sonderfall $M = 2$ wäre auch $P_X(X) = (0.5, 0.5)$ richtig. |
| − | '''4.''' | + | |
| − | '''5.''' | + | '''2.'''Von jedem Quellensymbol $X = μ$ kommt man sowohl zum Sinkensymbol $Y = μ$ als auch zum Erasure $Y = E ⇒$ Zutreffend ist dementsprechend der ''Lösungsvorschlag 3'' $⇒$ Genau $2M$ Verbindungen. |
| − | '''6.''' | + | |
| − | ''' | + | '''3.''' Alle Wahrscheinlichkeiten $Pr(Y = 1), ... , Pr(Y = M)$ sind gleich groß. Man erhält für $μ = 1, ... , M$: |
| + | $${\rm Pr}(Y \hspace{-0.05cm} = \mu) = \frac{ 1-\lambda }{M} \hspace{0.05cm}$$ | ||
| + | Außerdem kommt man von jedem Quellensymbol $X = 1, ... , X = M$ auch zum Erasure$ Y = 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 [http://www.lntwww.de/Informationstheorie/Ged%C3%A4chtnislose_Nachrichtenquellen#Bin.C3.A4re_Entropiefunktion 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 $⇒ pμκ = Pr [(X = μ) ∩ (Y = κ)] ≠ 0$ und die zugehörigen bedingten Wahrscheinlichkeiten $⇒ pκ|μ = 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. | ||
| + | $$ 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} =$$ | ||
| + | $$=\hspace{-0.15cm} ( 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 \hspace{-0.15cm} = \hspace{-0.15cm} \max_{P_X(X)} \hspace{0.15cm} I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) =$$ | ||
| + | $$= \hspace{-0.15cm} ( 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 \hspace{-0.15cm} = \hspace{-0.15cm} 4: \hspace{0.5cm} \underline {C=1.6\,\,{\rm bit}} \hspace{0.05cm}$$ | ||
| + | $$M \hspace{-0.15cm} =\hspace{-0.15cm} 2: \hspace{0.5cm} \underline {C=0.8\,\,{\rm bit}} \hspace{0.05cm}$$ | ||
| + | |||
| + | '''6.''' Der BEC–Kanal 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 [http://www.lntwww.de/index.php?title=Digitalsignal%C3%BCbertragung/Binary_Symmetric_Channel_(BSC)&action=edit&redlink=1 Binary Symmetric Channel] (BSC) mit der Verfälschungswahrscheinlichkeit $λ$. | ||
| + | |||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Version vom 28. November 2016, 17:01 Uhr
Betrachtet wird ein Auslöschungskanal mit
- den M Eingängen $x ∈ X = \{1, 2, ... , M\}$, und
- den $M + 1$ Ausgängen $y ∈ Y = \{1, 2, ... , M, E\}$
Die Grafik zeigt das Modell für den Sonderfall $M = 4$. Das Sinkensymbol $y = 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) \hspace{-0.15cm} = \hspace{-0.15cm} 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) \hspace{-0.15cm} =\hspace{-0.15cm} \lambda \hspace{0.05cm}$$ Gesucht ist
- die Kapazität $C_{M–EC}$ dieses M–ary Erasure Channels,
- die Kapazität $C_{BEC}$ des Binary Erasure Channels als Sonderfall des obigen Modells,
Hinweis: Die Aufgabe beschreibt die Thematik von Kapitel 3.3. In dem obigen Schaubild sind Auslöschungen (Wahrscheinlichkeit $λ$) blau gezeichnet und „richtige Übertragungswege” (also von $X = μ$ nach $Y = μ$) blau ($1 ≤ μ ≤ M$).
Fragebogen
Musterlösung
2.Von jedem Quellensymbol $X = μ$ kommt man sowohl zum Sinkensymbol $Y = μ$ als auch zum Erasure $Y = E ⇒$ Zutreffend ist dementsprechend der Lösungsvorschlag 3 $⇒$ Genau $2M$ Verbindungen.
3. Alle Wahrscheinlichkeiten $Pr(Y = 1), ... , Pr(Y = M)$ sind gleich groß. Man erhält für $μ = 1, ... , M$: $${\rm Pr}(Y \hspace{-0.05cm} = \mu) = \frac{ 1-\lambda }{M} \hspace{0.05cm}$$ Außerdem kommt man von jedem Quellensymbol $X = 1, ... , X = M$ auch zum Erasure$ Y = 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 $⇒ pμκ = Pr [(X = μ) ∩ (Y = κ)] ≠ 0$ und die zugehörigen bedingten Wahrscheinlichkeiten $⇒ pκ|μ = 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.
$$ 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} =$$ $$=\hspace{-0.15cm} ( 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 \hspace{-0.15cm} = \hspace{-0.15cm} \max_{P_X(X)} \hspace{0.15cm} I(X;Y) = H(Y) - H(Y \hspace{-0.1cm}\mid \hspace{-0.1cm} X) =$$ $$= \hspace{-0.15cm} ( 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 \hspace{-0.15cm} = \hspace{-0.15cm} 4: \hspace{0.5cm} \underline {C=1.6\,\,{\rm bit}} \hspace{0.05cm}$$ $$M \hspace{-0.15cm} =\hspace{-0.15cm} 2: \hspace{0.5cm} \underline {C=0.8\,\,{\rm bit}} \hspace{0.05cm}$$
6. Der BEC–Kanal 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 $λ$.
