Aufgaben:Exercise 1.5Z: SPC (5, 4) vs. RC (5, 1)

• Return to book

Single parity check code and Repetition code with  $n = 5$

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

1

How do the  $\text{SPC (5, 4)}$  and the  $\text{RC (5, 1)}$  differ in terms of code scope?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $

2

Which of the following code words are possible in the  $\text{SPC (5, 4)}$ ?

	$(0, 0, 0, 0, 0)$,
	$(0, 0, 1, 0, 0)$,
	$(1, 1, 0, 1, 1)$,
	$(1, 1, 1, 1, 1)$.

3

Which of the following code words are possible in the  $\text{RC (5, 1)}$ ?

	$(0, 0, 0, 0, 0)$,
	$(0, 0, 1, 0, 0)$,
	$(1, 1, 0, 1, 1)$,
	$(1, 1, 1, 1, 1)$.

4

How many code sequences  $(N)$  must be included in the maximum likelihood decision?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $

$ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}N \ = \ $

5

What is the minimum distance between the two codes?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

$\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $

6

Up to how many bit errors  $(e)$  does error detection work?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $

$ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $

7

Up to how many bit errors  $(t)$  does error correction work?

$\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $

$ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $

Solution

Solution

(1)  The code scope gives the number of possible code words. It holds $|\mathcal{C}| = 2^k$, so that there are.

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