Is it possible to get parity check matrix when i can't get identity matrix?

Question

I have a generating matrix $G$ for a binary code: $$ \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ \end{bmatrix} $$ I'am trying to get parity check matrix $H$ by obtaining square identity matrix on the right side on generator matrix, and then transposing remaining part, but I guess that's impossible in this case. What does it mean while matrix $H$ can't be found?

Answer 1

What does it mean while matrix H can't be found?

What does "$H$ can't be found" mean? The algorithm tells you exactly how to compute it. There is no chance for it not to be found. You mentioned obtaining the identity matrix on the right (which I did below for $G_2$ and $H_2$) but I am used to doing it on the left ($G_1$ and $H_1$). I went ahead and did both.

Your original generator matrix

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

is row equivalent to

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

and

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

Using the transposition trick, $G_1$ has parity check matrix

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

and $G_2$ has the parity check matrix

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

I couldn't see what your difficulty was since you did not explain where you are stuck. You probably see something here you don't understand, then, and you can ask a further question in the comments.

---

In your revised example

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

we can now see how you can't get the identity matrix on the left (I suppose you mean that.)

This can be solved by going back and forth between equivalent codes. Roughly speaking, two codes are considered equivalent if you can get from one to the other by taking the list of codewords arranged as rows in a matrix, and then permuting the columns and scaling the columns. In this case, we can get to an equivalent code by swapping the third and fourth columns of the generator matrix.

After finding a parity check matrix for this code, we can jump back to the original code by swapping the third and fourth columns again (for the parity check matrix too.

So after the swap we have

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

which is equivalent to

$$ \tilde G_3= \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix} $$

which has parity check

$$ \tilde H_3 \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{bmatrix} $$

and after swapping the columns back:

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

which has parity check

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