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

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(32 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)$ ]]
 
 
}}
 
 
 
[[Datei:P_ID2414__KC_A_1_15.png|right|frame|Funktion <i>Q</i>(<i>x</i>) und Näherungen ]]
 
  
 
Wir gehen von der folgenden Konstellation aus:
 
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 linearer Blockcode mit der Coderate $R = k/n$ und dem Distanzspektrum { $W_{i}$ }, $i = 1, ... , n,$
+
*ein AWGN–Kanal,&nbsp; gekennzeichnet durch&nbsp; $E_{\rm B}/N_{0}$ &nbsp; ⇒ &nbsp; umrechenbar in die Rauschleistung&nbsp; $\sigma^2$,
  
*ein AWGN–Kanal, gekennzeichnet durch „$E_{\rm B}/N_{0}$” ⇒  umrechenbar in die Rauschleistung $\sigma^2$,
+
*ein Empfänger,&nbsp; basierend auf&nbsp; "Soft Decision"&nbsp; sowie dem&nbsp; "Maximum–Likelihood–Kriterium".
  
*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, ... , 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, ... , 2^k):$
+
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}.$$
 
:$$ {\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 wurden verwendet:
+
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)$,
  
*die komplementäre Gaußsche Fehlerfunktion ${\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}$,
  
*das [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]] $w_{\rm H}(\underline{x}_{l})$ des Codewortes $\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}.$  
  
*die 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 sogenannte [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit|Union Bound]]:
+
*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 = 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 [http://www.eit.lth.se/fileadmin/eit/courses/ett051/Laborationer/Lab2ManualHt12009.pdf Truncated Union Bound] (TUB):
+
*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},$$
 
:$$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&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 exp}\left [ - 1/(2\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:
+
: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}.$$
 
:$$\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 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).
+
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.
 +
 
  
In der [[Aufgaben:1.16Z_Schranken_für_Q(x)|Aufgabe 1.16Z]] wird der Zusammenhang zwischen diesen Funktionen numerisch ausgewertet und Bezug genommen zu den Schranken ${\rm Q}_{o}(x)$ und ${\rm Q}_{u}(x)$, die in obiger Grafik ebenfalls eingezeichnet sind.
 
  
  
''Hinweis:''
+
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"]].
 +
 
 +
 
  
Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Schranken_für_die_Blockfehlerwahrscheinlichkeit|Schranken für die Blockfehlerwahrscheinlichkeit]] Weiter verweisen wir auf folgendes Flash–Modul:
 
  
Komplimentäre Gaußsche Fehlerfunktion (Dateigröße: 235 kB)
 
  
 
===Fragebogen===
 
===Fragebogen===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Gleichung gilt für die ''Union Bound''?
+
{Welche Gleichung gilt für die&nbsp; "Union Bound"?
 
|type="[]"}
 
|type="[]"}
- $p_{1} = {\rm Summe}$ (über $l = 2, ... , 2^k$)  $W_{l} · {\rm Q}[(l/\sigma^2)^{0.5}],$
+
- $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} = {\rm Summe}$ (über $i = 1, ... , n$)  $W_{i} · {\rm Q}[(i/\sigma^2)^{0.5}],$
+
+ $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 (8, 4, 4)–Code und $\sigma = 1$, $\sigma = 0.5$ an.
+
{Geben Sie die Union Bound für den&nbsp; $(8, 4, 4)$–Code und verschiedene&nbsp; $\sigma$&nbsp; an.
 
|type="{}"}
 
