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{with} \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)$.

The  $k×n$  generator matrix  $\mathbf{G}$  (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 code words 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} \cdot \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.3cm}(0, 0, 1, 0, 1, 1), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm}(0, 1, 1, 1, 1, 0), \hspace{0.3cm} ( 1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1), \hspace{0.3cm}(1, 1, 0, 0, 1, 1), \hspace{0.3cm}(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  $\mathcal{C}$?

	For all code words  $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$   ⇒   $\underline{x}_{i} \in {\rm GF}(2^6)$.
	$\mathcal{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 code word length is  $n = 6$   ⇒  the  $(5, \, 2)$  code is not eligible.

• For a  $(6, \, 2)$  code,  there are  $2^2 = 4$  distinct code words,  and for the  $(6, \, 3)$  code,  there are correspondingly  $2^3 = 8$.

• By specifying only two code words,  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 code word:

$$(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 are here the  statements 1 to 3:

• Basis vectors of the generator matrix  $\mathbf{G}$  are, for example,  the two given code words,  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.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm} (1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 0, 1, 1) \}$$

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

$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 1, 0, 1), \hspace{0.3cm} (1, 0, 1, 1, 0), \hspace{0.3cm}(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  $(2)$.

• Here not only  $\underline{u} = (0, 0, 0)$  leads to the code word  $(0, 0, 0, 0, 0)$,  but also  $\underline{u} = (1, 1, 1)$.