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

deutscher Text:

• Ein jeder  Wiederholungscode  (englisch:   Repetition Code) ist durch den Codeparameter  $k = 1$  charakterisiert. Beim  $\rm RC \ (5, \ 1)$  lauten die beiden Codeworte  $(0, 0, 0, 0, 0)$  und  $(1, 1, 1, 1, 1)$.

Deine Übersetzung:

• 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 size?

$\ {\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 size 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 code words  ($k = 4$),  and
• in the repetition code,  only  two code words  ($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 code words  (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  $\text{SPC (5, 4)}$  and the  $\text{RC (5, 1)}$.

(5)  For the  $\text{SPC (5, 4)}$,  the Hamming distance between any two code words is at least  $d_{\rm min} \hspace{0.15cm}\underline{= 2}$.  In contrast,  for  $\text{RC (5, 1)}$,  all bits of the two code words 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 code word.

• 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,  $\text{RC (5, 1)}$  can be used to correct errors up to  $\underline{t = 2}$  because of  $d_{\rm min} = 5$.