Aufgaben:Exercise 1.07Z: Classification of Block Codes

• Return to book

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

1 How can  "code 5"  be described?

	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.

2 Which of the following block codes are linear?

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

3 Which of the following block codes are systematic?

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

4 Which code pairs are dual to each other?

	code 1 and code 2,
	code 2 and code 3,
	code 3 and code 4.

Solution

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