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

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

$\ {\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}| \ = \ $

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

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

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

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

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

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

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

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

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

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

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