Difference between revisions of "Aufgaben:Exercise 5.6Z: Gilbert-Elliott Model"
From LNTwww
| Line 1: | Line 1: | ||
| − | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Digital_Signal_Transmission/Burst_Error_Channels}} |
| − | [[File:P_ID1843__Dig_Z_5_6.png|right|frame| | + | [[File:P_ID1843__Dig_Z_5_6.png|right|frame|Given Gilbert–Elliott model]] |
| − | + | We consider the <i>burst error channel model</i> according to [https://en.wikipedia.org/wiki/Edgar_Gilbert "E.N. Gilbert"] and E.O. Elliott (see sketch). For the transition probabilities let hold: | |
:$${\rm Pr}(\rm | :$${\rm Pr}(\rm | ||
G\hspace{0.05cm}|\hspace{0.05cm} B)= 0.1, \hspace{0.2cm} {\rm | G\hspace{0.05cm}|\hspace{0.05cm} B)= 0.1, \hspace{0.2cm} {\rm | ||
Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) = 0.01\hspace{0.05cm}.$$ | Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) = 0.01\hspace{0.05cm}.$$ | ||
| − | + | The error probability in the state "GOOD" is $p_{\rm G} = 0.1\%$. For the state "BAD" is $p_{\rm B} = 10\%$. | |
| − | + | In the course of this exercise, further parameters are to be determined: | |
| − | * | + | * the average error probability $p_{\rm M}$, |
| − | * | + | * the state probabilities $w_{\rm G} = \rm Pr(Z = G)$ and $w_{\rm B} = \rm Pr(Z = B)$, |
| − | * | + | * the values of the correlation function, which for $k > 0$ is given analytically as follows: |
:$$\varphi_{e}(k) = p_{\rm M}^2 + (p_{\rm B} - | :$$\varphi_{e}(k) = p_{\rm M}^2 + (p_{\rm B} - | ||
p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot | p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot | ||
| Line 25: | Line 25: | ||
| − | '' | + | ''Notes:'' |
| − | * | + | * The exercise belongs to the chapter [[Digital_Signal_Transmission/Burst_Error_Channels| "Burst Error Channels"]]. |
| − | * | + | *However, reference is also made to the chapter [[Theory_of_Stochastic_Signals/Markov_Chains| "Markov chains"]] in the book "Theory of Stochastic Signals" and in particular to the section [[Digital_Signal_Transmission/Burst_Error_Channels#Error_correlation_function_of_the_Gilbert-Elliott_model|"Error correlation function of the Gilbert-Elliott model"]] in the book "Channel Coding". |
| Line 33: | Line 33: | ||
| − | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {What are the following transition probabilities? |
|type="{}"} | |type="{}"} | ||
$\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}G) \ = \ ${ 0.99 3% } | $\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}G) \ = \ ${ 0.99 3% } | ||
$\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}B) \hspace{0.2cm} = \ ${ 0.9 3% } | $\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}B) \hspace{0.2cm} = \ ${ 0.9 3% } | ||
| − | { | + | {With what probabilities is the GE model in the state "GOOD" $(w_{\rm G})$ or in the state "BAD" $(w_{\rm B})$? |
|type="{}"} | |type="{}"} | ||
$w_{\rm G} \ = \ $ { 0.909 3% } | $w_{\rm G} \ = \ $ { 0.909 3% } | ||
$w_{\rm B} \ = \ $ { 0.091 3% } | $w_{\rm B} \ = \ $ { 0.091 3% } | ||
| − | { | + | {Calculate the mean error probability $p_{\rm M}$. |
|type="{}"} | |type="{}"} | ||
$p_{\rm M} \ = \ $ { 1 3% } $\ \%$ | $p_{\rm M} \ = \ $ { 1 3% } $\ \%$ | ||
| − | { | + | {Calculate the following ECF values: |
|type="{}"} | |type="{}"} | ||
$\varphi_e(k = 1) \hspace{0.35cm} = \ ${ 8.209 3% } $\ \cdot 10^{-4}$ | $\varphi_e(k = 1) \hspace{0.35cm} = \ ${ 8.209 3% } $\ \cdot 10^{-4}$ | ||
| Line 56: | Line 56: | ||
$\varphi_e(k = 50) \ = \ ${ 1.024 3% } $\ \cdot 10^{-4}$ | $\varphi_e(k = 50) \ = \ ${ 1.024 3% } $\ \cdot 10^{-4}$ | ||
| − | { | + | {What is the size of the ECF value $\varphi_e(k = 0)$? |
|type="{}"} | |type="{}"} | ||
$\varphi_e(k = 0) \ = \ ${ 1 3% } $\ \cdot 10^{-2}$ | $\varphi_e(k = 0) \ = \ ${ 1 3% } $\ \cdot 10^{-2}$ | ||
| − | { | + | {Can the mean error probability $p_{\rm M} = 0.005$ be achieved by |
|type="[]"} | |type="[]"} | ||
| − | - | + | - sole change of $p_{\rm G}$, |
| − | + | + | + sole change of $p_{\rm B}$, |
| − | - | + | - sole change of $\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}B)$, |
| − | + | + | + sole change of $\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}G)$? |
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' | + | '''(1)''' $\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}G) = 1 \, –Pr(B\hspace{0.05cm}|\hspace{0.05cm}G) \ \underline {= 0.99}$ and $\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}B) = 1 \, –Pr(G\hspace{0.05cm}|\hspace{0.05cm}B) \ \underline {= 0.9}$ are valid. |
| − | '''(2)''' | + | '''(2)''' The GE model is a stationary Markov chain. |
| − | * | + | *For the probability that it is in the state "GOOD", taking into account the result of subtask '''(1)''': |
:$$w_{\rm G} = {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} G) \cdot | :$$w_{\rm G} = {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} G) \cdot | ||
w_{\rm G} + {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdot | w_{\rm G} + {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdot | ||
| Line 83: | Line 83: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | * | + | *Further, $w_{\rm B} = 1 \, –w_{\rm G}$: |
:$${\rm Pr}(\rm | :$${\rm Pr}(\rm | ||
B\hspace{0.05cm}|\hspace{0.05cm} G) \cdot w_{\rm G} + {\rm Pr}(\rm | B\hspace{0.05cm}|\hspace{0.05cm} G) \cdot w_{\rm G} + {\rm Pr}(\rm | ||
| Line 97: | Line 97: | ||
| − | '''(3)''' | + | '''(3)''' The mean error probability $p_{\rm M}$ is obtained from the error probabilities $p_{\rm G}$ and $p_{\rm B}$ weighted by $w_{\rm G}$ and $w_{\rm B}$: |
:$$p_{\rm M} = w_{\rm G} \cdot p_{\rm G} + w_{\rm B} \cdot p_{\rm B} | :$$p_{\rm M} = w_{\rm G} \cdot p_{\rm G} + w_{\rm B} \cdot p_{\rm B} | ||
= \frac{10}{11} \cdot 10^{-3} + \frac{1}{11} \cdot 10^{-1}= \frac{10+100}{11} \cdot 10^{-3}\hspace{0.15cm}\underline { = | = \frac{10}{11} \cdot 10^{-3} + \frac{1}{11} \cdot 10^{-1}= \frac{10+100}{11} \cdot 10^{-3}\hspace{0.15cm}\underline { = | ||
| Line 103: | Line 103: | ||
| − | '''(4)''' | + | '''(4)''' According to the general equation on the specification section, for $k > 0$: |
:$$\varphi_{e}(k) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} p_{\rm M}^2 + | :$$\varphi_{e}(k) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} p_{\rm M}^2 + | ||
(p_{\rm B} - p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot | (p_{\rm B} - p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot | ||
| Line 125: | Line 125: | ||
| − | '''(5)''' | + | '''(5)''' For each channel model, because of $e_{\nu} ∈ \{0, 1\}$: |
:$$\varphi_{e}(k = 0 ) = {\rm E}[e_{\nu} ^2] = {\rm E}[e_{\nu} ] = | :$$\varphi_{e}(k = 0 ) = {\rm E}[e_{\nu} ^2] = {\rm E}[e_{\nu} ] = | ||
p_{\rm M} \hspace{0.05cm}.$$ | p_{\rm M} \hspace{0.05cm}.$$ | ||
| − | + | Using the result of subtask '''(3)''', $\varphi_e(k = 0) \ \underline {= 0.01}$ for the present case. | |
Revision as of 03:48, 19 September 2022
Given Gilbert–Elliott model
We consider the burst error channel model according to "E.N. Gilbert" and E.O. Elliott (see sketch). For the transition probabilities let hold:
- $${\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)= 0.1, \hspace{0.2cm} {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) = 0.01\hspace{0.05cm}.$$
The error probability in the state "GOOD" is $p_{\rm G} = 0.1\%$. For the state "BAD" is $p_{\rm B} = 10\%$.
In the course of this exercise, further parameters are to be determined:
- the average error probability $p_{\rm M}$,
- the state probabilities $w_{\rm G} = \rm Pr(Z = G)$ and $w_{\rm B} = \rm Pr(Z = B)$,
- the values of the correlation function, which for $k > 0$ is given analytically as follows:
- $$\varphi_{e}(k) = p_{\rm M}^2 + (p_{\rm B} - p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot \big [1 - {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G )- {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B )\big ]^{\it k} \hspace{0.05cm}.$$
Notes:
- The exercise belongs to the chapter "Burst Error Channels".
- However, reference is also made to the chapter "Markov chains" in the book "Theory of Stochastic Signals" and in particular to the section "Error correlation function of the Gilbert-Elliott model" in the book "Channel Coding".
Questions
Solution
(1) $\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}G) = 1 \, –Pr(B\hspace{0.05cm}|\hspace{0.05cm}G) \ \underline {= 0.99}$ and $\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}B) = 1 \, –Pr(G\hspace{0.05cm}|\hspace{0.05cm}B) \ \underline {= 0.9}$ are valid.
(2) The GE model is a stationary Markov chain.
- For the probability that it is in the state "GOOD", taking into account the result of subtask (1):
- $$w_{\rm G} = {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} G) \cdot w_{\rm G} + {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdot w_{\rm B}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) \cdot w_{\rm G} = {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdot w_{\rm B} \hspace{0.05cm}.$$
- Further, $w_{\rm B} = 1 \, –w_{\rm G}$:
- $${\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) \cdot w_{\rm G} + {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdot w_{\rm G} = {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)$$
- $$\Rightarrow \hspace{0.3cm} w_{\rm G} = \frac{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)} = \frac{0.1}{0.1 + 0.01} \hspace{0.15cm}\underline {\approx 0.909} \hspace{0.05cm},\hspace{0.2cm} w_{\rm B} = 1 - w_{\rm G }\hspace{0.15cm}\underline {\approx 0.091}\hspace{0.05cm}.$$
(3) The mean error probability $p_{\rm M}$ is obtained from the error probabilities $p_{\rm G}$ and $p_{\rm B}$ weighted by $w_{\rm G}$ and $w_{\rm B}$:
- $$p_{\rm M} = w_{\rm G} \cdot p_{\rm G} + w_{\rm B} \cdot p_{\rm B} = \frac{10}{11} \cdot 10^{-3} + \frac{1}{11} \cdot 10^{-1}= \frac{10+100}{11} \cdot 10^{-3}\hspace{0.15cm}\underline { = 1\%}\hspace{0.05cm}.$$
(4) According to the general equation on the specification section, for $k > 0$:
- $$\varphi_{e}(k) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} p_{\rm M}^2 + (p_{\rm B} - p_{\rm M}) \cdot (p_{\rm M} - p_{\rm G}) \cdot [1 - {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G )- {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B )]^{\it k} = 10^{-4} + 0.09 \cdot 0.009 \cdot 0.89^{\it k} = 10^{-4} \cdot \left ( 1 + 8.1 \cdot 0.89^{\it k} \right )\hspace{0.05cm}.$$
- $$\Rightarrow \hspace{0.3cm}\varphi_{e}(k = 1 ) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 10^{-4} \cdot \left ( 1 + 8.1 \cdot 0.89^{ 1} \right ) \hspace{0.15cm}\underline {= 8.209 \cdot 10^{-4}} \hspace{0.05cm},$$
- $$\Rightarrow \hspace{0.3cm}\varphi_{e}(k = 2 ) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 10^{-4} \cdot \left ( 1 + 8.1 \cdot 0.89^{ 2} \right )\hspace{0.15cm}\underline { = 7.416 \cdot 10^{-4}} \hspace{0.05cm},$$
- $$\Rightarrow \hspace{0.3cm}\varphi_{e}(k = 5 ) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 10^{-4} \cdot \left ( 1 + 8.1 \cdot 0.89^{ 5} \right )\hspace{0.15cm}\underline {= 5.523 \cdot 10^{-4}} \hspace{0.05cm},$$
- $$\Rightarrow \hspace{0.3cm}\varphi_{e}(k = 50 ) \hspace{-0.1cm} \ = \ \hspace{-0.1cm} 10^{-4} \cdot \left ( 1 + 8.1 \cdot 0.89^{ 50} \right ) \hspace{0.15cm}\underline {= 1.024 \cdot 10^{-4}} \hspace{0.05cm}.$$
(5) For each channel model, because of $e_{\nu} ∈ \{0, 1\}$:
- $$\varphi_{e}(k = 0 ) = {\rm E}[e_{\nu} ^2] = {\rm E}[e_{\nu} ] = p_{\rm M} \hspace{0.05cm}.$$
Using the result of subtask (3), $\varphi_e(k = 0) \ \underline {= 0.01}$ for the present case.
(6) Entsprechend der Teilaufgabe (3) gilt:
- $$p_{\rm M} = {10}/{11} \cdot p_{\rm G} + {1}/{11} \cdot p_{\rm B} \hspace{0.05cm}.$$
- Bei vorgegebenem $p_{\rm B} = 0.1$ ergibt sich selbst für $p_{\rm G} = 0$ (kein Fehler im Zustand "G") die mittlere Fehlerwahrscheinlichkeit zu $p_{\rm M} \approx 0.009$.
- Dagegen ist mit festem $p_{\rm G} = 0.001$ der Wert $p_{\rm M} = 0.005$ erreichbar:
- $$0.005 = {10}/{11} \cdot 10^{-3} + {1}/{11} \cdot p_{\rm B} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} p_{\rm B} \le 0.055 - 0.1 = 4.5\%\hspace{0.05cm}.$$
- Weiterhin kann die mittlere Fehlerwahrscheinlichkeit (mit vorgegebenem $p_{\rm G}$ und $p_{\rm B}$) auch wie folgt dargestellt werden:
- $$p_{\rm M} = \frac{p_{\rm G} \cdot {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)+ p_{\rm B} \cdot {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)} = \frac{0.001 \cdot {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)+ 0.1 \cdot {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}\hspace{0.05cm}.$$
- Mit $\rm Pr(B|G) = 0.01$ bzw. mit $\rm Pr(G|B) = 0.1$ erhält man folgende Gleichungen:
- $${\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) = 0.01\hspace{-0.15cm}:\hspace{0.2cm} {\it p}_{\rm M} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} \frac{0.001 \cdot {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B)+ 0.001 }{{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) + 0.01}\hspace{0.05cm},\hspace{0.5cm} {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) = 0.1\hspace{-0.15cm}:\hspace{0.2cm}{\it p}_{\rm M} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} \frac{0.0001 + 0.1 \cdot {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{0.1 +{\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) }\hspace{0.05cm}.$$
- Aus der letzten Gleichung ist zu erkennen, dass mit keinem $\rm Pr(G|B)$–Wert das Ergebnis $p_{\rm M} = 0.005$ möglich ist.
- Dagegen lässt sich durch ein kleineres $\rm Pr(B|G)$ die Bedingung erfüllen:
- $$0.005 = \frac{0.0001 + 0.1 \cdot {\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G)}{0.1 +{\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) } \hspace{0.3cm} \Rightarrow \hspace{0.3cm}{\rm Pr}(\rm B\hspace{0.05cm}|\hspace{0.05cm} G) \le \frac{0.0004}{0.095} \approx 0.0042\hspace{0.05cm}.$$
- Richtig sind somit die Lösungsvorschläge 2 und 4.
