# Constructing generator matrix of a linear code

The linear code $$C \cong \mathbb{F}^5_2$$ is given by $$C = \{(x_1, x_2, x_3, x_4, x_5) | x_1 + x_2 + x_3 = 0, x_4 + x_5 = 0$$ in $$\mathbb{F}_2\}$$.

Write down a parity check matrix and a generator matrix for $$C$$.

For the parity check matrix I've let $$\underline{x} = (x_1, x_2, x_3, x_4, x_5)$$.

So for the condition $$x_1 + x_2 + x_3 = 0$$ we have $$\underline{x}.(1 1 1 0 0)= 0$$.

And for the condition $$x_4 + x_5 = 0$$ we have $$\underline{x}.(0 0 0 1 1)= 0$$

So a parity check matrix is: $$\begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ \end{bmatrix}$$

How do I then go on to construct a generator matrix? I'm struggling to understand my notes and don't know how to begin. I just know that the dimension of $$C$$ is $$5 - 2 = 3$$ so the generator matrix will have $$5$$ columns and $$3$$ rows.

• Permute the coordinates so that your $P$ has the form $[ I_2 | H]$. Then the generator matrix has the form $[I_3 | H^t]$. See en.wikipedia.org/wiki/Parity-check_matrix – Henno Brandsma Jan 23 '16 at 9:48
• @HennoBrandsma So if I swap the second and the fourth columns to get $\begin{bmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ \end{bmatrix}$ then the generator matrix is $\begin{bmatrix} 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}$. Do I then need to permute the same columns back again? – Nique Jan 23 '16 at 9:54
• Yes, now you know the generator matrix for standard form. Then undo the swap at the end. – Henno Brandsma Jan 23 '16 at 9:55

Once you have $$H$$, to find $$G$$ you need to find a set of $$k$$ rows of length $$n$$ that are LI and orthogonal to the rows of $$H$$.

In a simple case like this, it could be done by trying, eg:

$$G= \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ \end{bmatrix}$$

A more general and systematic way is to try to find an equivalent code (same codebook, different mapping) by doing elementary operations with the rows of $$H$$, to put it in systematic form: $$H=( I | P´)$$ and then $$G=( P | I)$$ fits the bill.

In this case, we cannot do that manipulating the rows alone. We can resort to an aditional trick: you are also allowed to permute some columns , to bring it to systematic form, but then at the end un-permute the rows in the resulting $$G$$.

So, let's permute columns 2 and 4 to get the modified parity matrix

$$\begin{bmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ \end{bmatrix}=[I | P']$$

and the modified generator matrix is

$$[P | I] =\begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ \end{bmatrix}$$

and after permuting columns 2 and 4 we get

$$G = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$

You can (you should) check that the rows are indeed LI and orthogonal to the rows of $$H$$.