How to get the parity check matrix if I don't have an identity matrix in my generator matrix?

Question

Assuming I have the following code: $C = {00000,01001,01110,00111}$

My task is to get the parity check matrix $H$ for this code. So I created the generator matrix for this code, which is:

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

In class, I learned that the conversion between the generator matrix and the parity check matrix works in the following way:

$G = [I_k|A]$

$H = [A^T|I_{n-k}]$

However, in this case my generator matrix does not have the identity matrix on the left, and I cannot generate the generator matrix by multiplying a value or adding the two rows together, as none of these actions would change the first digit I would need to change in order to get an identity matrix.

How do I proceed here in order to get the parity check matrix for the given code?

Answer 1

Here is one algorithm that will work. To begin, swap columns of $G$ successively to produce a generator $\hat G$ that has the standard form. In this case, $$ \hat G = \pmatrix{1&0&0&1&0\\0&1&1&1&0}. $$ To get here, I swapped $(1,5)$ and $(2,4)$.

Produce the corresponding parity matrix $$ \hat H = \pmatrix{0&1&1&0&0\\1&1&0&1&0\\0&0&0&0&1}. $$ Take the swaps from before and apply them to the columns of $H$ in the reverse order. Switching $(2,4)$ then $(1,5)$ yields $$ H = \pmatrix{0&0&1&1&0\\0&1&0&1&1\\1&0&0&0&0}, $$ which is the desired parity matrix.