Exercise 1.07Z: Classification of Block Codes

Block codes of length $n = 4$

We consider block codes of length $n = 4$:

the single parity–check code $\text{SPC (4, 3)}$ ⇒ "code 1" with the generator matrix

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

the repetition code $\text{RC (4, 1)}$ ⇒ "code 2" with the parity-check matrix

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

the $\text{(4, 2)}$ block code ⇒ "code 3" with the generator matrix

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

the $\text{(4, 2)}$ block code ⇒ "code 4" with the generator matrix

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

another "code 5" with code size $|\hspace{0.05cm}C\hspace{0.05cm}| = 6$.

The individual codes are explicitly indicated in the graphic. The questions for these tasks are about the terms

"linear codes",

"systematic codes",

"dual codes".

Hints :

This exercise belongs to the chapter "General description of linear block codes".

Reference is also made to the sections "Single parity–check codes" and "Repetition codes".

Questions

Solution

(1) Statements 1 and 2 are correct:

That is why there are "$\rm 4 \ over \ 2 = 6$" code words.
Statement 3 is false. For example, if the first bit is "$0$", there is one code word starting "$00$" and two code words starting "$01$".

(2) Statements 1 to 4 are correct:

All codes that can be described by a generator matrix $\boldsymbol {\rm G}$ and/or a parity-check matrix $\boldsymbol {\rm H}$ are linear.
In contrast, "code 5" does not satisfy any of the conditions required for linear codes. For example

is missing the all-zero word,
the code size $|\mathcal{C}|$ is not a power of two,
gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid code word.

(3) Statements 1 to 3 are correct:

In a systematic code, the first $k$ bits of each code word $\underline{x}$ must always be equal to the information word $\underline{u}$.
This is achieved if the beginning of the generator matrix $\boldsymbol {\rm G}$ is an identity matrix $\boldsymbol{\rm I}_{k}$.
This is true for "code 1" $($with dimension $k = 3)$, "code 2" $($with $k = 1)$ and "code 3" $($with $k = 2)$.
The generator matrix of "code 2", however, is not explicitly stated. It is:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

(4) Statement 1 is correct:

Dual codes are those where the parity-check matrix $\boldsymbol {\rm H}$ of one code is equal to the generator matrix $\boldsymbol {\rm G}$ of the other code.
For example, this is true for "code 1" and "code 2."
For the $\text{SPC (4, 3)}$ holds:

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm} { \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

and for the repetition code $\text{RC (4, 1)}$:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm} { \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

Statement 2 is certainly wrong, already for dimensional reasons: The $\boldsymbol {\rm G}$ matrix of "code 3" is a $2×4$ matrix and the $\boldsymbol {\rm H}$ matrix of "code 2" is a $3×4$ matrix.

"Code 3" and "code 4" also do not satisfy the conditions of dual codes. The parity-check equations of

$${\rm Code}\hspace{0.15cm}3 = \{ (0, 0, 0, 0) \hspace{0.05cm},\hspace{0.1cm} (0, 1, 1, 0) \hspace{0.05cm},\hspace{0.1cm}(1, 0, 0, 1) \hspace{0.05cm},\hspace{0.1cm}(1, 1, 1, 1) \}$$

are as follows:

$$x_1 \oplus x_4 = 0\hspace{0.05cm},\hspace{0.2cm}x_2 \oplus x_3 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$

In contrast, the generator matrix of "code 4" is given as follows:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

	code 1,
	code 2,
	code 3,
	code 4,
	code 5.

	code 1,
	code 2,
	code 3,
	code 4,
	code 5.

	There are exactly two zeros in each code word.
	There are exactly two ones in each code word.
	After each "$0$", the symbols "$0$" and "$1$" are equally likely.