View source for Aufgaben:Exercise 1.5: SPC (5, 4) and BEC Model

{{quiz-Header|Buchseite=Channel_Coding/Examples_of_Binary_Block_Codes

}}

[[File:P_ID2385__KC_A_1_5_neu.png|right|frame|Code words of the&nbsp; $\rm SPC \ (5, 4)$]]

For this exercise it is required:

*The&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity_Check_Codes|single parity-check code]] with parameters&nbsp; $k = 4$&nbsp; and&nbsp; $n = 5$&nbsp; &nbsp; ⇒ &nbsp; $\rm SPC \ (5, 4)$&nbsp; adds to the information bits&nbsp; $u_{1}$, ... ,&nbsp; $u_{4}$&nbsp; a check bit&nbsp; $p$&nbsp; so that an even number of ones occurs in each code word&nbsp; $\underline{x}$&nbsp;:
:$$x_1   \oplus   x_2  \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$
:$$ u_1   \oplus   u_2  \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$

*The&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channel]]&nbsp; $\rm (BEC)$ - with binary input values&nbsp; $x_{i} \in \{0, \ 1\}$&nbsp; and ternary output&nbsp; $y_{i} \in \{0,\ 1,\ \rm E\}$&nbsp; leads with probability&nbsp; $\lambda = 0.1$&nbsp; to an erasure&nbsp; $\rm E$.
 
*Furthermore,&nbsp; ${\rm Pr}(y_{i} = x_{i}) = 1 - \lambda = 0.9$&nbsp; holds.&nbsp; A real transmission error is excluded:
:$$ {\rm Pr} \big[(x_i = 0)\cap (y_i = 1)\big] = {\rm Pr} \big[(x_i = 1)\cap (y_i = 0)\big] = 0\hspace{0.05cm}.$$

The relationship between the information word&nbsp; $\underline{u}$&nbsp; and the code word&nbsp; $\underline{x}$&nbsp; is given by the table.&nbsp; From the receive word&nbsp; $\underline{y}$&nbsp; the vector&nbsp; $\underline{v}$&nbsp; of information bits at the sink is formed by maximum likelihood decision,&nbsp; which should match the information word&nbsp; $\underline{u}$&nbsp; as much as possible. 

The following nomenclature applies:
:$$\underline{u} \ \in \  \{\underline{u}_0,\ \underline{u}_1,\hspace{0.15cm} \text{...} \hspace{0.2cm},\ \underline{u}_{15}\} \hspace{0.05cm},$$
:$$ \underline{v} \ \in \  \{\underline{v}_0,\ \underline{v}_1, \hspace{0.15cm}\text{...} \hspace{0.2cm},\ \underline{v}_{15},\ \underline{\rm E}\} \hspace{0.05cm}.$$

The result&nbsp; $\underline{v} =\underline{\rm E} = {\rm (E,\ E,\ E,\ E)}$&nbsp; indicates that decoding of the code word is not possible due to too many erasures.






Hints:
*This exercise belongs to the chapter&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes|"Examples of binary block codes"]].
 
*Reference is also made to the chapter&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures|"Channel Models and Decision Structures"]].
 
*The check bits of&nbsp; $u_{0}$,&nbsp; $u_{4}$&nbsp; and&nbsp; $u_{13}$&nbsp; are to be determined in the subtask&nbsp; '''(1)''''.
 



===Questions===

<quiz display=simple>
{What is the check bit&nbsp; $p$&nbsp; for each of the following information words&nbsp; $\underline{u}$&nbsp; ?
|type="{}"}
$\underline{u} = \underline{u_{0}}\text{:}\hspace{0.4cm}p \ = \ $ { 0. }
$\underline{u} = \underline{u_{4}}\text{:}\hspace{0.4cm}p \ = \ $ { 1 }
$\underline{u} = \underline{u_{13}}\text{:}\hspace{0.25cm}p \ = \ $ { 1 }

{ Let&nbsp; $ \underline{y} = (0,\ 0,\ 0,\ 0,\ {\rm E})$.&nbsp; What information word was sent?
|type="()"}
+ $ \underline{u}_{0}$,
- $ \underline{u}_{4}$,
- $ \underline{u}_{13}$.


{Let&nbsp; $ \underline{y} = (0,\ {\rm E},\ 0,\ 0,\ 1)$.&nbsp; What information word was sent?
|type="()"}
- $\underline{u}_{0}$,
+ $\underline{u}_{4}$,
- $\underline{u}_{13}$.

