Exercise 1.10: Some Generator Matrices

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

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

	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.

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

	$(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).$

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