|type="{}"}
$\ (8, 4, 4)–Code, \sigma = 1:   p_{1}$ = { 0.3215 3% }
+
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 32.15 3% } $\ \%$
$\ \sigma = 0.5: \ \ \ p_{1}$ = { 0.444 3% }$\ \cdot 10^{-3} $
+
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{1} \ = \ $ { 0.0444 3% } $\ \%$
  
 
+
{Was liefert die&nbsp; "Truncated Union Bound"&nbsp; bei gleichen Randbedingungen?
{Was liefert die ''Truncated Union Bound'' bei gleichen Randbedingungen?
 
 
|type="{}"}
 
|type="{}"}
$\ (8, 4, 4)–Code, \sigma = 1:   p_{2}$ = { 0.3192 3% }
+
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{2} \ = \ $ { 31.92 3% } $\ \%$
$\ \sigma = 0.5: \ \ \ p_{2}$ = { 0.444 3% }$\ \cdot 10^{-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&nbsp; (für alle Konstellationen)?
 
|type="[]"}
 
|type="[]"}
+ Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{1}$.
+
+ Die Blockfehlerwahrscheinlichkeit ist nie größer als&nbsp; $p_{1}$.
- Die Blockfehlerwahrscheinlichkeit ist nie größer als $p_{2}$.
+
- Die Blockfehlerwahrscheinlichkeit ist nie größer als&nbsp; $p_{2}$.
  
{Wie kommt man von $p_{1}$ zur Bhattacharyya–Schranke $p_{3}$? Dadurch, dass man
+
{Wie kommt man von&nbsp; $p_{1}$&nbsp; zur Bhattacharyya–Schranke&nbsp; $p_{3}$?&nbsp; Dadurch, dass man
 
|type="[]"}
 
|type="[]"}
+ die Fehlerfunktion ${\rm Q}(x)$ durch die Funktion ${\rm Q}_{\rm CR}(x)$ ersetzt,
+
+ die Fehlerfunktion&nbsp; ${\rm Q}(x)$&nbsp; durch die Funktion&nbsp; ${\rm Q}_{\rm CR}(x)$&nbsp; ersetzt,
- den Bhattacharyya–Parameter $\beta = 1/\sigma$ setzt,
+
- den Bhattacharyya–Parameter&nbsp; $\beta = 1/\sigma$&nbsp; setzt,
+ statt { $W_{i}$ } die Gewichtsfunktion $W(X)$ verwendet.
+
+ statt&nbsp; $\{W_i\}$&nbsp; die Gewichtsfunktion&nbsp; $W(X)$&nbsp; verwendet.
  
  
{Geben Sie die Bhattacharyya–Schranke für $\sigma = 1$ und $\sigma = 0.5$ an.
+
{Geben Sie die Bhattacharyya–Schranke für&nbsp; $\sigma = 1$&nbsp; und&nbsp; $\sigma = 0.5$&nbsp; an.
 
|type="{}"}
 
|type="{}"}
$\ (8, 4, 4)–Code, \sigma = 1:   p_{3}$ = { 1.913 3% }
+
$\sigma = 1.0 \text{:} \hspace{0.4cm} p_{3} \ = \ $ { 191.3 3% } $\ \%$
$\ \sigma = 0.5: \ \ \ p_{3}$ = { 0.47 3% }$\ \cdot 10^{-2} $
+
$\sigma = 0.5 \text{:} \hspace{0.4cm} p_{3} \ = \ $ { 0.47 3% } $\ \%$
 +
</quiz>
  
 +
===Musterlösung===
 +
{{ML-Kopf}}
 +
'''(1)'''&nbsp; Richtig ist die&nbsp;  <u>Antwort 2</u>.
  
 +
Das Distanzspektrum&nbsp; $\{W_i\}$&nbsp; ist definiert für&nbsp; $i = 0, \ \text{...} \ , \ n$:
  
</quiz>
+
*$W_{1}$&nbsp; gibt an,&nbsp; wie oft das Hamming–Gewicht&nbsp; $w_{\rm H}(\underline{x}_{i}) = 1$&nbsp; auftritt.
  
===Musterlösung===
+
*$W_{n}$&nbsp; gibt an,&nbsp; wie oft das Hamming–Gewicht $w_{\rm H}(\underline{x}_{i}) = n$&nbsp; auftritt.
{{ML-Kopf}}
 
