Aufgaben:Exercise 1.10: Some Generator Matrices

• Return to book

Considered generator matrices

We now consider various binary codes of uniform length  $n$. All codes of the form

$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1, x_2, \ \text{...} \ \hspace{0.05cm}, x_n) \hspace{0.5cm}\text{mit} \hspace{0.5cm} x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0, 1 \},\hspace{0.2cm} i = 1, \hspace{0.05cm} \text{...} \ \hspace{0.05cm}, n$$

can be represented and interpreted in an $n$-dimensional vector space.   ⇒   ${\rm GF}(2^n)$.

A  $k×n$ generator matrix  $\mathbf{G}$  (i.e. a matrix with  $k$  rows and  $n$  columns) yields a  $(n, \, k)$ code, but only if the rank of the matrix  $\mathbf{G}$  is also equal  $k$ . Further holds:

• Each code  $\mathcal{C}$  spans a  $k$-dimensional linear subspace of the Galois field  ${\rm GF}(2^n)$ .

• As basis vectors of this subspace,  $k$  independent codewords of  $\mathcal{C}$  can be used. There is no further restriction for the basis vectors.

• The parity-check matrix  $\mathbf{H}$  also spans a subspace of  ${\rm GF}(2^n)$  . But this has dimension  $m = n - k$  and is orthogonal to the subspace based on  $\mathbf{G}$ .

• For a linear code,  $\underline{x} = \underline{u} - \boldsymbol{ {\rm G}}$, where  $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$  indicates the information word. A systematic code exists if  $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$  holds.

• In a systematic code, there is a simple relationship between  $\mathbf{G}$  and  $\mathbf{H}$. For more details, see the  theory section.

Hints :

• This exercise belongs to the chapter  General Description of Linear Block Codes.
• For the whole exercise holds  $n = 6$.
• In the subtask (4) it is to be clarified which of the matrices  $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ resp. $ \boldsymbol{ {\rm G}}_{\rm C}$  result in a $(6, \, 3)$ block code with the code words listed below:

$$ ( 0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 0, 1, 0, 1, 1), \hspace{0.1cm}(0, 1, 0, 1, 0, 1), \hspace{0.1cm}(0, 1, 1, 1, 1, 0), \hspace{0.1cm} ( 1, 0, 0, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1), \hspace{0.1cm}(1, 1, 0, 0, 1, 1), \hspace{0.1cm}(1, 1, 1, 0, 0, 0)\hspace{0.05cm}.$$

Questions

1

Known are only the two code words  $(0, 1, 0, 1, 0, 1)$  and  $(1, 0, 0, 1, 1, 0)$  of a linear code. Which statements are true?

	It could be a  $(5, \, 2)$ code.
	It could be a  $(6, \, 2)$ code.
	It could be a  $(6, \, 3)$ code.

2

What are the four code words of the linear  $(6, \, 2)$ code explicitly?

	$(0 0 1 0 1 1), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).$
	$(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).$
	$(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 1 0 0 0).$

3

Which statements are true for this  $(6, \, 2)$ code $C$?

	For all codewords  $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$  $\underline{x}_{i} \in {\rm GF}(2^6)$.
	$C$  is a two-dimensional linear subvector space of  ${\rm GF}(2^6)$.
	$\mathbf{G}$  gives basis vectors of this subvector space  ${\rm GF}(2^2)$ .
	$\mathbf{G}$  and  $\mathbf{H}$  are each  $2×6$ matrices.

4

Which of the generator matrices given in the graphic result in a  $(6, \, 3)$ code?

	the generator matrix  $\boldsymbol{ {\rm G}}_{\rm A}$,
	the generator matrix  $\boldsymbol{ {\rm G}}_{\rm B}$,
	the generator matrix  $\boldsymbol{ {\rm G}}_{\rm C}$.

Solution

Solution

(1)  Correct are the suggested solutions 2 and 3:

• The codeword length is $n = $6  ⇒  the $(5, \, 2)$ code is not eligible.
• For a $(6, \, 2)$ code, there are $2^2 = 4$ distinct codewords, and for the $(6, \, 3)$ code, there are correspondingly $2^3 = 8$.
• By specifying only two codewords, neither the $(6, \, 2)$ code nor the $(6, \, 3)$ code can be excluded.

(2)  Correct is the solution suggestion 2:

• Since this is a linear code, the modulo $2$ sum must also be a valid codeword:

$$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.$$

• Likewise the all zero word:

$$(0, 1, 0, 1, 0, 1) \oplus (0, 1, 0, 1, 0, 1) = (0, 0, 0, 0, 0, 0)\hspace{0.05cm}.$$

(3)  Correct here are the statements 1 to 3:

• Basis vectors of the generator matrix $\mathbf{G}$ are, for example, the two given codewords, from which the parity-check matrix $\mathbf{H}$ can also be determined:

$${ \boldsymbol{\rm G}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 0 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 1 &0 &0 &0 &1 &0\\ 0 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

• In general, the $k$ basis vectors of the generator matrix $\mathbf{G}$ form a $k$-dimensional subspace and the $m×n$ matrix $\mathbf{H}$ (with $m = n - k$) forms an orthogonal subspace of dimension $m$.

Note: The code given here

$$\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 0, 1), (1, 0, 0, 1, 1, 0), \hspace{0.1cm}(1, 1, 0, 0, 1, 1) \}$$

is not very effective, since $p_{1} = x_{3}$ is always $0$. By puncturing this redundant bit you get the code

$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 1, 0, 1), (1, 0, 1, 1, 0), \hspace{0.1cm}(1, 1, 0, 1, 1) \}$$

with the same minimum distance $d_{\rm min} = 3$, but larger code rate $R = 2/5$ compared to $R = 1/3$.

(4)  Correct are the suggested solutions 1 and 2:

• The three rows $g_1, \ g_2$ and $g_3$ of the matrix $\mathbf{G}_{\rm A}$ are suitable as basis vectors, since they are linearly independent, that is, it holds

$$\underline{g}_1 \oplus \underline{g}_2 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_3\hspace{0.05cm},\hspace{0.5cm} \underline{g}_1 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_2\hspace{0.05cm},\hspace{0.5cm} \underline{g}_2 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_1\hspace{0.05cm}.$$

• The same is true for matrix $\mathbf{G}_{\rm B}$. The basis vectors are chosen here so that the code is also systematic.

• For the last generator matrix holds: $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$   ⇒   the rank of matrix (2) is smaller than its order (3).
• Here not only $\underline{u} = (0, 0, 0)$ leads to the codeword $(0, 0, 0, 0, 0)$, but also $\underline{u} = (1, 1, 1)$.