Difference between revisions of "Aufgaben:Exercise 2.15Z: Block Error Probability once more"

Latest revision as of 15:37, 2 November 2022

Binominal probabilities

Using a Reed–Solomon code with the correctability $t$ and "Bounded Distance Decoding" $\rm $ $\rm (BDD)$ is obtained for the block error probability with

the code word length $n$ and

the symbol falsification probability $\varepsilon_{\rm S}$:

$${\rm Pr(block\:error)} = \sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm}.$$

In this exercise, the block error probability for the $\rm RSC \, (7, \, 3, \, 5)_8$ and various $\varepsilon_{\rm S}$ values shall be calculated and approximated.

The above equation is reminiscent of the "Biomial Distribution".

The graph shows the probabilities of the binomial distribution for parameters $n = 7$ ("code word length") and $\varepsilon_{\rm S} = 0.25$ ("symbol falsification probability").

Hints:

This exercise belongs to the chapter "Error Probability and Application Areas".

For checking, you can use the interactive HTML5/JavaScript applet "Binomial and Poisson Distribution".

Questions

$\rm Pr(block\:error) \ = \ $

$\ \cdot 10^{-2}$

$\rm Pr(block\:error) \ = \ $

$\ \cdot 10^{-5}$

$\rm Approximation \text{:} \hspace{0.2cm} Pr(block\:error) \ \approx \ $

$\ \cdot 10^{-5}$

$\rm Pr(block\:error) \ \approx \ $

$\ \cdot 10^{-8}$

$\varepsilon_{\rm S} \ = \ $

$\ \cdot 10^{-4}$

Solution

(1) For the $\rm RSC \, (7, \, 3, \, 5)_8$, because $d_{\rm min} = 5 \ \Rightarrow \ t = 2$ gives the block error probability:

