Aufgaben:Exercise 1.07Z: Classification of Block Codes

• Return to book

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

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