'''(1)'''&nbsp; Richtig ist <u>Antwort 2</u>. Das Distanzspektrum { $W_{i}$ } ist definiert für $i = 0, ... , 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'':
+
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}.$$
 
:$$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 (8, 4, 4)–Codes wurde mit $W_{0} = 1 , W_{4} = 14, W_{8} = 1$ angegeben. Somit erhält man für $\boldsymbol{\sigma = 1}$:
+
'''(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:
 
   
 
   
bzw. für $\boldsymbol{\sigma = 0.5}$:
+
:$$\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.
 
   
 
   
'''(3)'''&nbsp; Mit der Minimaldistanz $d_{\rm min} = 4$ erhält man:
+
*Für die Schranke&nbsp; $p_{2}$&nbsp; ("Truncated Union Bound")&nbsp; trifft das nicht immer zu.
 
   
 
   
:$$\sigma = 1.0: \hspace{0.2cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} W_4 \cdot {\rm Q}\left ( 2 \right ) \hspace{0.15cm}\underline{= 0.3192}\hspace{0.05cm},$$
+
*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$:
:$$\sigma = 0.5: \hspace{0.2cm} p_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm}W_4 \cdot {\rm Q}\left ( 4 \right ) \approx p_1 \hspace{0.15cm}\underline{ = 0.444 \cdot 10^{-3}}\hspace{0.05cm}.$$
 
 
 
'''(4)'''&nbsp; Richtig ist <u>Antwort 1</u>. 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$ und 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} = 0.293$ und $p_{1} = 0.455$ liegen (wurde nicht nachgeprüft). Das heißt: $p_{2}$ ist keine obere Schranke.
+
*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>, wie die folgende Rechnung für den (8, 4, 4)–Code zeigt:
+
'''(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 Q(x) ≤ QCR(x) = exp(– x2/2). Damit kann für die Union Bound
+
*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 )$$
 
:$$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:
+
:eine weitere obere Schranke angegeben werden:
 
   
 
   
:$$p_1 \le W_4 \cdot {\rm exp}\left [ - {4}/(2 \sigma^2) \right ] +W_8 \cdot {\rm exp}\left [ - {8}/(2 \sigma^2) \right ] \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 exp}[–1/(2\sigama^2)]$ kann hierfür auch geschrieben werden (das vorgegebene $\beta = 1/\sigma$ ist also falsch):
+
*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}.$$
 
:$$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&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$$
+
:$$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}.$$
 +
 
  
:$$\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}.$$
  
'''(6)'''&nbsp; Mit σ = 1 lautet der Bhattacharyya–Parameter β = exp(–0.5) = 0.6065 und man erhält damit für die Bhattacharyya–Schranke:
+
*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.
 
   
 
   
Berücksichtigt man, dass p3 (eine Schranke für) eine Wahrscheinlichkeit angibt, so ist p3 = 1.913 nur eine triviale Schranke. Für σ = 0.5 ergibt sich dagegen β = exp(–2) ≈ 0.135. Dann gilt:
+
*Für&nbsp; $\sigma = 0.5$&nbsp; ergibt sich dagegen&nbsp; $\beta = {\rm e}^{–2}  \approx 0.135.$&nbsp; Dann gilt:
 
   
 
   
Ein Vergleich mit der Teilaufgabe b) zeigt, dass im vorliegenden Beispiel die Bhattacharyya–Schranke p3 um den Faktor (4.7 · 10–3)/(0.44 · 10–3) > 10 oberhalb der Union Bound p1 liegt. Der Grund für diese große Abweichung ist die Chernoff–Rubin–Schranke, die deutlich oberhalb der Q–Funktion liegt. In der Aufgabe Z1.16 wird die Abweichung zwischen QCR und Q(x) auch quantitativ berechnet:
+
:$$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ß}}
 
{{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}.$$