Aufgaben:Aufgabe 3.14: Fehlerwahrscheinlichkeitsschranken: Unterschied zwischen den Versionen
(17 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken}} | {{quiz-Header|Buchseite=Kanalcodierung/Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken}} | ||
− | [[Datei:P_ID2713__KC_A_3_14.png|right|frame| | + | [[Datei: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 [[Kanalcodierung/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 + ... | + | :$$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 | + | * Die <i>Burstfehlerwahrscheinlichkeit</i> wird durch die <b>Bhattacharyya–Schranke</b> 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 | + | * Dagegen ist die <i>Bitfehlerwahrscheinlichkeit</i> stets kleiner (oder gleich) der <b>Viterbi–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 [[Kanalcodierung/Distanzeigenschaften_und_Fehlerwahrscheinlichkeitsschranken| Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken]]. |
− | * Der Bhattacharyya–Parameter für BSC lautet: | + | * Der Bhattacharyya–Parameter für BSC lautet: $\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}$. |
− | + | * In obiger Tabelle sind für einige Werte des BSC–Parameters $\varepsilon$ angegeben: | |
− | * In obiger Tabelle sind für einige Werte des BSC–Parameters $\ | + | :* 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. |
− | * Im Verlauf dieser Aufgabe sollen Sie die entsprechenden Größen für $\ | + | * Die vollständige Tabelle finden Sie in der Musterlösung. |
− | * Die vollständige Tabelle finden Sie | + | |
− | |||
Zeile 42: | Zeile 48: | ||
{Welcher Bhattacharyya–Parameter ergibt sich für das BSC–Modell? | {Welcher Bhattacharyya–Parameter ergibt sich für das BSC–Modell? | ||
|type="{}"} | |type="{}"} | ||
− | $\ | + | $\varepsilon = 10^{–2} \text{:} \hspace{0.4cm} \beta \ = \ ${ 0.199 3% } |
− | $\ | + | $\varepsilon = 10^{–4} \text{:} \hspace{0.4cm} \beta \ = \ ${ 0.02 3% } |
{Wie lautet die Bhattacharyya–Schranke? | {Wie lautet die Bhattacharyya–Schranke? | ||
|type="{}"} | |type="{}"} | ||
− | $\ | + | $\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 5.18 3% } $\ \cdot 10^{–4}$ |
− | $\ | + | $\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 3.33 3% } $\ \cdot 10^{–9}$ |
{Wie lautet die Viterbi–Schranke? | {Wie lautet die Viterbi–Schranke? | ||
|type="{}"} | |type="{}"} | ||
− | $\ | + | $\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ ${ 8.61 3% } $\ \cdot 10^{–4}$ |
− | $\ | + | $\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ ${ 3.47 3% } $\ \cdot 10^{–9}$ |
− | {Für welche Werte $\ | + | {Für welche Werte $\varepsilon < \varepsilon_0$ sind beide Schranken nicht anwendbar? |
|type="{}"} | |type="{}"} | ||
− | $\ | + | $\varepsilon_0 \ = \ ${ 0.067 3% } |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' Der Bhattacharyya–Parameter ergibt sich für das BSC–Modell mit $\ | + | '''(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} | :$$\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 $\ | + | 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)''' 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: | + | '''(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} | :$$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{ | + | :$$\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}.$$ | ||
Zeile 92: | Zeile 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–Schranke: | + | *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 + ... | + | :$${\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 $\ | + | *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} | :$${\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 – bezogen auf $8.61 \cdot 10^{–4}$ – beträgt hier ca. $8.6\%$. Für $\ | + | *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} | :$${\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}.$$ | ||
− | + | [[Datei:P_ID2714__KC_A_3_14c.png|right|frame|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$$ | :$$\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}) | + | :$$\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 | + | [[Category:Aufgaben zu Kanalcodierung|^3.5 Distanzeigenschaften^]] |
Aktuelle Version vom 3. Juli 2019, 14:06 Uhr
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:
- Die Aufgabe gehört zum Kapitel Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken.
- Der Bhattacharyya–Parameter für BSC lautet: $\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}$.
- In obiger Tabelle sind für einige Werte des BSC–Parameters $\varepsilon$ angegeben:
- 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
Musterlösung
- $$\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}.$$
(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}.$$