$${\rm Pr(block\:error)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{f = 3}^{7} {7 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{7-f} $$

$$\Rightarrow \hspace{0.3cm}{\rm Pr(block\:error)} ={7 \choose 3} \cdot 0.1^3 \cdot 0.9^4 + {7 \choose 4} \cdot 0.1^4 \cdot 0.9^3 + {7 \choose 5} \cdot 0.1^5 \cdot 0.9^2+ {7 \choose 6} \cdot 0.1^6 \cdot 0.9+ {7 \choose 7} \cdot 0.1^7 \hspace{0.05cm}.$$

According to this calculation, five terms would have to be considered. However, since

$${\rm Pr(block\:error)} = \sum_{f = 0}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} = 1$$

is also valid, the following calculation is faster:

$${\rm Pr(block\:error)} =1 - \big [ {7 \choose 0} \cdot 0.9^7 + {7 \choose 1} \cdot 0.1 \cdot 0.9^6 + {7 \choose 2} \cdot 0.1^2 \cdot 0.9^5 \big ] =1 - \big [ 0.4783 + 0.3720 + 0.1240 \big ] \hspace{0.15cm} \underline{= 2.57 \cdot 10^{-2}} \hspace{0.05cm}.$$

(2) Analogous to the subtask (1) one obtains here:

$${\rm Pr(block\:error)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - \big [ 0.99^7 + 7 \cdot 0.01 \cdot 0.99^6 + 21 \cdot 0.01^2 \cdot 0.99^5 \big ] =1 - \big [ 0.9321 + 0.0659 + 0.0020 \big ] \approx 0 \hspace{0.05cm}.$$

This means: For the probability $\varepsilon_{\rm S} = 0.01$ the simplified calculation is very error-prone, because a value close to $1$ results for the bracket expression.

The full calculation yields here:

$${\rm Pr(block\:error)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {7 \choose 3} \cdot 0.01^3 \cdot 0.99^4 + {7 \choose 4} \cdot 0.01^4 \cdot 0.99^3 + {7 \choose 5} \cdot 0.01^5 \cdot 0.99^2+ {7 \choose 6} \cdot 0.01^6 \cdot 0.99+ {7 \choose 7} \cdot 0.01^7 $$

$$\Rightarrow \hspace{0.3cm}{\rm Pr(block\:error)}= 10^{-6} \cdot \big [ 33.6209 + 0.3396 + 0.0021 + ... \big ] \hspace{0.15cm} \underline{ \approx 3.396 \cdot 10^{-5}} \hspace{0.05cm}.$$

(3) From the sample solution to the subtask (2) the result can be read directly:

$${\rm Pr(block\:error)} \hspace{0.15cm} \underline{ \approx 3.362 \cdot 10^{-5}} \hspace{0.05cm}.$$

The relative error is about $-1\%$.

The minus sign indicates that this is only an approximation and not a bound: The approximate value is slightly smaller than the actual value.

(4) Restricting to the relevant term $(f = 3)$, we get $\varepsilon_{\rm S} = 0.001$:

$${\rm Pr(block\:error)} \approx {7 \choose 3} \cdot [10^{-3}]^3 \cdot 0.999^4 \hspace{0.15cm} \underline{ \approx 3.49 \cdot 10^{-8}} \hspace{0.05cm}.$$

The relative error here is only about $-0.1\%$.

(5) According to the derived approximation, the following holds for the considered code:

$${\rm Pr(block\:error)} \approx {7 \choose 3} \cdot {\varepsilon_{\rm S}}^3 = 35 \cdot {\varepsilon_{\rm S}}^3\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr(block\:error)} = 10^{-10}: \hspace{0.4cm} {\varepsilon_{\rm S}} = \big ( \frac{10^{-10}}{35} \big )^{1/3} = 2.857^{1/3} \cdot 10^{-4} \hspace{0.15cm} \underline{ \approx 1.42 \cdot 10^{-4}}\hspace{0.05cm}.$$

@@ Line 1: / Line 1: @@
-{{quiz-Header|Buchseite=Kanalcodierung/Fehlerwahrscheinlichkeit und Anwendungsgebiete}}
+{{quiz-Header|Buchseite=Channel_Coding/Error_Probability_and_Areas_of_Application}}
-[[File:P_ID2574__KC_Z_2_15.png|right|frame|Wahrscheinlichkeiten der Binominalverteilung]]
+[[File:P_ID2574__KC_Z_2_15.png|right|frame|Binominal probabilities]]
-Bei Verwendung eines Reed&ndash;Solomon&ndash;Codes mit der Korrekturfähigkeit $t$ und [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete#Blockfehlerwahrscheinlichkeit_f.C3.BCr_RSC_und_BDD|Bounded Distance Decoding]] (BDD) erhält man mit
+Using a Reed&ndash;Solomon code with the correctability&nbsp; $t$&nbsp; and&nbsp; [[Channel_Coding/Error_Probability_and_Areas_of_Application#Block_error_probability_for_RSC_and_BDD|"Bounded Distance Decoding"]]&nbsp; $\rm $&nbsp; $\rm (BDD)$&nbsp; is obtained for the block error probability with
-* der Codewortlänge $n$ und
+* the code word length&nbsp; $n$&nbsp; and
-* der Symbolverfälschungswahrscheinlichkeit $\epsilon_{\rm S}$
+* the symbol falsification probability&nbsp; $\varepsilon_{\rm S}$:
-für die Blockfehlerwahrscheinlichkeit:
+:$${\rm Pr(block\:error)}  =
-:$${\rm Pr(Blockfehler)}  =
 \sum_{f = t + 1}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} \hspace{0.05cm}.$$
-In dieser Aufgabe soll die Blockfehlerwahrscheinlichkeit für den $\rm RSC \, (7, \, 3, \, 5)_8$ und verschiedene $\epsilon_{\rm S}$&ndash;Werte berechnet und angenähert werden. Obige Gleichung erinnert an die [[Stochastische_Signaltheorie/Binomialverteilung|Biomialverteilung]]. Die Grafik zeigt die Wahrscheinlichkeiten der Binomialverteilung für die Parameter $n = 7$ (Codewortlänge) und $\epsilon_{\rm S} = 0.25$ (Symbolverfälschungswahrscheinlichkeit).
+In this exercise,&nbsp; the block error probability for the&nbsp; $\rm RSC \, (7, \, 3, \, 5)_8$&nbsp; and various&nbsp; $\varepsilon_{\rm S}$&nbsp; values shall be calculated and approximated.
-''Hinweise:''
+*The above equation is reminiscent of the&nbsp; [[Theory_of_Stochastic_Signals/Binomial_Distribution|"Biomial Distribution"]].&nbsp;
-* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Fehlerwahrscheinlichkeit_und_Anwendungsgebiete| Fehlerwahrscheinlichkeit und Anwendungsgebiete]].
-* Zur Kontrolle können Sie das folgende interaktive Flash&ndash;Modul nutzen:
-# [[Wahrscheinlichkeiten der Binomialverteilung]]
+*The graph shows the probabilities of the binomial distribution for parameters&nbsp; $n = 7$&nbsp; ("code word length") and&nbsp; $\varepsilon_{\rm S} = 0.25$&nbsp; ("symbol falsification probability").
-===Fragebogen===
+Hints:
+* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Error_Probability_and_Areas_of_Application| "Error Probability and Application Areas"]].
+* For checking,&nbsp; you can use the interactive HTML5/JavaScript applet&nbsp; [[Applets:Binomial_and_Poisson_Distribution_(Applet)|"Binomial and Poisson Distribution"]].
+===Questions===
 <quiz display=simple>
