Exercise 1.07Z: Classification of Block Codes

Block codes of length $n = 4$ Korrektur code

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 pages "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$ codewords.
Statement 3 is false. For example, if the first bit is $0$, there is one codeword starting $00$ and two codewords 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 cardinality $|\mathcal{C}|$ is not a power of two,
gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid codeword.

(3) Statements 1 to 3 are correct:

In a systematic code, the first $k$ bits of each codeword $\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 a unit 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 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 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 generator matrix $\boldsymbol {\rm G}$ of "Code 3" is a $2×4$ matrix and the parity-check matrix $\boldsymbol {\rm H}$ 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.