Difference between revisions of "Aufgaben:Exercise 1.5: SPC (5, 4) and BEC Model"
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Examples_of_Binary_Block_Codes |
}} | }} | ||
− | [[File:P_ID2385__KC_A_1_5_neu.png|right|frame| | + | [[File:P_ID2385__KC_A_1_5_neu.png|right|frame|Code words of the $\rm SPC \ (5, 4)$]] |
− | + | For this exercise it is required: | |
− | * | + | *The [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity_Check_Codes|Single Parity-check Code]] with parameters $k = 4$ and $n = 5$ ⇒ $\rm SPC \ (5, 4)$ adds to the information bits $u_{1}$, ... , $u_{4}$ adds a check bit $p$ so that an even number of ones occurs in each codeword $\underline{x}$ : |
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$ | :$$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}.$$ | :$$ u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$ | ||
− | * | + | *The [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channel]] (BEC) - with binary input values $x_{i} \in \{0, \ 1\}$ and ternary output $y_{i} \in \{0, 1, \rm E\}$ leads with probability $\lambda = 0.1$ to an extinction (English: ''Erasure''), abbreviated as $\rm E$. |
− | * | + | *Furthermore, ${\rm Pr}(y_{i} = x_{i}) = 1 - \lambda = 0.9$ holds. 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}.$$ | :$$ {\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 $\underline{u}$ and the codeword $\underline{x}$ is given by the table. From the receive word $\underline{y}$ the vector $\underline{v}$ of information bits at the sink is formed by maximum likelihood decision, which should match the information word $\underline{u}$ 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{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}.$$ | :$$ \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 $\underline{v} =\underline{\rm E} = {\rm (E, E, E, E)}$ indicates that decoding of the code word is not possible due to too many erasures. | |
Line 28: | Line 28: | ||
− | + | Hints: | |
− | * | + | *This exercise belongs to the chapter [[Channel_Coding/Examples_of_Binary_Block_Codes|Examples of binary block codes]]. |
− | * | + | *Reference is also made to the chapter [[Channel_Coding/Channel_Models_and_Decision_Structures|Channel Models and Decision Structures]]. |
− | * | + | *The check bits of $u_{0}$, $u_{4}$ and $u_{13}$ are to be determined in the subtask '''(1)''''. |
− | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
− | + | {What is the check bit $p$ for each of the following information words $\underline{u}$ ? | |
− | { | ||
|type="{}"} | |type="{}"} | ||
$\underline{u} = \underline{u_{0}}\text{:}\hspace{0.4cm}p \ = \ $ { 0. } | $\underline{u} = \underline{u_{0}}\text{:}\hspace{0.4cm}p \ = \ $ { 0. } | ||
Line 46: | Line 45: | ||
$\underline{u} = \underline{u_{13}}\text{:}\hspace{0.25cm}p \ = \ $ { 1 } | $\underline{u} = \underline{u_{13}}\text{:}\hspace{0.25cm}p \ = \ $ { 1 } | ||
− | { | + | { Let $ \underline{y} = (0, 0, 0, {\rm E})$. What information word was sent? |
|type="()"} | |type="()"} | ||
+ $ \underline{u}_{0}$, | + $ \underline{u}_{0}$, | ||
Line 53: | Line 52: | ||
− | { | + | {let $ \underline{y} = (0, {\rm E}, 0, 0, 1)$. What information word was sent? |
|type="()"} | |type="()"} | ||
- $\underline{u}_{0}$, | - $\underline{u}_{0}$, | ||
Line 59: | Line 58: | ||
- $\underline{u}_{13}$. | - $\underline{u}_{13}$. | ||
− | { | + | {With what probability does $\underline{y}$ match the codeword $\underline{x}$ ? |
|type="{}"} | |type="{}"} | ||
$\ {\rm Pr} (\underline{y} = \underline{x}) \ = \ ${ 59.1 3% } $\ \%$ | $\ {\rm Pr} (\underline{y} = \underline{x}) \ = \ ${ 59.1 3% } $\ \%$ | ||
− | { | + | {With what probability do the two vectors $\underline{u}$ and $\underline{v}$ match? |
|type="{}"} | |type="{}"} | ||
$\ {\rm Pr} (\underline{v} = \underline{u}) \ = \ $ { 91.9 3% } $\ \%$ | $\ {\rm Pr} (\underline{v} = \underline{u}) \ = \ $ { 91.9 3% } $\ \%$ | ||
− | { | + | {What is the probability of a detected error? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm Pr} (\underline{\upsilon} = {\rm {\underline{ E | + | $\ {\rm Pr} (\underline{\upsilon} = {\rm {\underline{ E}}) \ = \ $ { 8.1 3% } $\ \%$ |
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
Line 84: | Line 83: | ||
'''(2)''' Richtig ist die <u>Antwort 1</u>: | '''(2)''' Richtig ist die <u>Antwort 1</u>: | ||
− | * | + | *Because of the fact that the number of ones must be even, the erased check bit $p = 0$. Thus, $\underline{u}_{0}$ was sent. |
− | '''(3)''' | + | '''(3)''' Correct is <u>answer 2</u>: |
− | * | + | *According to the same considerations as in the last subtask, we arrive at $\underline{y} = (0, |
− | {\rm E}, 0, 0, 1)$ | + | {\rm E}, 0, 0, 1)$ to the result. |
:$$\underline{x} = \underline{x}_{4} = (0, 1, 0, 0, 1) ⇒ \underline{u}_{4} = (0, 1, 0, 0).$$ | :$$\underline{x} = \underline{x}_{4} = (0, 1, 0, 0, 1) ⇒ \underline{u}_{4} = (0, 1, 0, 0).$$ | ||
− | '''(4)''' | + | '''(4)''' The event $\underline{y} = \underline{x}$ occurs only if none of the $n = 5$ code bits is cleared 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}.$$ | :$${\rm Pr}(\underline{y} = \underline{x}) = (1 - \lambda)^5 = 0.9^5 \hspace{0.15cm} \underline{= 59.1\%} \hspace{0.05cm}.$$ | ||
− | '''(5)''' | + | '''(5)''' The event $v = u$ then occurs, |
− | * | + | *if all code bits are transmitted correctly ⇒ ${\rm Pr}(\underline{y} = \underline{x})$, |
− | * | + | *but also when only one codebit is erased. According to the binomial distribution, there are 5 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 = | + | :$${\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)''' | + | '''(6)''' Due to the BEC model, the corruption of a codeword $\underline{x}$ is per se impossible, since none of the bits from $0 → 1$ or from $1 → 0$ can be corrupted. 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}.$$ | :$${\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}.$$ | ||
Revision as of 04:38, 11 June 2022
For this exercise it is required:
- The Single Parity-check Code with parameters $k = 4$ and $n = 5$ ⇒ $\rm SPC \ (5, 4)$ adds to the information bits $u_{1}$, ... , $u_{4}$ adds a check bit $p$ so that an even number of ones occurs in each codeword $\underline{x}$ :
- $$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 Binary Erasure Channel (BEC) - with binary input values $x_{i} \in \{0, \ 1\}$ and ternary output $y_{i} \in \{0, 1, \rm E\}$ leads with probability $\lambda = 0.1$ to an extinction (English: Erasure), abbreviated as $\rm E$.
- Furthermore, ${\rm Pr}(y_{i} = x_{i}) = 1 - \lambda = 0.9$ holds. 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 $\underline{u}$ and the codeword $\underline{x}$ is given by the table. From the receive word $\underline{y}$ the vector $\underline{v}$ of information bits at the sink is formed by maximum likelihood decision, which should match the information word $\underline{u}$ 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 $\underline{v} =\underline{\rm E} = {\rm (E, E, E, E)}$ indicates that decoding of the code word is not possible due to too many erasures.
Hints:
- This exercise belongs to the chapter Examples of binary block codes.
- Reference is also made to the chapter Channel Models and Decision Structures.
- The check bits of $u_{0}$, $u_{4}$ and $u_{13}$ are to be determined in the subtask (1)'.
Questions
Solution
(1) Das Prüfbit $p$ wird beim Single Parity–check Code so bestimmt, dass die Summe aller Einsen im Codewort $\underline{x} = (u_{1}, u_{2}, ... , u_{4}, p)$ geradzahlig ist.
Beispielsweise erhält man:
- $$\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) Richtig ist die Antwort 1:
- Because of the fact that the number of ones must be even, the erased check bit $p = 0$. Thus, $\underline{u}_{0}$ was sent.
(3) Correct is answer 2:
- According to the same considerations as in the last subtask, we arrive at $\underline{y} = (0, {\rm E}, 0, 0, 1)$ to the result.
- $$\underline{x} = \underline{x}_{4} = (0, 1, 0, 0, 1) ⇒ \underline{u}_{4} = (0, 1, 0, 0).$$
(4) The event $\underline{y} = \underline{x}$ occurs only if none of the $n = 5$ code bits is cleared 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) The event $v = u$ then occurs,
- if all code bits are transmitted correctly ⇒ ${\rm Pr}(\underline{y} = \underline{x})$,
- but also when only one codebit is erased. According to the binomial distribution, there are 5 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) Due to the BEC model, the corruption of a codeword $\underline{x}$ is per se impossible, since none of the bits from $0 → 1$ or from $1 → 0$ can be corrupted. 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}.$$