2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Henno Brandsma Jan 23 '16 at 9:48
  • $\begingroup$ @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? $\endgroup$ – Nique Jan 23 '16 at 9:54
  • 1
    $\begingroup$ Yes, now you know the generator matrix for standard form. Then undo the swap at the end. $\endgroup$ – Henno Brandsma Jan 23 '16 at 9:55
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.