-{Multiple-Choice
+{What is the block error probability for&nbsp; $\varepsilon_{\rm S} = 10^{-1}$?
-|type="[]"}
+|type="{}"}
-+ correct
+$\rm Pr(block\:error) \ = \ ${ 2.57 3% } $\ \cdot 10^{-2}$
-- false
+{What is the block error probability for&nbsp; $\varepsilon_{\rm S} =10^{-2}$?
+|type="{}"}
+$\rm Pr(block\:error) \ = \ ${ 3.396 3% } $\ \cdot 10^{-5}$
+{What result is obtained for&nbsp; $\varepsilon_{\rm S} =10^{-2}$,&nbsp; considering only the term&nbsp; $f = t + 1$&nbsp;?
+|type="{}"}
+$\rm Approximation \text{:} \hspace{0.2cm} Pr(block\:error) \ \approx \ ${ 3.362 3% } $\ \cdot 10^{-5}$
+{What result is obtained approximately for&nbsp; $\varepsilon_{\rm S} = 10^{-3}$?
+|type="{}"}
+$\rm Pr(block\:error) \ \approx \ ${ 3.49 3% } $\ \cdot 10^{-8}$
-{Input-Box Frage
+{What&nbsp; $\varepsilon_{\rm S}$&nbsp; is needed for the block error probability&nbsp; $10^{-10}$?
 |type="{}"}
-$xyz \ = \ ${ 5.4 3% } $ab$
+$\varepsilon_{\rm S} \ = \ ${ 1.42 3% } $\ \cdot 10^{-4}$
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp;
+'''(1)'''&nbsp; For the&nbsp; $\rm RSC \, (7, \, 3, \, 5)_8$,&nbsp; because&nbsp; $d_{\rm min} = 5 \ \Rightarrow \ t = 2$&nbsp; gives the block error probability:
-'''(2)'''&nbsp;
+:$${\rm Pr(block\:error)}  \hspace{-0.15cm} \ = \ \hspace{-0.15cm}
-'''(3)'''&nbsp;
+\sum_{f = 3}^{7} {7 \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{7-f} $$
-'''(4)'''&nbsp;
+:$$\Rightarrow \hspace{0.3cm}{\rm Pr(block\:error)} ={7 \choose 3} \cdot 0.1^3 \cdot 0.9^4 + {7 \choose 4} \cdot 0.1^4 \cdot 0.9^3
-'''(5)'''&nbsp;
++ {7 \choose 5} \cdot 0.1^5 \cdot 0.9^2+
+ {7 \choose 6} \cdot 0.1^6 \cdot 0.9+ {7 \choose 7} \cdot 0.1^7
+\hspace{0.05cm}.$$
+*According to this calculation,&nbsp; five terms would have to be considered.&nbsp; However,&nbsp; since
+:$${\rm Pr(block\:error)}  =
+\sum_{f = 0}^{n} {n \choose f} \cdot {\varepsilon_{\rm S}}^f \cdot (1 - \varepsilon_{\rm S})^{n-f} = 1$$
+:is also valid,&nbsp; the following calculation is faster:
+:$${\rm Pr(block\:error)} =1 - \big [ {7 \choose 0}  \cdot 0.9^7 + {7 \choose 1} \cdot 0.1 \cdot 0.9^6
++ {7 \choose 2} \cdot 0.1^2 \cdot 0.9^5 \big ] =1 - \big [ 0.4783 + 0.3720 + 0.1240  \big ] \hspace{0.15cm} \underline{= 2.57 \cdot 10^{-2}}
+\hspace{0.05cm}.$$
+'''(2)'''&nbsp; Analogous to the subtask&nbsp; '''(1)'''&nbsp; one obtains here:
+:$${\rm Pr(block\:error)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1 - \big [ 0.99^7 + 7 \cdot 0.01 \cdot 0.99^6
++ 21 \cdot 0.01^2 \cdot 0.99^5 \big ] =1 - \big [ 0.9321 + 0.0659 + 0.0020  \big ] \approx 0
+\hspace{0.05cm}.$$
+*This means: &nbsp; For the probability&nbsp; $\varepsilon_{\rm S} = 0.01$&nbsp; the simplified calculation is very error-prone,&nbsp; because a value close to&nbsp; $1$&nbsp; results for the bracket expression.
+*The full calculation yields here:
+:$${\rm Pr(block\:error)}  \hspace{-0.15cm} \ = \ \hspace{-0.15cm}
+{7 \choose 3} \cdot 0.01^3 \cdot 0.99^4 + {7 \choose 4} \cdot 0.01^4 \cdot 0.99^3 +
+{7 \choose 5} \cdot 0.01^5 \cdot 0.99^2+  {7 \choose 6} \cdot 0.01^6 \cdot 0.99+
+{7 \choose 7} \cdot 0.01^7 $$
+:$$\Rightarrow \hspace{0.3cm}{\rm Pr(block\:error)}= 10^{-6} \cdot
+\big [ 33.6209 +  0.3396 + 0.0021 + ... \big ] \hspace{0.15cm} \underline{ \approx  3.396 \cdot 10^{-5}}
+\hspace{0.05cm}.$$
+'''(3)'''&nbsp; From the sample solution to the subtask&nbsp; '''(2)'''&nbsp; the result can be read directly:
+:$${\rm Pr(block\:error)} \hspace{0.15cm}  \underline{ \approx  3.362 \cdot 10^{-5}}
+\hspace{0.05cm}.$$
+*The relative error is about&nbsp; $-1\%$.
+*The minus sign indicates that this is only an approximation and not a bound:&nbsp; The approximate value is slightly smaller than the actual value.
+'''(4)'''&nbsp; Restricting to the relevant term&nbsp; $(f = 3)$,&nbsp; we get&nbsp; $\varepsilon_{\rm S} = 0.001$:
+:$${\rm Pr(block\:error)}  \approx
+{7 \choose 3} \cdot [10^{-3}]^3 \cdot 0.999^4  \hspace{0.15cm} \underline{ \approx  3.49 \cdot 10^{-8}}
+\hspace{0.05cm}.$$
+*The relative error here is  only about&nbsp; $-0.1\%$.
+'''(5)'''&nbsp; According to the derived approximation,&nbsp; the following holds for the considered code:
+:$${\rm Pr(block\:error)}  \approx {7 \choose 3} \cdot {\varepsilon_{\rm S}}^3 = 35 \cdot {\varepsilon_{\rm S}}^3\hspace{0.3cm}
+\Rightarrow  \hspace{0.3cm} {\rm Pr(block\:error)} = 10^{-10}: \hspace{0.4cm} {\varepsilon_{\rm S}} =
+\big ( \frac{10^{-10}}{35} \big )^{1/3} = 2.857^{1/3} \cdot 10^{-4}
+\hspace{0.15cm} \underline{ \approx  1.42 \cdot 10^{-4}}\hspace{0.05cm}.$$
 {{ML-Fuß}}
@@ Line 45: / Line 118: @@
-[[Category:Aufgaben zu  Kanalcodierung|^2.6 Fehlerwahrscheinlichkeit und Anwendungsgebiete^]]
+[[Category:Channel Coding: Exercises|^2.6 Block Error Probability of RS Codes^]]