Aufgaben:Aufgabe 1.16: Fehlerwahrscheinlichkeitsschranken für AWGN: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Schranken für die Blockfehlerwahrscheinlichkeit }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Mul…“)
 
 
(37 dazwischenliegende Versionen von 4 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&nbsp; ${\rm Q}(x)$&nbsp; und Näherungen;<br>es gilt:&nbsp; ${\rm Q_u}(x)\le{\rm Q}(x)\le{\rm Q_o}(x)$ ]]
 +
 +
Wir gehen von der folgenden Konstellation aus:
 +
*Ein linearer Blockcode mit Coderate&nbsp; $R = k/n$&nbsp; und Distanzspektrum&nbsp; $\{W_i\}, \ i = 1, \ \text{...} \ , n$,
 +
 +
*ein AWGN–Kanal,&nbsp; gekennzeichnet durch&nbsp; $E_{\rm B}/N_{0}$ &nbsp; ⇒ &nbsp; umrechenbar in die Rauschleistung&nbsp; $\sigma^2$,
 +
 +
*ein Empfänger,&nbsp; basierend auf&nbsp; "Soft Decision"&nbsp; sowie dem&nbsp; "Maximum–Likelihood–Kriterium".
 +
 +
 +
Unter der für die gesamte Aufgabe gültigen Annahme,&nbsp; dass stets das Nullwort &nbsp; $\underline{x}_{1} = (0, 0, \text{...} \ , 0)$ &nbsp; gesendet wird,&nbsp; gilt für die&nbsp; [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|"paarweise Fehlerwahrscheinlichkeit"]]&nbsp; mit einem anderen Codewort&nbsp; $\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&nbsp; "[Liv10]".&nbsp; In dieser Gleichung werden verwendet:
 +
*die&nbsp; [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|"komplementäre Gaußsche Fehlerfunktion"]]&nbsp; ${\rm Q}(x)$,
 +
 +
*das&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|"Hamming–Gewicht"]]&nbsp; $w_{\rm H}(\underline{x}_{l})$&nbsp; des Codewortes&nbsp; $\underline{x}_{l}$,
 +
 +
*die&nbsp; [[Digitalsignalübertragung/Optimierung_der_Basisbandübertragungssysteme#Systemoptimierung_bei_Leistungsbegrenzung|"AWGN–Rauschleistung"]]&nbsp; $\sigma^2 = (2 · R · E_{\rm B}/N_{0})^{–1}.$
 +
 +
 +
Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben:
 +
 +
*die so genannte&nbsp; [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|"Union Bound"]]&nbsp; $\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&nbsp; [[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"]]&nbsp; $\rm (TUB)$:
 +
 +
:$$p_2 = W_{d_{\rm min}} \cdot {\rm Q}\left ( \sqrt{d_{\rm min}/\sigma^2} \right ) \hspace{0.05cm},$$
 +
 +
*die&nbsp; [[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}.$$
 +
 +
:In diesem Fall ist das Distanzspektrum&nbsp; $\{W_i\}$&nbsp; 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&nbsp; "Union Bound"&nbsp; $p_{1}$&nbsp; zur ungenaueren Schranke&nbsp; $p_{3}$&nbsp; wird unter Anderem
 +
*die Funktion&nbsp; ${\rm Q}(x)$&nbsp; durch die&nbsp; [https://de.wikipedia.org/wiki/Chernoff-Ungleichung "Chernoff–Rubin–Schranke"]&nbsp; ${\rm Q}_{\rm CR}(x)$&nbsp; ersetzt.
 +
 +
*Beide Funktionen sind in obigerer Grafik dargestellt (rote bzw. grüne Kurve).
 +
 +
 +
In der&nbsp; [[Aufgaben:Aufgabe_1.16Z:_Schranken_für_die_Gaußsche_Fehlerfunktion|"Aufgabe 1.16Z"]]&nbsp; wird der Zusammenhang zwischen diesen Funktionen numerisch ausgewertet und zu den Schranken&nbsp; ${\rm Q}_{o}(x)$ und ${\rm Q}_{u}(x)$&nbsp; Bezug genommen,&nbsp; die in obiger Grafik ebenfalls eingezeichnet sind.
 +
 +
 +
 +
 +
Hinweise:
 +
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit|"Schranken für die Blockfehlerwahrscheinlichkeit"]].
 +
 +
* Die oben zitierte Literaturstelle&nbsp;  "[Liv10]"&nbsp; verweist auf das Vorlesungsmanuskript: <br>"Liva, G.:&nbsp; Channel Coding.&nbsp;  Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010".
 +
 +
* Weiter verweisen wir auf das interaktive HTML5/JavaScript&ndash;Applet&nbsp; [[Applets:Komplementäre_Gaußsche_Fehlerfunktionen| "Komplementäre Gaußsche Fehlerfunktionen"]].
  
  
}}
 
  
[[Datei:|right|]]
 
  
  
Zeile 11: Zeile 66:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
+
{Welche Gleichung gilt für die&nbsp; "Union Bound"?
 
|type="[]"}
 
|type="[]"}
- Falsch
+
- $p_{1} = \sum_{l\hspace{0.05cm}=\hspace{0.05cm}2}^{2^k} W_{l} · {\rm Q}\big[(l/\sigma^2)^{0.5}\big],$
+ Richtig
+
+ $p_{1} = \sum_{i\hspace{0.05cm}=\hspace{0.05cm}1}^{n} W_{i} · {\rm Q}\big[(i/\sigma^2)^{0.5}\big].$
  
 +
{Geben Sie die Union Bound für den&nbsp; $(8, 4, 4)$–Code und verschiedene&nbsp; $\sigma$&nbsp; an.
 +
|type="{}"}
 +
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 32.15 3% } $\ \%$
 +
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 0.0444 3% } $\ \%$
  
