Difference between revisions of "Aufgaben:Exercise 1.5Z: SPC (5, 4) vs. RC (5, 1)"
Line 3: | Line 3: | ||
}} | }} | ||
− | [[File:P_ID2386__KC_Z_1_5.png|right|frame|Single parity check code and | + | [[File:P_ID2386__KC_Z_1_5.png|right|frame|Single parity-check code and repetition code with $n = 5$]] |
− | There is a certain relationship between the | + | There is a certain relationship between the "single parity-check code" and the "repetition code" of the same code length $n$. As will be shown in the chapter [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]] they are so called "dual codes". |
− | *The [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity_Check_Codes| | + | *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 four information bits $u_{1}$, ... , $u_{4}$ a check bit $p$ so that an even number of ones occurs in each code word $\underline{x}$: |
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$ | :$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$ | ||
Revision as of 11:52, 14 June 2022
There is a certain relationship between the "single parity-check code" and the "repetition code" of the same code length $n$. As will be shown in the chapter "General Description of Linear Block Codes" they are so called "dual codes".
- The single parity-check code with parameters $k = 4$ and $n = 5$ ⇒ $\rm SPC \ (5, 4)$ adds to the four information bits $u_{1}$, ... , $u_{4}$ a check bit $p$ so that an even number of ones occurs in each code word $\underline{x}$:
- $$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$
- Each Repetition Code is characterized by the code parameter $k = 1$ . For $\rm RC \ (5, \ 1)$ the two code words are $(0, 0, 0, 0)$ and $(1, 1, 1, 1)$.
The graphic shows the basic structure of these two codes, which will be compared in this task.
Hints:
- This exercise belongs to the chapter Examples of Binary Block Codes.
- Reference is made in particular to the pages Single Parity Check Codes and Repetition Codes.
Questions
Solution
- in the Single Parity Check code considered here, there are 16 codewords ($k = 4$), and
- in the repeat code, only two codewords ($k = 1$).
(2) For any single parity check code, the number of ones is even ⇒ answers 1 and 3.
(3) For any repetition code, there are only two codewords (independent of $n$), both given here ⇒ Answer 1 and 4.
(4) Due to bit errors, there can always be $N = 2^n \hspace{0.15cm}\underline{= 32}$ different bit combinations for the receive vector $\underline{y}$, all of which must be included in the maximum likelihood decision.
- This is true for both the SPC (5, 4) and the RC (5, 1).
(5) For the SPC (5, 4), the Hamming distance between any two codewords is at least $d_{\rm min} \hspace{0.15cm}\underline{= 2}$. In contrast, for RC (5, 1), all bits of the two codewords are different ⇒ $d_{\rm min} \hspace{0.15cm}\underline{= 5}$.
(6) Error detection is possible as long as there are no more than $e = d_{\rm min} - 1$ bit errors in a codeword.
- Using the result from (5), we obtain $\underline{e = 1}$ (SPC) or $\underline{e = 4}$ (RC).
(7) In general, for the number of correctable errors:
- $$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$
- For any single parity check code, ($d_{\rm min} - 1)/2 = 0.5$ ⇒ $\underline{t = 0}$.
- In contrast, RC (5, 1) can be used to correct errors up to $\underline{t = 2}$ because of $d_{\rm min} = 5$.