Aufgaben:Exercise 3.14: Error Probability Bounds - Revision history

Guenter at 17:15, 22 November 2022

2022-11-22T17:15:28Z

Guenter at 17:02, 22 November 2022

2022-11-22T17:02:07Z

Guenter at 16:51, 21 November 2022

2022-11-21T16:51:29Z

Guenter at 15:25, 21 November 2022

2022-11-21T15:25:03Z

Noah at 20:49, 20 October 2022

2022-10-20T20:49:01Z

Show changes

Guenter at 08:50, 13 October 2022

2022-10-13T08:50:04Z

Guenter: Guenter moved page Aufgaben:Aufgabe 3.14: Fehlerwahrscheinlichkeitsschranken to Aufgaben:Exercise 3.14: Error Probability Bounds

2022-10-13T08:47:03Z

Guenter moved page Aufgabe 3.14: Fehlerwahrscheinlichkeitsschranken to Exercise 3.14: Error Probability Bounds

Javier: Text replacement - "”" to """

2021-05-28T14:28:57Z

Text replacement - "”" to """

Javier: Text replacement - "„" to """

2021-05-28T14:28:36Z

Text replacement - "„" to """

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:50:20Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 59: / Line 59: @@
 $\varepsilon = 10^{-4} \text{:} \hspace{0.4cm} {\rm Pr(Bhattacharyya)} \ = \ ${ 3.33 3% } $\ \cdot 10^{&ndash;9}$
-{What is the viterbi bound?
+{What is the Viterbi bound?
 |type="{}"}
 $\varepsilon = 10^{-2} \text{:} \hspace{0.4cm} {\rm Pr(Viterbi)} \ = \ ${ 8.61 3% } $\ \cdot 10^{&ndash;4}$
@@ Line 71: / Line 71: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The Bhattacharyya parameter results for the BSC model with $\varepsilon = 0.01$ to
+'''(1)'''&nbsp; The Bhattacharyya parameter results for the BSC model with&nbsp; $\varepsilon = 0.01$&nbsp; to
 :$$\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}.$$
