Difference between revisions of "Aufgaben:Exercise 3.14: Error Probability Bounds"

From LNTwww
m (Text replacement - "”" to """)
(20 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken}}
  
[[File:P_ID2713__KC_A_3_14.png|right|frame|Unvollständige Tabelle für Bhattacharyya– und Viterbi–Schranke]]
+
[[File:P_ID2713__KC_A_3_14.png|right|frame|Bhattacharyya– und die Viterbi–Schranke beim BSC–Modell (unvollständige Tabelle)]]
 
Für den häufig verwendeten Faltungscode mit  
 
Für den häufig verwendeten Faltungscode mit  
* der Coderate $R = 1/2$,
+
* der Coderate  $R = 1/2$,
* dem Gedächtnis $m = 2$,
+
* dem Gedächtnis  $m = 2$, und
 
* der Übertragungsfunktionsmatrix
 
* der Übertragungsfunktionsmatrix
 
:$${\boldsymbol{\rm G}}(D) = \big ( 1 + D + D^2\hspace{0.05cm},\hspace{0.1cm} 1  + D^2 \hspace{0.05cm}\big ) $$
 
:$${\boldsymbol{\rm G}}(D) = \big ( 1 + D + D^2\hspace{0.05cm},\hspace{0.1cm} 1  + D^2 \hspace{0.05cm}\big ) $$
  
lautet die [[Kanalcodierung/Distanzeigenschaften_und_Fehlerwahrscheinlichkeitsschranken#Erweiterte_Pfadgewichtsfunktion|erweiterte Pfadgewichtsfunktion]]:
+
lautet die  [[Channel_Coding/Distanzeigenschaften_und_Fehlerwahrscheinlichkeitsschranken#Erweiterte_Pfadgewichtsfunktion|erweiterte Pfadgewichtsfunktion]]:
 
:$$T_{\rm enh}(X, U) =  \frac{UX^5}{1- 2 \hspace{0.05cm}U \hspace{-0.05cm}X}  \hspace{0.05cm}.$$
 
:$$T_{\rm enh}(X, U) =  \frac{UX^5}{1- 2 \hspace{0.05cm}U \hspace{-0.05cm}X}  \hspace{0.05cm}.$$
  
Mit der schon häufiger benutzten Reihenentwicklung $1/(1 \, –x) = 1 + x + x^2 + \ ... $ kann hierfür auch geschrieben werden:
+
Mit der schon häufiger benutzten Reihenentwicklung  $1/(1 \, –x) = 1 + x + x^2 + \text{...} \ $  kann hierfür auch geschrieben werden:
:$$T_{\rm enh}(X, U) = U X^5 \cdot \left [ 1 + (2 \hspace{0.05cm}U \hspace{-0.05cm}X) + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^2 + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^3 + ... \hspace{0.10cm} \right ]  \hspace{0.05cm}.$$
+
:$$T_{\rm enh}(X, U) = U X^5 \cdot \left [ 1 + (2 \hspace{0.05cm}U \hspace{-0.05cm}X) + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^2 + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^3 +\text{...\hspace{0.10cm} \right ]  \hspace{0.05cm}.$$
  
Die „einfache” Pfadgewichtsfunktion $T(X)$ ergibt sich daraus, wenn man die zweite Variable $U = 1$ setzt.
+
Die "einfache" Pfadgewichtsfunktion  $T(X)$  ergibt sich daraus, wenn man die zweite Variable  $U = 1$  setzt.
  
Anhand dieser Funktionen können Fehlerwahrscheinlichkeitsschranken angegeben werden:
+
Anhand dieser beiden  Funktionen können Fehlerwahrscheinlichkeitsschranken angegeben werden:
* Die <i>Burstfehlerwahrscheinlichkeit</i> wird durch die <span style="color: rgb(204, 0, 0);"><b>Bhattacharyya&ndash;Schranke</b></span> begrenzt:
+
* Die&nbsp; <i>Burstfehlerwahrscheinlichkeit</i>&nbsp; wird durch die&nbsp; <b>Bhattacharyya&ndash;Schranke</b>&nbsp; begrenzt:
 
:$${\rm Pr(Burstfehler)} \le {\rm Pr(Bhattacharyya)} = T(X = \beta) \hspace{0.05cm}.$$
 
:$${\rm Pr(Burstfehler)} \le {\rm Pr(Bhattacharyya)} = T(X = \beta) \hspace{0.05cm}.$$
  
* Dagegen ist die <i>Bitfehlerwahrscheinlichkeit</i> stets kleiner (oder gleich) der <span style="color: rgb(204, 0, 0);"><b>Viterbi&ndash;Schranke</b></span>:
+
* Dagegen ist die&nbsp; <i>Bitfehlerwahrscheinlichkeit</i>&nbsp; stets kleiner (oder gleich) der&nbsp; <b>Viterbi&ndash;Schranke</b>:
 
::<math>{\rm Pr(Bitfehler)} \le {\rm Pr(Viterbi)} = \left [ \frac {\rm d}{ {\rm d}U}\hspace{0.2cm}T_{\rm enh}(X, U) \right ]_{\substack{X=\beta \\ U=1} }  
 
::<math>{\rm Pr(Bitfehler)} \le {\rm Pr(Viterbi)} = \left [ \frac {\rm d}{ {\rm d}U}\hspace{0.2cm}T_{\rm enh}(X, U) \right ]_{\substack{X=\beta \\ U=1} }  
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
 +
 +
 +
 +
 +
 +
 +
  
 
''Hinweise:''
 
''Hinweise:''
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Distanzeigenschaften_und_Fehlerwahrscheinlichkeitsschranken| Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken]].  
+
* Die Aufgabe gehört zum Kapitel&nbsp; [[Channel_Coding/Distanzeigenschaften_und_Fehlerwahrscheinlichkeitsschranken| Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken]].  
* Der Bhattacharyya&ndash;Parameter für BSC lautet:
+
* Der Bhattacharyya&ndash;Parameter für BSC lautet: &nbsp; $\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}$.
:$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}$$
+
* In obiger Tabelle sind für einige Werte des BSC&ndash;Parameters&nbsp; $\varepsilon$&nbsp; angegeben:
* In obiger Tabelle sind für einige Werte des BSC&ndash;Parameters $\epsilon$ angegeben:
+
:*&nbsp; der Bhattacharyya&ndash;Parameter&nbsp; $\beta$,
** der Bhattacharyya&ndash;Parameter $\beta$,
+
:*&nbsp; die Bhattacharyya&ndash;Schranke&nbsp; ${\rm Pr}(\rm Bhattacharyya)$, und
** die Bhattacharyya&ndash;Schranke ${\rm Pr}(\rm Bhattacharyya)$, und
+
:* &nbsp; die Viterbi&ndash;Schranke&nbsp; $\rm Pr(Viterbi)$.
** die Viterbi&ndash;Schranke $\rm Pr(Viterbi)$.
+
* Im Verlauf dieser Aufgabe sollen Sie die entsprechenden Größen für&nbsp; $\varepsilon = 10^{-2}$&nbsp; und&nbsp; $\varepsilon = 10^{-4}$ berechnen.
* Im Verlauf dieser Aufgabe sollen Sie die entsprechenden Größen für $\epsilon = 10^{&ndash;2}$ und $\epsilon = 10^{&ndash;4}$ berechnen.
+
* Die vollständige Tabelle finden Sie in der Musterlösung.
* Die vollständige Tabelle finden Sie dann in der Musterlösung.
+
* Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 
  
  
Line 42: Line 48:
 
{Welcher Bhattacharyya&ndash;Parameter ergibt sich für das BSC&ndash;Modell?
 
{Welcher Bhattacharyya&ndash;Parameter ergibt sich für das BSC&ndash;Modell?
 
|type="{}"}
 
|type="{}"}
$\epsilon = 10^{&ndash;2} \text{:} \hspace{0.2cm} \beta \ = \ ${ 0.199 3% }
+
$\varepsilon = 10^{&ndash;2} \text{:} \hspace{0.4cm} \beta \ = \ ${ 0.199 3% }
$\epsilon = 10^{&ndash;4} \text{:} \hspace{0.2cm} \beta \ = \ ${ 0.02 3% }
+
$\varepsilon = 10^{&ndash;4} \text{:} \hspace{0.4cm} \beta \ = \ ${ 0.02 3% }
  
 
{Wie lautet die Bhattacharyya&ndash;Schranke?
 
{Wie lautet die Bhattacharyya&ndash;Schranke?
 
|type="{}"}
 
|type="{}"}
$\epsilon = 10^{&ndash;2} \text{:} \hspace{0.2cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 5.18 3% } $\ \cdot 10^{&ndash;4}$
+
$\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 5.18 3% } $\ \cdot 10^{&ndash;4}$
$\epsilon = 10^{&ndash;4} \text{:} \hspace{0.2cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 3.33 3% } $\ \cdot 10^{&ndash;9}$
+
$\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 3.33 3% } $\ \cdot 10^{&ndash;9}$
  
 
{Wie lautet die Viterbi&ndash;Schranke?
 
{Wie lautet die Viterbi&ndash;Schranke?
 
|type="{}"}
 
|type="{}"}
$\epsilon = 10^{&ndash;2} \text{:} \hspace{0.2cm} {\rm Pr(Viterbi)} \ = \ ${ 8.61 3% } $\ \cdot 10^{&ndash;4}$
+
$\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ ${ 8.61 3% } $\ \cdot 10^{&ndash;4}$
$\epsilon = 10^{&ndash;2} \text{:} \hspace{0.2cm} {\rm Pr(Viterbi)} \ = \ ${ 3.47 3% } $\ \cdot 10^{&ndash;9}$
+
$\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ ${ 3.47 3% } $\ \cdot 10^{&ndash;9}$
  
{Für welche Werte $\epsilon < \epsilon_0$ sind die beiden Schranken nicht anwendbar?
+
{Für welche Werte&nbsp; $\varepsilon < \varepsilon_0$&nbsp; sind beide Schranken nicht anwendbar?
 
|type="{}"}
 
|type="{}"}
$\epsilon_0 \ = \ ${ 0.067 3% }
+
$\varepsilon_0 \ = \ ${ 0.067 3% }
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Der Bhattacharyya&ndash;Parameter ergibt sich für das BSC&ndash;Modell mit $\epsilon = 0.01$ zu  
+
'''(1)'''&nbsp; Der Bhattacharyya&ndash;Parameter ergibt sich für das BSC&ndash;Modell mit $\varepsilon = 0.01$ zu  
 
:$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} \hspace{0.2cm}\underline {\approx 0.199}
 
:$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} \hspace{0.2cm}\underline {\approx 0.199}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Für noch kleinere Verfälschungswahrscheinlichkeiten $\epsilon$ kann näherungsweise geschrieben werden:
+
Für noch kleinere Verfälschungswahrscheinlichkeiten $\varepsilon$ kann näherungsweise geschrieben werden:
 
:$$\beta \approx 2 \cdot \sqrt{\varepsilon } \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.2cm} \beta \hspace{0.2cm}\underline {\approx 0.02}
 
:$$\beta \approx 2 \cdot \sqrt{\varepsilon } \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.2cm} \beta \hspace{0.2cm}\underline {\approx 0.02}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
  
'''(2)'''&nbsp; Es gilt ${\rm Pr(Burstfehler)} &#8804; {\rm Pr(Bhattacharyya)}$ mit ${\rm Pr(Bhattacharyya)} = T(X = \beta)$. Für den betrachteten Faltungscode der Rate 1/2, dem Gedächtnis $m = 2$ und $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$ lautet die Pfadgewichtsfunktion:
+
'''(2)'''&nbsp; Es gilt ${\rm Pr(Burstfehler)} &#8804; {\rm Pr(Bhattacharyya)}$ mit ${\rm Pr(Bhattacharyya)} = T(X = \beta)$.  
 +
*Für den betrachteten Faltungscode der Rate 1/2, dem Gedächtnis $m = 2$ und $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$ lautet die Pfadgewichtsfunktion:
 
:$$T(X) = \frac{X^5 }{1- 2X} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
:$$T(X) = \frac{X^5 }{1- 2X} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 
{\rm Pr(Bhattacharyya)} = T(X = \beta) = \frac{\beta^5 }{1- 2\beta}$$
 
{\rm Pr(Bhattacharyya)} = T(X = \beta) = \frac{\beta^5 }{1- 2\beta}$$
 
:$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm}
 
:$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm}
 
{\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{1- 2\cdot 0.199}  \hspace{0.2cm}\underline {\approx 5.18 \cdot 10^{-4}}\hspace{0.05cm},$$
 
{\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{1- 2\cdot 0.199}  \hspace{0.2cm}\underline {\approx 5.18 \cdot 10^{-4}}\hspace{0.05cm},$$
:$$\hspace{0.95cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm}
+
:$$\hspace{0.85cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm}
 
{\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{1- 2\cdot 0.02}  \hspace{0.38cm}\underline {\approx 3.33 \cdot 10^{-9}}\hspace{0.05cm}.$$
 
{\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{1- 2\cdot 0.02}  \hspace{0.38cm}\underline {\approx 3.33 \cdot 10^{-9}}\hspace{0.05cm}.$$
  
Line 92: Line 99:
 
:$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm}
 
:$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm}
 
{\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{(1- 2\cdot 0.199)^2} = \hspace{0.2cm}\underline {\approx 8.61 \cdot 10^{-4}}\hspace{0.05cm},$$
 
{\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{(1- 2\cdot 0.199)^2} = \hspace{0.2cm}\underline {\approx 8.61 \cdot 10^{-4}}\hspace{0.05cm},$$
:$$\varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm}
+
:$$\hspace{0.85cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm}
 
{\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{(1- 2\cdot 0.02)^2} = \hspace{0.2cm}\underline {\approx 3.47 \cdot 10^{-9}}\hspace{0.05cm}.$$
 
{\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{(1- 2\cdot 0.02)^2} = \hspace{0.2cm}\underline {\approx 3.47 \cdot 10^{-9}}\hspace{0.05cm}.$$
  
Wir überprüfen das Ergebnis anhand der folgenden Näherung:
+
*Wir überprüfen das Ergebnis anhand der folgenden Näherung:
:$$T_{\rm enh}(X, U) = U X^5 + 2\hspace{0.05cm}U^2 X^6 + 4\hspace{0.05cm}U^3 X^7 + 8\hspace{0.05cm}U^4 X^8 + ... $$
+
:$$T_{\rm enh}(X, U) = U X^5 + 2\hspace{0.05cm}U^2 X^6 + 4\hspace{0.05cm}U^3 X^7 + 8\hspace{0.05cm}U^4 X^8 + \text{...} $$
:$$\Rightarrow \hspace{0.3cm}\frac {\rm d}{{\rm d}U}\hspace{0.1cm}T_{\rm enh}(X, U) = X^5 + 4\hspace{0.05cm}U X^6 + 12\hspace{0.05cm}U^2 X^7 + 32\hspace{0.05cm}U^3 X^8 + ... $$
+
:$$\Rightarrow \hspace{0.3cm}\frac {\rm d}{{\rm d}U}\hspace{0.1cm}T_{\rm enh}(X, U) = X^5 + 4\hspace{0.05cm}U X^6 + 12\hspace{0.05cm}U^2 X^7 + 32\hspace{0.05cm}U^3 X^8 + \text{...} $$
  
Setzt man $U = 1$ und $X = \beta$ so erhält man wieder die Viterbi&ndash;Schranke:
+
*Setzt man $U = 1$ und $X = \beta$ so erhält man wieder die Viterbi&ndash;Schranke:
:$${\rm Pr(Viterbi)}  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \beta^5 + 4\hspace{0.05cm}\beta^6 + 12\hspace{0.05cm}\beta^7 + 32\hspace{0.05cm}\beta^8 + ...
+
:$${\rm Pr(Viterbi)}  \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \beta^5 + 4\hspace{0.05cm}\beta^6 + 12\hspace{0.05cm}\beta^7 + 32\hspace{0.05cm}\beta^8 +\text{...}
=$$
+
= \beta^5 \cdot (1+ 4\hspace{0.05cm}\beta + 12\hspace{0.05cm}\beta^2 + 32\hspace{0.05cm}\beta^3 + ... )\hspace{0.05cm}. $$
:$$\ = \ \hspace{-0.15cm}  \beta^5 \cdot (1+ 4\hspace{0.05cm}\beta + 12\hspace{0.05cm}\beta^2 + 32\hspace{0.05cm}\beta^3 + ... )\hspace{0.05cm}. $$
 
  
Für $\epsilon = 10^{&ndash;2} \ \Rightarrow \ \beta = 0.199$ erhält man, wenn man die unendliche Summe nach dem $\beta^3$&ndash;Term abbricht:
+
*Für $\varepsilon = 10^{&ndash;2} \ \Rightarrow \ \beta = 0.199$ erhält man, wenn man die unendliche Summe nach dem $\beta^3$&ndash;Term abbricht:
 
:$${\rm Pr(Viterbi)} \approx 3.12 \cdot 10^{-4} \cdot (1 + 0.796 + 0.475 + 0.252) = 7.87 \cdot 10^{-4}
 
:$${\rm Pr(Viterbi)} \approx 3.12 \cdot 10^{-4} \cdot (1 + 0.796 + 0.475 + 0.252) = 7.87 \cdot 10^{-4}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Der Abbruchfehler &ndash; bezogen auf $8.61 \cdot 10^{&ndash;4}$ &ndash; beträgt hier ca. $8.6\%$. Für $\epsilon = 10^{&ndash;4} \ \Rightarrow \ \beta = 0.02$ macht man durch den Abbruch nahezu keinen Fehler:
+
*Der Abbruchfehler &ndash; bezogen auf $8.61 \cdot 10^{&ndash;4}$ &ndash; beträgt hier ca. $8.6\%$. Für $\varepsilon = 10^{&ndash;4} \ \Rightarrow \ \beta = 0.02$ ist der Abbruchfehler noch geringer:
 
:$${\rm Pr(Viterbi)} \approx 3.20 \cdot 10^{-9} \cdot (1 + 0.086 + 0.0048 + 0.0003) = 3.47 \cdot 10^{-9}
 
:$${\rm Pr(Viterbi)} \approx 3.20 \cdot 10^{-9} \cdot (1 + 0.086 + 0.0048 + 0.0003) = 3.47 \cdot 10^{-9}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
  
'''(4)'''&nbsp; [[File:P_ID2714__KC_A_3_14c.png|right|frame|Bhattacharyya– und Viterbi–Schranke für BSC]] Für $\beta = 0.5$ ergeben sich für beide Schranken der Wert &bdquo;unendlich&rdquo;. Für noch größere $\beta$&ndash;Werte wird die Bhattacharyya&ndash;Schranke negativ und auch das Ergebnis für die Viterbi&ndash;Schranke ist dann nicht anwendbar. Daraus folgt:
+
[[File:P_ID2714__KC_A_3_14c.png|right|frame|Bhattacharyya– und die Viterbi–Schranke beim BSC&ndash;Modell (vollständige Tabelle)]]
 +
'''(4)'''&nbsp; Für $\beta = 0.5$ ergeben sich für beide Schranken der Wert "unendlich".  
 +
 
 +
*Für noch größere $\beta$&ndash;Werte wird die Bhattacharyya&ndash;Schranke negativ und auch das Ergebnis für die Viterbi&ndash;Schranke ist dann nicht anwendbar. Daraus folgt:
 
:$$\beta_0 = 2 \cdot \sqrt{\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.5$$
 
:$$\beta_0 = 2 \cdot \sqrt{\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.5$$
 
:$$\Rightarrow \hspace{0.3cm} {\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.25^2 = 0.0625$$
 
:$$\Rightarrow \hspace{0.3cm} {\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.25^2 = 0.0625$$
 
:$$\Rightarrow \hspace{0.3cm} \varepsilon_0^2 - \varepsilon_0 + 0.0625 = 0$$
 
:$$\Rightarrow \hspace{0.3cm} \varepsilon_0^2 - \varepsilon_0 + 0.0625 = 0$$
:$$\Rightarrow \hspace{0.3cm} \varepsilon_0 = 0.5 \cdot (1 - \sqrt{0.75}) \underline {\approx 0.067}\hspace{0.05cm}.$$
+
:$$\Rightarrow \hspace{0.3cm} \varepsilon_0 = 0.5 \cdot (1 - \sqrt{0.75}) \hspace{0.15cm} \underline {\approx 0.067}\hspace{0.05cm}.$$
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^3.5 Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken^]]
+
[[Category:Channel Coding: Exercises|^3.5 Distanzeigenschaften^]]

Revision as of 15:28, 28 May 2021

Bhattacharyya– und die Viterbi–Schranke beim BSC–Modell (unvollständige Tabelle)

Für den häufig verwendeten Faltungscode mit

  • der Coderate  $R = 1/2$,
  • dem Gedächtnis  $m = 2$, und
  • der Übertragungsfunktionsmatrix
$${\boldsymbol{\rm G}}(D) = \big ( 1 + D + D^2\hspace{0.05cm},\hspace{0.1cm} 1 + D^2 \hspace{0.05cm}\big ) $$

lautet die  erweiterte Pfadgewichtsfunktion:

$$T_{\rm enh}(X, U) = \frac{UX^5}{1- 2 \hspace{0.05cm}U \hspace{-0.05cm}X} \hspace{0.05cm}.$$

Mit der schon häufiger benutzten Reihenentwicklung  $1/(1 \, –x) = 1 + x + x^2 + \text{...} \ $  kann hierfür auch geschrieben werden:

$$T_{\rm enh}(X, U) = U X^5 \cdot \left [ 1 + (2 \hspace{0.05cm}U \hspace{-0.05cm}X) + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^2 + (2 \hspace{0.05cm}U\hspace{-0.05cm}X)^3 +\text{...} \hspace{0.10cm} \right ] \hspace{0.05cm}.$$

Die "einfache" Pfadgewichtsfunktion  $T(X)$  ergibt sich daraus, wenn man die zweite Variable  $U = 1$  setzt.

Anhand dieser beiden Funktionen können Fehlerwahrscheinlichkeitsschranken angegeben werden:

  • Die  Burstfehlerwahrscheinlichkeit  wird durch die  Bhattacharyya–Schranke  begrenzt:
$${\rm Pr(Burstfehler)} \le {\rm Pr(Bhattacharyya)} = T(X = \beta) \hspace{0.05cm}.$$
  • Dagegen ist die  Bitfehlerwahrscheinlichkeit  stets kleiner (oder gleich) der  Viterbi–Schranke:
\[{\rm Pr(Bitfehler)} \le {\rm Pr(Viterbi)} = \left [ \frac {\rm d}{ {\rm d}U}\hspace{0.2cm}T_{\rm enh}(X, U) \right ]_{\substack{X=\beta \\ U=1} } \hspace{0.05cm}.\]





Hinweise:

  •   der Bhattacharyya–Parameter  $\beta$,
  •   die Bhattacharyya–Schranke  ${\rm Pr}(\rm Bhattacharyya)$, und
  •   die Viterbi–Schranke  $\rm Pr(Viterbi)$.
  • Im Verlauf dieser Aufgabe sollen Sie die entsprechenden Größen für  $\varepsilon = 10^{-2}$  und  $\varepsilon = 10^{-4}$ berechnen.
  • Die vollständige Tabelle finden Sie in der Musterlösung.



Fragebogen

1

Welcher Bhattacharyya–Parameter ergibt sich für das BSC–Modell?

$\varepsilon = 10^{–2} \text{:} \hspace{0.4cm} \beta \ = \ $

$\varepsilon = 10^{–4} \text{:} \hspace{0.4cm} \beta \ = \ $

2

Wie lautet die Bhattacharyya–Schranke?

$\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ $

$\ \cdot 10^{–4}$
$\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ $

$\ \cdot 10^{–9}$

3

Wie lautet die Viterbi–Schranke?

$\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ $

$\ \cdot 10^{–4}$
$\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ $

$\ \cdot 10^{–9}$

4

Für welche Werte  $\varepsilon < \varepsilon_0$  sind beide Schranken nicht anwendbar?

$\varepsilon_0 \ = \ $


Musterlösung

(1)  Der Bhattacharyya–Parameter ergibt sich für das BSC–Modell mit $\varepsilon = 0.01$ zu

$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} \hspace{0.2cm}\underline {\approx 0.199} \hspace{0.05cm}.$$

Für noch kleinere Verfälschungswahrscheinlichkeiten $\varepsilon$ kann näherungsweise geschrieben werden:

$$\beta \approx 2 \cdot \sqrt{\varepsilon } \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.2cm} \beta \hspace{0.2cm}\underline {\approx 0.02} \hspace{0.05cm}.$$


(2)  Es gilt ${\rm Pr(Burstfehler)} ≤ {\rm Pr(Bhattacharyya)}$ mit ${\rm Pr(Bhattacharyya)} = T(X = \beta)$.

  • Für den betrachteten Faltungscode der Rate 1/2, dem Gedächtnis $m = 2$ und $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$ lautet die Pfadgewichtsfunktion:
$$T(X) = \frac{X^5 }{1- 2X} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = T(X = \beta) = \frac{\beta^5 }{1- 2\beta}$$
$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm} {\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{1- 2\cdot 0.199} \hspace{0.2cm}\underline {\approx 5.18 \cdot 10^{-4}}\hspace{0.05cm},$$
$$\hspace{0.85cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm} {\rm Pr(Bhattacharyya)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{1- 2\cdot 0.02} \hspace{0.38cm}\underline {\approx 3.33 \cdot 10^{-9}}\hspace{0.05cm}.$$


(3)  Zur Berechnung der Viterbi–Schranke gehen wir von der erweiterten Pfadgewichtsfunktion aus:

$$T_{\rm enh}(X, U) = \frac{U X^5}{1- 2UX} \hspace{0.05cm}.$$
  • Die Ableitung dieser Funktion nach dem Eingangsparameter $U$ lautet:
$$\frac {\rm d}{{\rm d}U}\hspace{0.1cm}T_{\rm enh}(X, U) = \frac{(1- 2UX) \cdot X^5 - U X^5 \cdot (-2X)}{(1- 2UX)^2} = \frac{ X^5}{(1- 2UX)^2} \hspace{0.05cm}.$$
  • Diese Gleichung liefert für $U = 1$ und $X = \beta$ die Viterbi–Schranke:
$$\frac {\rm d}{{\rm d}U}\hspace{0.1cm}T_{\rm enh}(X, U) = \frac{(1- 2UX) \cdot X^5 - U X^5 \cdot (-2X)}{(1- 2UX)^2} = \frac{U X^5}{(1- 2UX)^2} \hspace{0.05cm}.$$
$$\Rightarrow \hspace{0.3cm}\varepsilon = 10^{-2}\hspace{-0.1cm}: \hspace{0.1cm} {\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.199^5 }{(1- 2\cdot 0.199)^2} = \hspace{0.2cm}\underline {\approx 8.61 \cdot 10^{-4}}\hspace{0.05cm},$$
$$\hspace{0.85cm} \varepsilon = 10^{-4}\hspace{-0.1cm}: \hspace{0.1cm} {\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \frac{0.02^5 }{(1- 2\cdot 0.02)^2} = \hspace{0.2cm}\underline {\approx 3.47 \cdot 10^{-9}}\hspace{0.05cm}.$$
  • Wir überprüfen das Ergebnis anhand der folgenden Näherung:
$$T_{\rm enh}(X, U) = U X^5 + 2\hspace{0.05cm}U^2 X^6 + 4\hspace{0.05cm}U^3 X^7 + 8\hspace{0.05cm}U^4 X^8 + \text{...} $$
$$\Rightarrow \hspace{0.3cm}\frac {\rm d}{{\rm d}U}\hspace{0.1cm}T_{\rm enh}(X, U) = X^5 + 4\hspace{0.05cm}U X^6 + 12\hspace{0.05cm}U^2 X^7 + 32\hspace{0.05cm}U^3 X^8 + \text{...} $$
  • Setzt man $U = 1$ und $X = \beta$ so erhält man wieder die Viterbi–Schranke:
$${\rm Pr(Viterbi)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \beta^5 + 4\hspace{0.05cm}\beta^6 + 12\hspace{0.05cm}\beta^7 + 32\hspace{0.05cm}\beta^8 +\text{...} = \beta^5 \cdot (1+ 4\hspace{0.05cm}\beta + 12\hspace{0.05cm}\beta^2 + 32\hspace{0.05cm}\beta^3 + ... )\hspace{0.05cm}. $$
  • Für $\varepsilon = 10^{–2} \ \Rightarrow \ \beta = 0.199$ erhält man, wenn man die unendliche Summe nach dem $\beta^3$–Term abbricht:
$${\rm Pr(Viterbi)} \approx 3.12 \cdot 10^{-4} \cdot (1 + 0.796 + 0.475 + 0.252) = 7.87 \cdot 10^{-4} \hspace{0.05cm}.$$
  • Der Abbruchfehler – bezogen auf $8.61 \cdot 10^{–4}$ – beträgt hier ca. $8.6\%$. Für $\varepsilon = 10^{–4} \ \Rightarrow \ \beta = 0.02$ ist der Abbruchfehler noch geringer:
$${\rm Pr(Viterbi)} \approx 3.20 \cdot 10^{-9} \cdot (1 + 0.086 + 0.0048 + 0.0003) = 3.47 \cdot 10^{-9} \hspace{0.05cm}.$$


Bhattacharyya– und die Viterbi–Schranke beim BSC–Modell (vollständige Tabelle)

(4)  Für $\beta = 0.5$ ergeben sich für beide Schranken der Wert "unendlich".

  • Für noch größere $\beta$–Werte wird die Bhattacharyya–Schranke negativ und auch das Ergebnis für die Viterbi–Schranke ist dann nicht anwendbar. Daraus folgt:
$$\beta_0 = 2 \cdot \sqrt{\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.5$$
$$\Rightarrow \hspace{0.3cm} {\varepsilon_0 \cdot (1- \varepsilon_0)} = 0.25^2 = 0.0625$$
$$\Rightarrow \hspace{0.3cm} \varepsilon_0^2 - \varepsilon_0 + 0.0625 = 0$$
$$\Rightarrow \hspace{0.3cm} \varepsilon_0 = 0.5 \cdot (1 - \sqrt{0.75}) \hspace{0.15cm} \underline {\approx 0.067}\hspace{0.05cm}.$$