Aufgaben:Aufgabe 1.16: Fehlerwahrscheinlichkeitsschranken für AWGN: Unterschied zwischen den Versionen
(2 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Schranken für die Blockfehlerwahrscheinlichkeit}} | {{quiz-Header|Buchseite=Kanalcodierung/Schranken für die Blockfehlerwahrscheinlichkeit}} | ||
− | [[Datei:P_ID2414__KC_A_1_15.png|right|frame|Fehlerfunktion ${\rm Q}(x)$ und Näherungen ]] | + | [[Datei:P_ID2414__KC_A_1_15.png|right|frame|Fehlerfunktion ${\rm Q}(x)$ und Näherungen;<br>es gilt: ${\rm Q_u}(x)\le{\rm Q}(x)\le{\rm Q_o}(x)$ ]] |
Wir gehen von der folgenden Konstellation aus: | Wir gehen von der folgenden Konstellation aus: | ||
− | * | + | *Ein linearer Blockcode mit Coderate $R = k/n$ und Distanzspektrum $\{W_i\}, \ i = 1, \ \text{...} \ , n$, |
− | |||
− | |||
+ | *ein AWGN–Kanal, gekennzeichnet durch $E_{\rm B}/N_{0}$ ⇒ umrechenbar in die Rauschleistung $\sigma^2$, | ||
− | Unter der für die gesamte Aufgabe gültigen Annahme, dass stets das Nullwort $\underline{x}_{1} = (0, 0, \text{...} \ , 0)$ gesendet wird, gilt für die [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit| | + | *ein Empfänger, basierend auf "Soft Decision" sowie dem "Maximum–Likelihood–Kriterium". |
+ | |||
+ | |||
+ | Unter der für die gesamte Aufgabe gültigen Annahme, dass stets das Nullwort $\underline{x}_{1} = (0, 0, \text{...} \ , 0)$ gesendet wird, gilt für die [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|"paarweise Fehlerwahrscheinlichkeit"]] mit einem anderen Codewort $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$: | ||
:$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$ | :$$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$ | ||
− | Die Herleitung dieser Beziehung finden Sie in [Liv10]. In dieser Gleichung werden verwendet: | + | Die Herleitung dieser Beziehung finden Sie in "[Liv10]". In dieser Gleichung werden verwendet: |
− | *die [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|komplementäre Gaußsche Fehlerfunktion]] ${\rm Q}(x)$, | + | *die [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|"komplementäre Gaußsche Fehlerfunktion"]] ${\rm Q}(x)$, |
− | *das [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]] $w_{\rm H}(\underline{x}_{l})$ des Codewortes $\underline{x}_{l}$, | + | |
− | *die [[Digitalsignalübertragung/Optimierung_der_Basisbandübertragungssysteme#Systemoptimierung_bei_Leistungsbegrenzung|AWGN–Rauschleistung]] $\sigma^2 = (2 · R · E_{\rm B}/N_{0})^{–1}.$ | + | *das [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|"Hamming–Gewicht"]] $w_{\rm H}(\underline{x}_{l})$ des Codewortes $\underline{x}_{l}$, |
+ | |||
+ | *die [[Digitalsignalübertragung/Optimierung_der_Basisbandübertragungssysteme#Systemoptimierung_bei_Leistungsbegrenzung|"AWGN–Rauschleistung"]] $\sigma^2 = (2 · R · E_{\rm B}/N_{0})^{–1}.$ | ||
Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben: | Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben: | ||
− | *die so genannte [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|Union Bound]] (UB): | + | *die so genannte [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|"Union Bound"]] $\rm (UB)$: |
:$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$ | :$$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$ | ||
− | *die so genannte [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Schranken_f.C3.BCr_den_.287.2C_4.2C_3.29.E2.80.93Hamming.E2.80.93Code_beim_AWGN.E2.80.93Kanal|Truncated Union Bound]] (TUB): | + | *die so genannte [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Schranken_f.C3.BCr_den_.287.2C_4.2C_3.29.E2.80.93Hamming.E2.80.93Code_beim_AWGN.E2.80.93Kanal|"Truncated Union Bound"]] $\rm (TUB)$: |
:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$ | :$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$ | ||
− | *die [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Die_obere_Schranke_nach_Bhattacharyya|Bhattacharyya–Schranke]]: | + | *die [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Die_obere_Schranke_nach_Bhattacharyya|"Bhattacharyya–Schranke"]]: |
:$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm mit}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$ | :$$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm mit}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$ | ||
Zeile 37: | Zeile 41: | ||
:$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$ | :$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$ | ||
− | Beim Übergang von der | + | Beim Übergang von der "Union Bound" $p_{1}$ zur ungenaueren Schranke $p_{3}$ wird unter Anderem |
+ | *die Funktion ${\rm Q}(x)$ durch die [https://de.wikipedia.org/wiki/Chernoff-Ungleichung "Chernoff–Rubin–Schranke"] ${\rm Q}_{\rm CR}(x)$ ersetzt. | ||
+ | |||
+ | *Beide Funktionen sind in obigerer Grafik dargestellt (rote bzw. grüne Kurve). | ||
+ | |||
+ | |||
+ | In der [[Aufgaben:Aufgabe_1.16Z:_Schranken_für_die_Gaußsche_Fehlerfunktion|"Aufgabe 1.16Z"]] wird der Zusammenhang zwischen diesen Funktionen numerisch ausgewertet und zu den Schranken ${\rm Q}_{o}(x)$ und ${\rm Q}_{u}(x)$ Bezug genommen, die in obiger Grafik ebenfalls eingezeichnet sind. | ||
+ | |||
− | |||
+ | Hinweise: | ||
+ | * Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit|"Schranken für die Blockfehlerwahrscheinlichkeit"]]. | ||
+ | * Die oben zitierte Literaturstelle "[Liv10]" verweist auf das Vorlesungsmanuskript: <br>"Liva, G.: Channel Coding. Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010". | ||
− | + | * Weiter verweisen wir auf das interaktive HTML5/JavaScript–Applet [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen| "Komplementäre Gaußsche Fehlerfunktionen"]]. | |
− | |||
− | |||
− | * Weiter verweisen wir auf das interaktive Applet [[Applets: | ||
Zeile 56: | Zeile 66: | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Welche Gleichung gilt für die | + | {Welche Gleichung gilt für die "Union Bound"? |
|type="[]"} | |type="[]"} | ||
- $p_{1} = \sum_{l\hspace{0.05cm}=\hspace{0.05cm}2}^{2^k} W_{l} · {\rm Q}\big[(l/\sigma^2)^{0.5}\big],$ | - $p_{1} = \sum_{l\hspace{0.05cm}=\hspace{0.05cm}2}^{2^k} W_{l} · {\rm Q}\big[(l/\sigma^2)^{0.5}\big],$ | ||
Zeile 66: | Zeile 76: | ||
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 0.0444 3% } $\ \%$ | $\sigma = 0.5 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 0.0444 3% } $\ \%$ | ||
− | {Was liefert die | + | {Was liefert die "Truncated Union Bound" bei gleichen Randbedingungen? |
|type="{}"} | |type="{}"} | ||
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{2} \ = \ $ { 31.92 3% } $\ \%$ | $\sigma = 1.0 \text{:} \hspace{0.4cm} p_{2} \ = \ $ { 31.92 3% } $\ \%$ | ||
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{2} \ = \ $ { 0.044 3% } $\ \%$ | $\sigma = 0.5 \text{:} \hspace{0.4cm} p_{2} \ = \ $ { 0.044 3% } $\ \%$ | ||
− | {Welche Aussage gilt immer (für alle Konstellationen)? | + | {Welche Aussage gilt immer (für alle Konstellationen)? |
|type="[]"} | |type="[]"} | ||
+ Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{1}$. | + Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{1}$. | ||
- Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{2}$. | - Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{2}$. | ||
− | {Wie kommt man von $p_{1}$ zur Bhattacharyya–Schranke $p_{3}$? Dadurch, dass man | + | {Wie kommt man von $p_{1}$ zur Bhattacharyya–Schranke $p_{3}$? Dadurch, dass man |
|type="[]"} | |type="[]"} | ||
+ die Fehlerfunktion ${\rm Q}(x)$ durch die Funktion ${\rm Q}_{\rm CR}(x)$ ersetzt, | + die Fehlerfunktion ${\rm Q}(x)$ durch die Funktion ${\rm Q}_{\rm CR}(x)$ ersetzt, | ||
Zeile 91: | Zeile 101: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Richtig ist die <u>Antwort 2</u>. Das Distanzspektrum $\{W_i\}$ ist definiert für $i = 0, \ \text{...} \ , \ n$: | + | '''(1)''' Richtig ist die <u>Antwort 2</u>. |
+ | |||
+ | Das Distanzspektrum $\{W_i\}$ ist definiert für $i = 0, \ \text{...} \ , \ n$: | ||
+ | |||
+ | *$W_{1}$ gibt an, wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = 1$ auftritt. | ||
− | + | *$W_{n}$ gibt an, wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = n$ auftritt. | |
− | *$W_{n}$ gibt an, wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = n$ auftritt. | ||
− | Damit lautet die | + | Damit lautet die "Union Bound": |
:$$p_1 = {\rm Pr(Union \hspace{0.15cm}Bound)}= \sum_{i = 1}^{n}\hspace{0.05cm}W_i \cdot {\rm Q}\left ( \sqrt{i/\sigma^2} \right ) \hspace{0.05cm}.$$ | :$$p_1 = {\rm Pr(Union \hspace{0.15cm}Bound)}= \sum_{i = 1}^{n}\hspace{0.05cm}W_i \cdot {\rm Q}\left ( \sqrt{i/\sigma^2} \right ) \hspace{0.05cm}.$$ | ||
− | '''(2)''' Das Distanzspektrum des $(8, 4, 4)$–Codes wurde mit $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$ angegeben. Somit erhält man für $\sigma = 1$: | + | '''(2)''' Das Distanzspektrum des $(8, 4, 4)$–Codes wurde mit $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$ angegeben. |
+ | *Somit erhält man für $\sigma = 1$: | ||
:$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right ) | :$$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right ) | ||
= 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$ | = 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$ | ||
− | + | *Und für $\sigma = 0.5$: | |
:$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right ) | :$$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right ) | ||
= 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$ | = 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$ | ||
− | '''(3)''' Mit der Minimaldistanz $d_{\rm min} = 4$ erhält man: | + | '''(3)''' Mit der Minimaldistanz $d_{\rm min} = 4$ erhält man: |
:$$\sigma = 1.0\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 31.92\%}\hspace{0.05cm},$$ | :$$\sigma = 1.0\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 31.92\%}\hspace{0.05cm},$$ | ||
Zeile 117: | Zeile 131: | ||
− | '''(4)''' Richtig ist der <u>Lösungsvorschlag 1</u>: | + | '''(4)''' Richtig ist der <u>Lösungsvorschlag 1</u>: |
− | *Die | + | *Die "Union Bound" – hier mit $p_{1}$ bezeichnet – ist in jedem Fall eine obere Schranke für die Blockfehlerwahrscheinlichkeit. |
− | *Für die Schranke $p_{2}$ ( | + | |
− | *Beispielsweise erhält man beim $(7, 4, 3)$–Hamming–Code ⇒ $W_{3} = W_{4} = 7, \ W_{7} = 1$ mit der Streuung $\sigma = 1$: | + | *Für die Schranke $p_{2}$ ("Truncated Union Bound") trifft das nicht immer zu. |
+ | |||
+ | *Beispielsweise erhält man beim $(7, 4, 3)$–Hamming–Code ⇒ $W_{3} = W_{4} = 7, \ W_{7} = 1$ mit der Streuung $\sigma = 1$: | ||
:$$p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{3} \right ) = 7 \cdot 4.18 \cdot 10^{-2} \approx 0.293\hspace{0.05cm},$$ | :$$p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{3} \right ) = 7 \cdot 4.18 \cdot 10^{-2} \approx 0.293\hspace{0.05cm},$$ | ||
:$$p_1 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} p_2 + 7 \cdot {\rm Q}\left ( \sqrt{4} \right )+ 1 \cdot {\rm Q}\left ( \sqrt{7} \right ) \approx 0.455 \hspace{0.05cm}.$$ | :$$p_1 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} p_2 + 7 \cdot {\rm Q}\left ( \sqrt{4} \right )+ 1 \cdot {\rm Q}\left ( \sqrt{7} \right ) \approx 0.455 \hspace{0.05cm}.$$ | ||
− | Die tatsächliche Blockfehlerwahrscheinlichkeit wird wahrscheinlich zwischen $p_{2} = 29.3\%$ und $p_{1} = 45.5\%$ liegen (wurde allerdings nicht nachgeprüft). <br>Das heißt: $p_{2}$ ist keine obere Schranke. | + | *Die tatsächliche Blockfehlerwahrscheinlichkeit wird wahrscheinlich zwischen $p_{2} = 29.3\%$ und $p_{1} = 45.5\%$ liegen (wurde allerdings von uns nicht nachgeprüft). <br>Das heißt: $p_{2}$ ist keine obere Schranke. |
− | '''(5)''' Richtig sind die <u>Lösungsvorschläge 1 und 3</u>, wie die folgende Rechnung für den $(8, 4, 4)$–Code zeigt: | + | '''(5)''' Richtig sind die <u>Lösungsvorschläge 1 und 3</u>, wie die folgende Rechnung für den $(8, 4, 4)$–Code zeigt: |
− | *Es gilt ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$. Damit kann für die Union Bound | + | *Es gilt ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$. Damit kann für die Union Bound |
:$$p_1 = W_4 \cdot {\rm Q}\left ( \sqrt{4/\sigma^2} \right ) +W_8 \cdot {\rm Q}\left ( \sqrt{8/\sigma^2} \right )$$ | :$$p_1 = W_4 \cdot {\rm Q}\left ( \sqrt{4/\sigma^2} \right ) +W_8 \cdot {\rm Q}\left ( \sqrt{8/\sigma^2} \right )$$ | ||
Zeile 138: | Zeile 154: | ||
:$$p_1 \le W_4 \cdot {\rm e}^{ - {4}/(2 \sigma^2) } +W_8 \cdot {\rm e}^{ - {8}/(2 \sigma^2) } \hspace{0.05cm}.$$ | :$$p_1 \le W_4 \cdot {\rm e}^{ - {4}/(2 \sigma^2) } +W_8 \cdot {\rm e}^{ - {8}/(2 \sigma^2) } \hspace{0.05cm}.$$ | ||
− | *Mit $\beta = {\rm e}^{–1/(2\sigma^2)}$ kann hierfür auch geschrieben werden (das vorgegebene $\beta = 1/\sigma$ ist also falsch): | + | *Mit $\beta = {\rm e}^{–1/(2\sigma^2)}$ kann hierfür auch geschrieben werden (das vorgegebene $\beta = 1/\sigma$ ist also falsch): |
:$$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$ | :$$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$ | ||
− | *Die Gewichtsfunktion des $(8, 4, 4)$–Codes lautet: | + | *Die Gewichtsfunktion des $(8, 4, 4)$–Codes lautet: |
:$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm} | :$$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm} | ||
Zeile 148: | Zeile 164: | ||
− | '''(6)''' Mit $\sigma = 1$ lautet der Bhattacharyya–Parameter $\beta = {\rm e}^{–0.5} = 0.6065$ und man erhält damit für die Bhattacharyya–Schranke: | + | '''(6)''' Mit $\sigma = 1$ lautet der Bhattacharyya–Parameter $\beta = {\rm e}^{–0.5} = 0.6065$ und man erhält damit für die Bhattacharyya–Schranke: |
:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 0.135 + 0.018= 1.913 \hspace{0.15cm}\underline{= 191.3%}\hspace{0.05cm}.$$ | :$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 0.135 + 0.018= 1.913 \hspace{0.15cm}\underline{= 191.3%}\hspace{0.05cm}.$$ | ||
− | *Berücksichtigt man, dass $p_{3}$ (eine Schranke für) eine Wahrscheinlichkeit angibt, so ist $p_{3} = 1.913$ nur eine triviale Schranke. | + | *Berücksichtigt man, dass $p_{3}$ (eine Schranke für) eine Wahrscheinlichkeit angibt, so ist $p_{3} = 1.913$ nur eine triviale Schranke. |
− | *Für $\sigma = 0.5$ ergibt sich dagegen $\beta = {\rm e}^{–2} \approx 0.135.$ Dann gilt: | + | |
+ | *Für $\sigma = 0.5$ ergibt sich dagegen $\beta = {\rm e}^{–2} \approx 0.135.$ Dann gilt: | ||
:$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 3.35 \cdot 10^{-4} + 1.1 \cdot 10^{-7} \hspace{0.15cm}\underline{= 0.47 \%}\hspace{0.05cm}.$$ | :$$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 3.35 \cdot 10^{-4} + 1.1 \cdot 10^{-7} \hspace{0.15cm}\underline{= 0.47 \%}\hspace{0.05cm}.$$ | ||
− | Ein Vergleich mit der Teilaufgabe (2) zeigt, dass im vorliegenden Beispiel die Bhattacharyya–Schranke $p_{3}$ um den Faktor $(0.47 · 10^{–2})/(0.044 · 10^{–2}) > 10$ oberhalb der | + | Ein Vergleich mit der Teilaufgabe '''(2)''' zeigt, dass im vorliegenden Beispiel die Bhattacharyya–Schranke $p_{3}$ um den Faktor |
− | *Der Grund für diese große Abweichung ist die Chernoff–Rubin–Schranke, die deutlich oberhalb der ${\rm Q}$–Funktion liegt. | + | :$$(0.47 · 10^{–2})/(0.044 · 10^{–2}) > 10$$ |
− | *In der [[Aufgaben:Aufgabe_1.16Z:_Schranken_für_die_Gaußsche_Fehlerfunktion|Aufgabe 1.16Z]] wird die Abweichung zwischen ${\rm Q}_{\rm CR}$ und ${\rm Q}(x)$ auch quantitativ berechnet: | + | oberhalb der "Union Bound" $p_{1}$ liegt. |
+ | *Der Grund für diese große Abweichung ist die Chernoff–Rubin–Schranke, die deutlich oberhalb der ${\rm Q}$–Funktion liegt. | ||
+ | |||
+ | *In der [[Aufgaben:Aufgabe_1.16Z:_Schranken_für_die_Gaußsche_Fehlerfunktion|"Aufgabe 1.16Z"]] wird die Abweichung zwischen ${\rm Q}_{\rm CR}$ und ${\rm Q}(x)$ auch quantitativ berechnet: | ||
:$${{\rm Q_{CR}}( x )}/{{\rm Q}( x )} \approx 2.5 \cdot x \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {{\rm Q_{CR}}( x = 4 )}/{{\rm Q}( x = 4)} \approx 10 \hspace{0.05cm}.$$ | :$${{\rm Q_{CR}}( x )}/{{\rm Q}( x )} \approx 2.5 \cdot x \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {{\rm Q_{CR}}( x = 4 )}/{{\rm Q}( x = 4)} \approx 10 \hspace{0.05cm}.$$ |
Aktuelle Version vom 5. August 2022, 15:40 Uhr
Wir gehen von der folgenden Konstellation aus:
- Ein linearer Blockcode mit Coderate $R = k/n$ und Distanzspektrum $\{W_i\}, \ i = 1, \ \text{...} \ , n$,
- ein AWGN–Kanal, gekennzeichnet durch $E_{\rm B}/N_{0}$ ⇒ umrechenbar in die Rauschleistung $\sigma^2$,
- ein Empfänger, basierend auf "Soft Decision" sowie dem "Maximum–Likelihood–Kriterium".
Unter der für die gesamte Aufgabe gültigen Annahme, dass stets das Nullwort $\underline{x}_{1} = (0, 0, \text{...} \ , 0)$ gesendet wird, gilt für die "paarweise Fehlerwahrscheinlichkeit" mit einem anderen Codewort $\underline{x}_{l} (l = 2,\ \text{...} \ , 2^k)$:
- $$ {\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = {\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm}.$$
Die Herleitung dieser Beziehung finden Sie in "[Liv10]". In dieser Gleichung werden verwendet:
- die "komplementäre Gaußsche Fehlerfunktion" ${\rm Q}(x)$,
- das "Hamming–Gewicht" $w_{\rm H}(\underline{x}_{l})$ des Codewortes $\underline{x}_{l}$,
- die "AWGN–Rauschleistung" $\sigma^2 = (2 · R · E_{\rm B}/N_{0})^{–1}.$
Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben:
- die so genannte "Union Bound" $\rm (UB)$:
- $$p_1 = \sum_{l = 2}^{2^k}\hspace{0.05cm}{\rm Pr}[\hspace{0.05cm}\underline{x}_{\hspace{0.02cm}1} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}l}\hspace{0.05cm}] = \sum_{l \hspace{0.05cm}= \hspace{0.05cm}2}^{2^k}\hspace{0.05cm}{\rm Q}\left ( \sqrt{w_{\rm H}(\underline{x}_{\hspace{0.02cm}l})/\sigma^2} \right ) \hspace{0.05cm},$$
- die so genannte "Truncated Union Bound" $\rm (TUB)$:
- $$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$
- $$p_3 = W(\beta) - 1\hspace{0.05cm},\hspace{0.2cm} {\rm mit}\hspace{0.15cm} \beta = {\rm e}^{ - 1/(2\sigma^2) } \hspace{0.05cm}.$$
- In diesem Fall ist das Distanzspektrum $\{W_i\}$ durch die Gewichtsfunktion zu ersetzen:
- $$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$
Beim Übergang von der "Union Bound" $p_{1}$ zur ungenaueren Schranke $p_{3}$ wird unter Anderem
- die Funktion ${\rm Q}(x)$ durch die "Chernoff–Rubin–Schranke" ${\rm Q}_{\rm CR}(x)$ ersetzt.
- Beide Funktionen sind in obigerer Grafik dargestellt (rote bzw. grüne Kurve).
In der "Aufgabe 1.16Z" wird der Zusammenhang zwischen diesen Funktionen numerisch ausgewertet und zu den Schranken ${\rm Q}_{o}(x)$ und ${\rm Q}_{u}(x)$ Bezug genommen, die in obiger Grafik ebenfalls eingezeichnet sind.
Hinweise:
- Die Aufgabe gehört zum Kapitel "Schranken für die Blockfehlerwahrscheinlichkeit".
- Die oben zitierte Literaturstelle "[Liv10]" verweist auf das Vorlesungsmanuskript:
"Liva, G.: Channel Coding. Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010".
- Weiter verweisen wir auf das interaktive HTML5/JavaScript–Applet "Komplementäre Gaußsche Fehlerfunktionen".
Fragebogen
Musterlösung
Das Distanzspektrum $\{W_i\}$ ist definiert für $i = 0, \ \text{...} \ , \ n$:
- $W_{1}$ gibt an, wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = 1$ auftritt.
- $W_{n}$ gibt an, wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = n$ auftritt.
Damit lautet die "Union Bound":
- $$p_1 = {\rm Pr(Union \hspace{0.15cm}Bound)}= \sum_{i = 1}^{n}\hspace{0.05cm}W_i \cdot {\rm Q}\left ( \sqrt{i/\sigma^2} \right ) \hspace{0.05cm}.$$
(2) Das Distanzspektrum des $(8, 4, 4)$–Codes wurde mit $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$ angegeben.
- Somit erhält man für $\sigma = 1$:
- $$p_1 = W_4 \cdot {\rm Q}\left ( 2 \right ) + W_8 \cdot {\rm Q}\left ( 2 \cdot \sqrt{2} \right ) = 14 \cdot 2.28 \cdot 10^{-2}+ 1 \cdot 0.23 \cdot 10^{-2} \hspace{0.15cm}\underline{\approx 32.15\%}\hspace{0.05cm},$$
- Und für $\sigma = 0.5$:
- $$p_1 = 14 \cdot {\rm Q}\left ( 4 \right ) + {\rm Q}\left ( 4 \cdot \sqrt{2} \right ) = 14 \cdot 3.17 \cdot 10^{-5}+ 1.1 \cdot 10^{-8} \hspace{0.15cm}\underline{\approx 0.0444 \%}\hspace{0.05cm}.$$
(3) Mit der Minimaldistanz $d_{\rm min} = 4$ erhält man:
- $$\sigma = 1.0\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 31.92\%}\hspace{0.05cm},$$
- $$\sigma = 0.5\text{:} \hspace{0.4cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm}W_4 \cdot {\rm Q}\left ( 4 \right ) \approx p_1 \hspace{0.15cm}\underline{ = 0.0444 \%}\hspace{0.05cm}.$$
(4) Richtig ist der Lösungsvorschlag 1:
- Die "Union Bound" – hier mit $p_{1}$ bezeichnet – ist in jedem Fall eine obere Schranke für die Blockfehlerwahrscheinlichkeit.
- Für die Schranke $p_{2}$ ("Truncated Union Bound") trifft das nicht immer zu.
- Beispielsweise erhält man beim $(7, 4, 3)$–Hamming–Code ⇒ $W_{3} = W_{4} = 7, \ W_{7} = 1$ mit der Streuung $\sigma = 1$:
- $$p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 7 \cdot {\rm Q}\left ( \sqrt{3} \right ) = 7 \cdot 4.18 \cdot 10^{-2} \approx 0.293\hspace{0.05cm},$$
- $$p_1 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} p_2 + 7 \cdot {\rm Q}\left ( \sqrt{4} \right )+ 1 \cdot {\rm Q}\left ( \sqrt{7} \right ) \approx 0.455 \hspace{0.05cm}.$$
- Die tatsächliche Blockfehlerwahrscheinlichkeit wird wahrscheinlich zwischen $p_{2} = 29.3\%$ und $p_{1} = 45.5\%$ liegen (wurde allerdings von uns nicht nachgeprüft).
Das heißt: $p_{2}$ ist keine obere Schranke.
(5) Richtig sind die Lösungsvorschläge 1 und 3, wie die folgende Rechnung für den $(8, 4, 4)$–Code zeigt:
- Es gilt ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$. Damit kann für die Union Bound
- $$p_1 = W_4 \cdot {\rm Q}\left ( \sqrt{4/\sigma^2} \right ) +W_8 \cdot {\rm Q}\left ( \sqrt{8/\sigma^2} \right )$$
- eine weitere obere Schranke angegeben werden:
- $$p_1 \le W_4 \cdot {\rm e}^{ - {4}/(2 \sigma^2) } +W_8 \cdot {\rm e}^{ - {8}/(2 \sigma^2) } \hspace{0.05cm}.$$
- Mit $\beta = {\rm e}^{–1/(2\sigma^2)}$ kann hierfür auch geschrieben werden (das vorgegebene $\beta = 1/\sigma$ ist also falsch):
- $$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$
- Die Gewichtsfunktion des $(8, 4, 4)$–Codes lautet:
- $$W(X) = 1 + W_4 \cdot X^4 + W_8 \cdot X^8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(\beta) - 1 = W_4 \cdot \beta^4 + W_8 \cdot \beta^8\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_3 = W(\beta) - 1 \ge p_1\hspace{0.05cm}.$$
(6) Mit $\sigma = 1$ lautet der Bhattacharyya–Parameter $\beta = {\rm e}^{–0.5} = 0.6065$ und man erhält damit für die Bhattacharyya–Schranke:
- $$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 0.135 + 0.018= 1.913 \hspace{0.15cm}\underline{= 191.3%}\hspace{0.05cm}.$$
- Berücksichtigt man, dass $p_{3}$ (eine Schranke für) eine Wahrscheinlichkeit angibt, so ist $p_{3} = 1.913$ nur eine triviale Schranke.
- Für $\sigma = 0.5$ ergibt sich dagegen $\beta = {\rm e}^{–2} \approx 0.135.$ Dann gilt:
- $$p_3 = 14 \cdot \beta^4 + \beta^8 = 14 \cdot 3.35 \cdot 10^{-4} + 1.1 \cdot 10^{-7} \hspace{0.15cm}\underline{= 0.47 \%}\hspace{0.05cm}.$$
Ein Vergleich mit der Teilaufgabe (2) zeigt, dass im vorliegenden Beispiel die Bhattacharyya–Schranke $p_{3}$ um den Faktor
- $$(0.47 · 10^{–2})/(0.044 · 10^{–2}) > 10$$
oberhalb der "Union Bound" $p_{1}$ liegt.
- Der Grund für diese große Abweichung ist die Chernoff–Rubin–Schranke, die deutlich oberhalb der ${\rm Q}$–Funktion liegt.
- In der "Aufgabe 1.16Z" wird die Abweichung zwischen ${\rm Q}_{\rm CR}$ und ${\rm Q}(x)$ auch quantitativ berechnet:
- $${{\rm Q_{CR}}( x )}/{{\rm Q}( x )} \approx 2.5 \cdot x \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {{\rm Q_{CR}}( x = 4 )}/{{\rm Q}( x = 4)} \approx 10 \hspace{0.05cm}.$$