{With what probability does&nbsp; $\underline{y}$&nbsp; match the code word&nbsp; $\underline{x}$&nbsp;?
|type="{}"}
$\ {\rm Pr} (\underline{y} = \underline{x}) \ = \ ${ 59.1 3% } $\ \%$

{With what probability do the two vectors&nbsp; $\underline{u}$&nbsp; and&nbsp; $\underline{v}$&nbsp; match?
|type="{}"}
$\ {\rm Pr} (\underline{v} = \underline{u}) \ = \ $ { 91.9 3% } $\ \%$

{What is the probability of a detected error?
|type="{}"}
$\ {\rm Pr} (\underline{\upsilon} = {\rm {\underline{ E}}}) \ = \ $ { 8.1 3% } $\ \%$


</quiz>

===Solution===
{{ML-Kopf}}

'''(1)'''&nbsp; The check bit&nbsp; $p$&nbsp; is determined in the "single parity-check code"&nbsp; in such a way,&nbsp;  that the sum of all ones in the code word $\underline{x} = (u_{1},\ u_{2}, ... ,\ u_{4},\ p)$&nbsp; is even.&nbsp;  <br>For example, one gets:
:$$\underline{u}_0 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (0, 0, 0, 0) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 0} \hspace{0.05cm},$$
:$$ \underline{u}_4 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (0, 1, 0, 0) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}_4 = (0, 1, 0, 0, 1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 1} \hspace{0.05cm},$$ 
:$$\underline{u}_{13} \hspace{-0.1cm}\ = \ \hspace{-0.1cm} (1, 1, 0, 1) \hspace{0.15cm} \Rightarrow \hspace{0.15cm} \underline{x}_{13} = (1, 1, 0, 1, 1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} p \hspace{0.15cm} \underline{= 1} \hspace{0.05cm}.$$


'''(2)'''&nbsp; Correct is&nbsp; <u>answer 1</u>:
*Because of the fact that the number of ones must be even,&nbsp; the erased check bit&nbsp; $p = 0$.&nbsp; Thus,&nbsp; $\underline{u}_{0}$ was sent. 



'''(3)'''&nbsp; Correct is&nbsp; <u>answer 2</u>:
*According to the same considerations as in the last subtask,&nbsp; we arrive with&nbsp; $\underline{y} = (0,\
 {\rm E},\ 0,\ 0,\ 1)$&nbsp; to the result 
:$$\underline{x} = \underline{x}_{4} = (0, 1, 0, 0, 1) ⇒ \underline{u}_{4} = (0, 1, 0, 0).$$


'''(4)'''&nbsp; The event&nbsp; $\underline{y} = \underline{x}$&nbsp; occurs only if none of the&nbsp; $n = 5$&nbsp; code bits is erased by the BEC channel:
:$${\rm Pr}(\underline{y} = \underline{x}) = (1 - \lambda)^5 = 0.9^5 \hspace{0.15cm} \underline{= 59.1\%} \hspace{0.05cm}.$$


'''(5)'''&nbsp; The event&nbsp; $v = u$&nbsp; then occurs, 
*if all code bits are transmitted correctly &nbsp; &rArr; &nbsp; ${\rm Pr}(\underline{y} = \underline{x})$, 
*but also when only one code bit is erased.&nbsp; According to the binomial distribution,&nbsp; there are five possibilities for this:
:$${\rm Pr}(\underline{v} = \underline{u}) \hspace{-0.1cm}\ = \ \hspace{-0.1cm} {\rm Pr}(\underline{y} = \underline{x}) + 5 \cdot (1 - \lambda)^4 \cdot \lambda =  0.591 + 5 \cdot 0.656^4 \cdot 0.1 \hspace{0.15cm} \underline{= 91.9 \%} \hspace{0.05cm}.$$


'''(6)'''&nbsp; Due to the BEC model,&nbsp; the falsification of a code word&nbsp; $\underline{x}$&nbsp; is per se impossible,&nbsp; since none of the bits can be falsified from&nbsp; $0 → 1$&nbsp; or from&nbsp; $1 → 0$.&nbsp; Rather:
:$${\rm Pr}(\underline{v} = \underline{u}) + {\rm Pr}(\underline{v} = {\rm\underline{ E}}) = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr}(\underline{v} = {\rm\underline{ E}}) = 1 - {\rm Pr}(\underline{v} = \underline{u}) \hspace{0.15cm} \underline{= 8.1\%} \hspace{0.05cm}.$$

{{ML-Fuß}}



[[Category:Channel Coding: Exercises|^1.3 Examples of Binary Block Codes^]]