{Input-Box Frage
+
{Was liefert die&nbsp; "Truncated Union Bound"&nbsp; bei gleichen Randbedingungen?
 
|type="{}"}
 
|type="{}"}
$\alpha$ = { 0.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% } $\ \%$
  
 +
{Welche Aussage gilt immer&nbsp; (für alle Konstellationen)?
 +
|type="[]"}
 +
+ Die Blockfehlerwahrscheinlichkeit ist nie größer als&nbsp; $p_{1}$.
 +
- Die Blockfehlerwahrscheinlichkeit ist nie größer als&nbsp; $p_{2}$.
 +
 +
{Wie kommt man von&nbsp; $p_{1}$&nbsp; zur Bhattacharyya–Schranke&nbsp; $p_{3}$?&nbsp; Dadurch, dass man
 +
|type="[]"}
 +
+ die Fehlerfunktion&nbsp; ${\rm Q}(x)$&nbsp; durch die Funktion&nbsp; ${\rm Q}_{\rm CR}(x)$&nbsp; ersetzt,
 +
- den Bhattacharyya–Parameter&nbsp; $\beta = 1/\sigma$&nbsp; setzt,
 +
+ statt&nbsp; $\{W_i\}$&nbsp; die Gewichtsfunktion&nbsp; $W(X)$&nbsp; verwendet.
  
  
 +
{Geben Sie die Bhattacharyya–Schranke für&nbsp; $\sigma = 1$&nbsp; und&nbsp; $\sigma = 0.5$&nbsp; an.
 +
|type="{}"}
 +
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{3} \ = \ $ { 191.3 3% } $\ \%$
 +
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{3} \ = \ $ { 0.47 3% } $\ \%$
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
'''(1)'''&nbsp; Richtig ist die&nbsp;  <u>Antwort 2</u>.
'''2.'''
+
 
'''3.'''
+
Das Distanzspektrum&nbsp; $\{W_i\}$&nbsp; ist definiert für&nbsp; $i = 0, \ \text{...} \ , \ n$:
'''4.'''
+
 
'''5.'''
+
*$W_{1}$&nbsp; gibt an,&nbsp; wie oft das Hamming–Gewicht&nbsp; $w_{\rm H}(\underline{x}_{i}) = 1$&nbsp; auftritt.
'''6.'''
+
 
'''7.'''
+
*$W_{n}$&nbsp; gibt an,&nbsp; wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = n$&nbsp; auftritt.
{{ML-Fuß}}
+
 
 +
 
 +
Damit lautet die&nbsp; "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)'''&nbsp; Das Distanzspektrum des&nbsp; $(8, 4, 4)$–Codes wurde mit&nbsp; $W_{0} = 1 , \ W_{4} = 14, \ W_{8} = 1$&nbsp; angegeben.&nbsp;
 +
*Somit erhält man für&nbsp; $\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&nbsp; $\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)'''&nbsp; Mit der Minimaldistanz&nbsp; $d_{\rm min} = 4$&nbsp; 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)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 1</u>:
 +
*Die&nbsp; "Union Bound"&nbsp; – hier mit&nbsp; $p_{1}$&nbsp; bezeichnet – ist in jedem Fall eine obere Schranke für die Blockfehlerwahrscheinlichkeit.
 +
 +
*Für die Schranke&nbsp; $p_{2}$&nbsp; ("Truncated Union Bound")&nbsp; trifft das nicht immer zu.
 +
 +
*Beispielsweise erhält man beim&nbsp; $(7, 4, 3)$–Hamming–Code  &nbsp; ⇒ &nbsp;  $W_{3} = W_{4} = 7, \ W_{7} = 1$&nbsp; mit der Streuung&nbsp; $\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&nbsp; $p_{2} = 29.3\%$&nbsp; und&nbsp; $p_{1} = 45.5\%$&nbsp; liegen (wurde allerdings von uns nicht nachgeprüft). <br>Das heißt: &nbsp; $p_{2}$&nbsp; ist keine obere Schranke.
 +
 
 +
 
 +
'''(5)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 3</u>,&nbsp; wie die folgende Rechnung für den&nbsp; $(8, 4, 4)$–Code zeigt:
 +
 
 +
