Difference between revisions of "Aufgaben:Exercise 3.13: Code Rate and Reliability"
m (Guenter verschob die Seite 3.12 Coderate und Zuverlässigkeit nach 3.13 Coderate und Zuverlässigkeit) |
|||
| Line 3: | Line 3: | ||
}} | }} | ||
| − | [[File:P_ID2805__Inf_A_3_12.png|right|]] | + | [[File:P_ID2805__Inf_A_3_12.png|right|frame|Binäre Entropiefunktion]] |
| − | Das Kanalcodierungstheorem von Shannon besagt unter anderem, dass über einen Kanal mit beliebig kleiner Blockfehlerwahrscheinlichkeit übertragen werden kann, so lange die Coderate $R$ nicht größer ist als die Kanalkapazität $C$. Dieses Ergebnis erreicht man mit ''Kanalcodierung'' (englisch: ''Channel Coding'') bei sehr großen Blocklängen: $n → ∞$, was mit einem beliebig großen Aufwand verbunden ist. | + | Das Kanalcodierungstheorem von [https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon] besagt unter anderem, dass über einen Kanal mit beliebig kleiner Blockfehlerwahrscheinlichkeit übertragen werden kann, so lange die Coderate $R$ nicht größer ist als die Kanalkapazität $C$. Dieses Ergebnis erreicht man mit ''Kanalcodierung'' (englisch: ''Channel Coding'') allerdings nur bei sehr großen Blocklängen: $n → ∞$, was mit einem beliebig großen Aufwand verbunden ist. |
Diese Aussage basiert auf informationstheoretischen Gesetzmäßigkeiten, die Shannon selbst aufgestellt hat. Shannon sagt nicht, wie diese „unendlich gute” Kanalcodierung aussehen muss, er beweist nur, dass es sie gibt. | Diese Aussage basiert auf informationstheoretischen Gesetzmäßigkeiten, die Shannon selbst aufgestellt hat. Shannon sagt nicht, wie diese „unendlich gute” Kanalcodierung aussehen muss, er beweist nur, dass es sie gibt. | ||
| − | Der Umkehrschluss des Kanalcodierungstheorems sagt aus, dass mit einer Rate $R > C$ keine fehlerfreie Übertragung möglich ist. Es gibt kein Codiersystem mit verschwindend kleiner Fehlerwahrscheinlichkeit, auch wenn die Codierung noch so aufwändig und ausgeklügelt wäre. | + | Der Umkehrschluss des Kanalcodierungstheorems sagt aus, dass mit einer Rate $R > C$ keine fehlerfreie Übertragung möglich ist. Es gibt dann kein Codiersystem mit verschwindend kleiner Fehlerwahrscheinlichkeit, auch wenn die Codierung noch so aufwändig und ausgeklügelt wäre. |
Vielmehr lassen sich für den Fall $R > C$ zwei Schranken angeben: | Vielmehr lassen sich für den Fall $R > C$ zwei Schranken angeben: | ||
| − | + | * Überträgt man über einen ''diskreten gedächtnislosen Kanal'' (DMC) mit einer Rate $R$ größer als die Kanalkapazität $C$, so gibt es eine untere Schranke für die Bitfehlerwahrscheinlichkeit: | |
| − | $$ p_{\rm B} \ge H_{\rm bin}^{-1} \left (1 - \frac{C}{R} \right) > 0 \hspace{0.05cm}.$$ | + | :$$ p_{\rm B} \ge H_{\rm bin}^{-1} \left (1 - \frac{C}{R} \right) > 0 \hspace{0.05cm}.$$ |
| − | + | * Soll die Bitfehlerwahrscheinlichkeit nach bestmöglicher Decodierung den Wert $p_B$ nicht überschreiten, so darf die Coderate einen vorgegebenen Grenzwert nicht unterschreiten: | |
| − | $$ R \le \frac{C}{1 - H_{\rm bin}( p_{\rm B})} \hspace{0.05cm}.$$ | + | :$$ R \le \frac{C}{1 - H_{\rm bin}( p_{\rm B})} \hspace{0.05cm}.$$ |
| − | In dieser Aufgabe sollen diese Gleichungen unter Verwendung der [ | + | |
| − | $$ H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p} | + | In dieser Aufgabe sollen diese Gleichungen unter Verwendung der [[Informationstheorie/Ged%C3%A4chtnislose_Nachrichtenquellen#Bin.C3.A4re_Entropiefunktion|binären Entropiefunktion]] |
| − | numerisch ausgewertet werden. Diese ist oben skizziert. Wegen $0 < p_B ≤ 1$ und $0 < C/R < 1$ liegt das Argument der Funktion $H_{bin}(⋅)$ und deren Umkehrfunktion $H_{bin}^{ –1 }(⋅)$ stets zwischen $0$ und $1$. | + | :$$ H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}$$ |
| − | ''' | + | numerisch ausgewertet werden. Diese ist oben skizziert. Wegen $0 < p_B ≤ 1$ und $0 < C/R < 1$ liegt das Argument der Funktion $H_{\rm bin}(⋅)$ und deren Umkehrfunktion $H_{\rm bin}^{ –1 }(⋅)$ stets zwischen $0$ und $1$. |
| + | |||
| + | |||
| + | ''Hinweise:'' | ||
| + | *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#Rate.2C_Kanalkapazit.C3.A4t_und_Bitfehlerwahrscheinlichkeit|Rate, Kanalkapazität und Bitfehlerwahrscheinlichkeit]]. | ||
| + | *Die Werte der binären Entropiefunktion werden zum Beispiel durch das interaktice Berechnungsmodul [[Entropien von Nachrichtenquellen]] bereitgestellt. | ||
| + | *Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein. | ||
| + | |||
| + | |||
===Fragebogen=== | ===Fragebogen=== | ||
Revision as of 16:06, 7 June 2017
Das Kanalcodierungstheorem von Claude E. Shannon besagt unter anderem, dass über einen Kanal mit beliebig kleiner Blockfehlerwahrscheinlichkeit übertragen werden kann, so lange die Coderate $R$ nicht größer ist als die Kanalkapazität $C$. Dieses Ergebnis erreicht man mit Kanalcodierung (englisch: Channel Coding) allerdings nur bei sehr großen Blocklängen: $n → ∞$, was mit einem beliebig großen Aufwand verbunden ist.
Diese Aussage basiert auf informationstheoretischen Gesetzmäßigkeiten, die Shannon selbst aufgestellt hat. Shannon sagt nicht, wie diese „unendlich gute” Kanalcodierung aussehen muss, er beweist nur, dass es sie gibt.
Der Umkehrschluss des Kanalcodierungstheorems sagt aus, dass mit einer Rate $R > C$ keine fehlerfreie Übertragung möglich ist. Es gibt dann kein Codiersystem mit verschwindend kleiner Fehlerwahrscheinlichkeit, auch wenn die Codierung noch so aufwändig und ausgeklügelt wäre.
Vielmehr lassen sich für den Fall $R > C$ zwei Schranken angeben:
- Überträgt man über einen diskreten gedächtnislosen Kanal (DMC) mit einer Rate $R$ größer als die Kanalkapazität $C$, so gibt es eine untere Schranke für die Bitfehlerwahrscheinlichkeit:
- $$ p_{\rm B} \ge H_{\rm bin}^{-1} \left (1 - \frac{C}{R} \right) > 0 \hspace{0.05cm}.$$
- Soll die Bitfehlerwahrscheinlichkeit nach bestmöglicher Decodierung den Wert $p_B$ nicht überschreiten, so darf die Coderate einen vorgegebenen Grenzwert nicht unterschreiten:
- $$ R \le \frac{C}{1 - H_{\rm bin}( p_{\rm B})} \hspace{0.05cm}.$$
In dieser Aufgabe sollen diese Gleichungen unter Verwendung der binären Entropiefunktion
- $$ H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}$$
numerisch ausgewertet werden. Diese ist oben skizziert. Wegen $0 < p_B ≤ 1$ und $0 < C/R < 1$ liegt das Argument der Funktion $H_{\rm bin}(⋅)$ und deren Umkehrfunktion $H_{\rm bin}^{ –1 }(⋅)$ stets zwischen $0$ und $1$.
Hinweise:
- Die Aufgabe gehört zum Kapitel Anwendung auf die Digitalsignalübertragung.
- Bezug genommen wird insbesondere auf die Seite Rate, Kanalkapazität und Bitfehlerwahrscheinlichkeit.
- Die Werte der binären Entropiefunktion werden zum Beispiel durch das interaktice Berechnungsmodul Entropien von Nachrichtenquellen bereitgestellt.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
2.Durch Umstellung obiger Gleichung erhält man mit $H_{bin}(p_B)$ aus der $\text{Grafik}$: \begin{align*} R_{\rm max} = \frac{C}{1 - H_{\rm bin}( p_{\rm B})} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_{\rm B} \hspace{-0.15cm} &= \hspace{-0.15cm} 0.10:\hspace{0.2cm} R_{\rm max} = \frac{0.5}{1 - 0.469}\hspace{0.15cm} \underline {=0.942} \hspace{0.05cm},\\ \Rightarrow \hspace{0.3cm} p_{\rm B} \hspace{-0.15cm} &= \hspace{-0.15cm} 0.05:\hspace{0.2cm} R_{\rm max} = \frac{0.5}{1 - 0.286}\hspace{0.15cm} \underline {=0.700}\hspace{0.05cm}\end{align*} 3. Für die binäre Entropiefunktion gilt definitionsgemäß: $$H_{\rm bin}( p) = p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} + (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$ Beide Terme sind positiv. Daraus folgt der Lösungsvorschlag 2: $$ H_{\rm bin}( p) > p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} \hspace{0.05cm}.$$ Die Differenz ist durch den zweiten Term der binären Entropiefunktion gegeben: $$ H_{\rm bin}( p) - p \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{p} = (1-p) \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{1-p}\hspace{0.05cm}.$$ Dieser Term wird umso kleiner, je kleiner p ist. Zutreffend ist also auch der Lösungsvorschlag 3: $$ p_{\rm B} \hspace{-0.15cm} =\hspace{-0.15cm} 10^{-3}: \hspace{0.3cm} 0.999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.999}= 1.4420 \cdot 10^{-3} \hspace{0.05cm},$$ $$p_{\rm B} \hspace{-0.15cm} =\hspace{-0.15cm} 10^{-4}: \hspace{0.3cm} 0.9999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.9999}= 1.4427 \cdot 10^{-4} \hspace{0.05cm},$$ $$p_{\rm B} \hspace{-0.15cm} =\hspace{-0.15cm} 10^{-5}: \hspace{0.3cm} 0.99999 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.99999}= 1.4427 \cdot 10^{-5} \hspace{0.05cm}.$$ 4. Der Ausdruck $R/C$ gibt die obere Schranke gemäß dem inversen Kanalcodierungstheorem an. Für $p_B = 10^{ –3 }$ erhält man folgende Schranke: $R/C ≤ 1.01154 ⇒ R/C – 1 ≤ 1.154 · 10^{ –2 }$.
- Beim Vorschlag 2 ist die Näherung gemäß (c) berücksichtigt. Da nun der Nenner vergrößert wird, ist $R′/C < R/C$, beispielsweise gilt für $p_B = 10{ –3 }: R′/C = 1.01007 · 10{ –2 }$. Es handelt sich auch hier um eine obere Schranke, die etwas sicherer ist als die erste Schranke $R/C.$
- Die Schranke $R′′ < R′$ ergibt sich, wenn man $1/(1 – ε)$ durch $1 + ε$ ersetzt ($ε$ ist positiv). Für $p_B = 10{ –3 }$erhält man nun beispielsweise $R′′/C = 1.00997 ⇒ R′′/C – 1 ≤ 0.997 · 10{ –2}.$
- $R′′′$ ist identisch mit $R′′$ und für Überschlagsrechnungen bei ganzzahligem Exponenten $i$ gut geeignet. Für den Zehnerlogarithmus gilt der Zahlenwert $lg(2) ≈ 0.30103.$
Alle Vorschläge sind richtig. Die Tabelle zeigt für verschiedene Bitfehlerwahrscheinlichkeiten $p_B$ die Schranke $R/C$ und die 3. Näherung. Man erkennt die gute Übereinstimmung der beiden Schranken.
