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

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