*Es gilt ${\rm Q}(x) ≤ {\rm Q_{CR}}(x) = {\rm e}^{-x^2/2}$.&nbsp; 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&nbsp; $\beta = {\rm e}^{–1/(2\sigma^2)}$&nbsp; kann hierfür auch geschrieben werden&nbsp; (das vorgegebene&nbsp; $\beta = 1/\sigma$&nbsp; ist also falsch):
 +
 +
:$$p_1 \le W_4 \cdot \beta^4 + W_8 \cdot \beta^8 \hspace{0.05cm}.$$
 +
 
 +
*Die Gewichtsfunktion des&nbsp; $(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)'''&nbsp; Mit&nbsp; $\sigma = 1$&nbsp; lautet der Bhattacharyya–Parameter&nbsp; $\beta = {\rm e}^{–0.5} = 0.6065$&nbsp; 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,&nbsp; dass&nbsp; $p_{3}$&nbsp; (eine Schranke für)&nbsp; eine Wahrscheinlichkeit angibt,&nbsp; so ist&nbsp; $p_{3} = 1.913$&nbsp; nur eine triviale Schranke.
 +
 +
*Für&nbsp; $\sigma = 0.5$&nbsp; ergibt sich dagegen&nbsp; $\beta = {\rm e}^{–2}  \approx 0.135.$&nbsp; 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&nbsp; '''(2)'''&nbsp; zeigt,&nbsp; dass im vorliegenden Beispiel die Bhattacharyya–Schranke&nbsp; $p_{3}$&nbsp; um den Faktor
 +
:$$(0.47 · 10^{–2})/(0.044 · 10^{–2}) > 10$$
 +
oberhalb der&nbsp; "Union Bound"&nbsp; $p_{1}$&nbsp; liegt.
 +
*Der Grund für diese große Abweichung ist die Chernoff–Rubin–Schranke,&nbsp; die deutlich oberhalb der&nbsp; ${\rm Q}$–Funktion liegt.
 +
 +
*In der [[Aufgaben:Aufgabe_1.16Z:_Schranken_für_die_Gaußsche_Fehlerfunktion|"Aufgabe 1.16Z"]]&nbsp; wird die Abweichung zwischen&nbsp; ${\rm Q}_{\rm CR}$&nbsp; und&nbsp; ${\rm Q}(x)$&nbsp; 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}.$$
 +
{{ML-Fuß}}
  
[[Category:Aufgaben zu  Kanalcodierung|^1.6 Schranken für die Blockfehlerwahrscheinlichkeit
 
  
  
^]]
+
[[Category:Aufgaben zu  Kanalcodierung|^1.6 Fehlerwahrscheinlichkeitsschranken^]]

Aktuelle Version vom 5. August 2022, 15:40 Uhr

Fehlerfunktion  ${\rm Q}(x)$  und Näherungen;
es gilt:  ${\rm Q_u}(x)\le{\rm Q}(x)\le{\rm Q_o}(x)$

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:

  • das  "Hamming–Gewicht"  $w_{\rm H}(\underline{x}_{l})$  des Codewortes  $\underline{x}_{l}$,


Damit lassen sich verschiedene Schranken für die Blockfehlerwahrscheinlichkeit angeben:

$$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_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

  • 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 oben zitierte Literaturstelle  "[Liv10]"  verweist auf das Vorlesungsmanuskript:
    "Liva, G.:  Channel Coding.  Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010".



Fragebogen

1

Welche Gleichung gilt für die  "Union Bound"?

$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_{i\hspace{0.05cm}=\hspace{0.05cm}1}^{n} W_{i} · {\rm Q}\big[(i/\sigma^2)^{0.5}\big].$

2

Geben Sie die Union Bound für den  $(8, 4, 4)$–Code und verschiedene  $\sigma$  an.

$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{1} \ = \ $

$\ \%$
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{1} \ = \ $

$\ \%$

3

Was liefert die  "Truncated Union Bound"  bei gleichen Randbedingungen?

$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{2} \ = \ $

$\ \%$
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{2} \ = \ $

$\ \%$

4

Welche Aussage gilt immer  (für alle Konstellationen)?

Die Blockfehlerwahrscheinlichkeit ist nie größer als  $p_{1}$.
Die Blockfehlerwahrscheinlichkeit ist nie größer als  $p_{2}$.

5

Wie kommt man von  $p_{1}$  zur Bhattacharyya–Schranke  $p_{3}$?  Dadurch, dass man

die Fehlerfunktion  ${\rm Q}(x)$  durch die Funktion  ${\rm Q}_{\rm CR}(x)$  ersetzt,
den Bhattacharyya–Parameter  $\beta = 1/\sigma$  setzt,
statt  $\{W_i\}$  die Gewichtsfunktion  $W(X)$  verwendet.

6

Geben Sie die Bhattacharyya–Schranke für  $\sigma = 1$  und  $\sigma = 0.5$  an.

$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{3} \ = \ $

$\ \%$
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{3} \ = \ $

$\ \%$


Musterlösung

(1)  Richtig ist die  Antwort 2.

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}.$$