-For even smaller corruption probabilities $\varepsilon$ can be written approximately:
+*For even smaller falsification probabilities&nbsp; $\varepsilon$&nbsp; can be written approximately:
 :$$\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)'''&nbsp; It holds ${\rm Pr(Burst\:error)} &#8804; {\rm Pr(Bhattacharyya)}$ with ${\rm Pr(Bhattacharyya)} = T(X = \beta)$.
+'''(2)'''&nbsp; It holds&nbsp; ${\rm Pr(burst\:error)} &#8804; {\rm Pr(Bhattacharyya)}$&nbsp; with&nbsp; ${\rm Pr(Bhattacharyya)} = T(X = \beta)$.
-*For the considered convolutional code of rate 1/2, memory $m = 2$ and $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$, the path weighting enumerator function is:
+*For the considered convolutional code of rate 1/2,&nbsp; memory $m = 2$&nbsp; and&nbsp; $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$,&nbsp; the path weighting enumerator function is:
 :$$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}$$
@@ Line 90: / Line 90: @@
-'''(3)'''&nbsp; To calculate the Viterbi bound, we assume the extended path weighting enumerator function:
+'''(3)'''&nbsp; To calculate the Viterbi bound,&nbsp; we assume the&nbsp; "extended path weighting enumerator function":
 :$$T_{\rm enh}(X, U) =   \frac{U  X^5}{1- 2UX}  \hspace{0.05cm}.$$
-* The derivative of this function with respect to the input parameter $U$ is:
+* The derivative of this function with respect to the input parameter&nbsp; $U$ gives:
 :$$\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}.$$
-* This equation provides the Viterbi bound for $U = 1$ and $X = \beta$:
+* This equation provides the Viterbi bound for&nbsp; $U = 1$&nbsp; and&nbsp; $X = \beta$:
 :$$\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}
@@ Line 109: / Line 109: @@
 :$$\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{...} $$
-*Setting $U = 1$ and $X = \beta$ we get again the Viterbi bound:
+*Setting&nbsp; $U = 1$&nbsp; and&nbsp; $X = \beta$&nbsp; we get again the Viterbi bound:
 :$${\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}. $$
-*For $\varepsilon = 10^{&ndash;2} \ \Rightarrow \ \beta = 0.199$ is obtained by truncating the infinite sum after the $\beta^3$&ndash;term:
+*For&nbsp; $\varepsilon = 10^{&ndash;2} \ \Rightarrow \ \beta = 0.199$&nbsp; is obtained by truncating the infinite sum after the&nbsp; $\beta^3$&nbsp; term:
 :$${\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}.$$
-*The termination error &ndash; related to $8.61 \cdot 10^{&ndash;4}$ &ndash; here is about $8.6\%$. For $\varepsilon = 10^{&ndash;4} \ \Rightarrow \ \beta = 0.02$ the termination error is even smaller:
+*The termination error&nbsp; $($related to&nbsp; $8.61 \cdot 10^{&ndash;4})$&nbsp; is here about&nbsp; $8.6\%$.&nbsp; For $\varepsilon = 10^{&ndash;4} \ \Rightarrow \ \beta = 0.02$ the termination error is even smaller:
 :$${\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}.$$
-  [[File:EN_KC_A_3_14c.png|right|frame|Bhattacharyya and the Viterbi bound in the BSC model (full table).]]
+  [[File:EN_KC_A_3_14c.png|right|frame|Bhattacharyya and Viterbi bound in the BSC model&nbsp; $($full table$)$.]]
-'''(4)'''&nbsp; For $\beta = 0.5$ both bounds result in the value "infinite".
+'''(4)'''&nbsp; For&nbsp; $\beta = 0.5$&nbsp; both bounds result in the value&nbsp; "infinite".
-*For even larger $\beta$&ndash;values, the Bhattacharyya bound becomes negative and the result for the Viterbi bound is then also not applicable. It follows:
+*For even larger&nbsp; $\beta$&nbsp; values,&nbsp; the Bhattacharyya bound becomes negative and the result for the Viterbi bound is then also not applicable.&nbsp; It follows:
 :$$\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$$

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Distance_Characteristics_and_Error_Probability_Barriers}}
-[[File:EN_KC_A_3_14_neu.png|right|frame|Bhattacharyya and the Viterbi barrier in the BSC model (incomplete table).]]
+[[File:EN_KC_A_3_14_neu.png|right|frame|Bhattacharyya and Viterbi bound with the BSC model&nbsp; $($incomplete table$)$.]]
 For the frequently used convolutional code with
 * the code rate&nbsp; $R = 1/2$,
 * the memory&nbsp; $m = 2$, and
 * the transfer function matrix
-:$${\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 ), $$
-is the&nbsp; [[Channel_Coding/Distance_Characteristics_and_Error_Probability_Barriers#Enhanced_path_weighting_enumerator_function|"extended path weighting enumerator function"]]:
+the&nbsp; [[Channel_Coding/Distance_Characteristics_and_Error_Probability_Bounds#Enhanced_path_weighting_enumerator_function|"extended path weighting enumerator function"]] is:
 :$$T_{\rm enh}(X, U) =   \frac{UX^5}{1- 2 \hspace{0.05cm}U \hspace{-0.05cm}X}  \hspace{0.05cm}.$$
-With the already more frequently used series expansion&nbsp; $1/(1 \, &ndash;x) = 1 + x + x^2 + \text{...} \ $&nbsp; can also be written for this purpose:
+With the series expansion &nbsp; $1/(1 \, &ndash;x) = 1 + x + x^2 + \text{...} \ $ &nbsp; can also be written for this purpose:
 :$$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}.$$
-The "simple" path weighting enumerator function&nbsp; $T(X)$&nbsp; results from setting the second variable&nbsp; $U = 1$&nbsp;.
+The&nbsp; "simple path weighting enumerator function"&nbsp; $T(X)$&nbsp; results from setting the second variable&nbsp; $U = 1$&nbsp;.
-Using these two functions, error probability bounds can be specified:
+Using these two functions,&nbsp; error probability bounds can be specified:
-* The&nbsp; <i>burst error probability</i>&nbsp; is limited by the&nbsp; <b>Bhattacharyya barrier</b>&nbsp;:
+* The&nbsp; "burst error probability"&nbsp; is limited by the&nbsp; <b>Bhattacharyya bound</b>:
-:$${\rm Pr(Burst\:error)} \le {\rm Pr(Bhattacharyya)} = T(X = \beta) \hspace{0.05cm}.$$
+:$${\rm Pr(burst\:error)} \le {\rm Pr(Bhattacharyya)} = T(X = \beta) \hspace{0.05cm}.$$
-* In contrast, the&nbsp; <i>bit error probability</i>&nbsp; is always less than (or equal to) the&nbsp; <b>Viterbi bound</b>:
+* In contrast,&nbsp; the&nbsp; "bit error probability"&nbsp; is always less than&nbsp; $($or equal to$)$&nbsp; the&nbsp; <b>Viterbi bound</b>:
-::<math>{\rm Pr(Bit\:error)} \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(bit\:error)} \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>
@@ Line 28: / Line 30: @@
 * You can find the complete table in the sample solution.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Distance_Characteristics_and_Error_Probability_Barriers}}
-[[File:EN_KC_A_3_14.png|right|frame|Bhattacharyya and the Viterbi barrier in the BSC model (incomplete table).]]
+[[File:EN_KC_A_3_14_neu.png|right|frame|Bhattacharyya and the Viterbi barrier in the BSC model (incomplete table).]]
 For the frequently used convolutional code with
 * the code rate&nbsp; $R = 1/2$,

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Distance_Characteristics_and_Error_Probability_Barriers}}
-[[File:P_ID2713__KC_A_3_14.png|right|frame|Bhattacharyya and the Viterbi barrier in the BSC model (incomplete table).]]
+[[File:EN_KC_A_3_14.png|right|frame|Bhattacharyya and the Viterbi barrier in the BSC model (incomplete table).]]
 For the frequently used convolutional code with
 * the code rate&nbsp; $R = 1/2$,
@@ Line 119: / Line 119: @@
-  [[File:P_ID2714__KC_A_3_14c.png|right|frame|Bhattacharyya and the Viterbi bound in the BSC model (full table).]]
+  [[File:EN_KC_A_3_14c.png|right|frame|Bhattacharyya and the Viterbi bound in the BSC model (full table).]]
 '''(4)'''&nbsp; For $\beta = 0.5$ both bounds result in the value "infinite".

← Older revision		Revision as of 08:50, 13 October 2022
Line 131:		Line 131:


−	[[Category:Channel Coding: Exercises\|^3.5 ~~Distanzeigenschaften~~^]]	+	[[Category:Channel Coding: Exercises\|^3.5 Distance Properties^]]

@@ Line 14: / Line 14: @@
 :$$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&rdquo; Pfadgewichtsfunktion&nbsp; $T(X)$&nbsp; ergibt sich daraus, wenn man die zweite Variable&nbsp; $U = 1$&nbsp; setzt.
+Die "einfache" Pfadgewichtsfunktion&nbsp; $T(X)$&nbsp; ergibt sich daraus, wenn man die zweite Variable&nbsp; $U = 1$&nbsp; setzt.
 Anhand dieser beiden  Funktionen können Fehlerwahrscheinlichkeitsschranken angegeben werden:
@@ Line 120: / Line 120: @@
   [[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&rdquo;.
+'''(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:

← Older revision		Revision as of 12:50, 23 March 2021
Line 131:		Line 131:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^3.5 Distanzeigenschaften^]]	+	[[Category:Channel Coding: Exercises\|^3.5 Distanzeigenschaften^]]