Aufgaben:Exercise 5.6Z: Gilbert-Elliott Model

• Return to book

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

1 What are the following transition probabilities?

$\rm Pr(G\hspace{0.05cm}|\hspace{0.05cm}G) \ = \ $

$\rm Pr(B\hspace{0.05cm}|\hspace{0.05cm}B) \hspace{0.2cm} = \ $

2 With what probabilities is the GE model in the state "GOOD"  $(w_{\rm G})$  or in the state "BAD"  $(w_{\rm B})$?

$w_{\rm G} \ = \ $

$w_{\rm B} \ = \ $

3 Calculate the mean error probability  $p_{\rm M}$.

$p_{\rm M} \ = \ $ $\ \%$

4 Calculate the following ECF values:

$\varphi_e(k = 1) \hspace{0.35cm} = \ $ $\ \cdot 10^{-4}$

$\varphi_e(k = 2) \hspace{0.35cm} = \ $ $\ \cdot 10^{-4}$

$\varphi_e(k = 5) \hspace{0.35cm} = \ $ $\ \cdot 10^{-4}$

$\varphi_e(k = 50) \ = \ $ $\ \cdot 10^{-4}$

5 What is the size of the ECF value  $\varphi_e(k = 0)$?

$\varphi_e(k = 0) \ = \ $ $\ \cdot 10^{-2}$

6 Can the mean error probability  $p_{\rm M} = 0.005$  be achieved by

	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)$?

Solution

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) \cdotw_{\rm G} + {\rm Pr}(\rm G\hspace{0.05cm}|\hspace{0.05cm} B) \cdotw_{\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 \cdot0.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 \cdot10^{-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)  According to subtask (3) holds:

$$p_{\rm M} = {10}/{11} \cdot p_{\rm G} + {1}/{11} \cdotp_{\rm B} \hspace{0.05cm}.$$

• With given $p_{\rm B} = 0.1$, even for $p_{\rm G} = 0$ (no error in state "G"), the average error probability is $p_{\rm M} \approx 0.009$.
• In contrast, with fixed $p_{\rm G} = 0.001$ the value $p_{\rm M} = 0.005$ is achievable:

$$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}.$$

• Furthermore, the mean error probability (with given $p_{\rm G}$ and $p_{\rm B}$) can also be represented as follows:

$$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}.$$*With $\rm Pr(B|G) = 0.01$ and with $\rm Pr(G|B) = 0.1$, respectively, the following equations are obtained::$${\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}.$$

• From the last equation it can be seen that with no $\rm Pr(G|B)$ value the result $p_{\rm M} = 0.005$ is possible.
• On the other hand, with a smaller $\rm Pr(B|G)$ the condition can be fulfilled:

$$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}.$$

• Solutions 2 and 4 are therefore correct.