How do I find parity check matrix if generator matrix can't be written in standard form?

Question

$G=\left ( \begin{matrix} 1 &1 &0 &1&0&0&1\\ 1&0 &1 &0&1&0&1\\ 0&1 &1&0&0&1&1 \end{matrix} \right )$

Is it possible to get parity check matrix if generator matrix is not in the standard form?

Answer 1

You can always try to reduce your generator matrix through row reduction into something of the form $\begin{bmatrix} I_k&P\end{bmatrix}.$ Then you can use the standard method of turning $\begin{bmatrix} I_k&P\end{bmatrix}$ into $\begin{bmatrix} -P^T \\I_{n-k}\end{bmatrix}$ to get the parity check matrix.

Here though, that fails. We can still work with the definition of parity check matrix, though. We want something that sends any combination of these rows to zero, so we can solve $\begin{bmatrix} G & | & \bf{0} \end{bmatrix}$ where $\bf{0}$ is a column vector of all zeroes. Here we get

$$\begin{bmatrix} 1&1&0&1&0&0&1&0\\1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\end{bmatrix} $$ which is equivalent to

$$\begin{bmatrix} 1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\end{bmatrix} .$$ Thus the solutions to this system all satisfy $$x_1=x_3+x_5+x_7,$$ $$x_2=x_3+x_6+x_7,$$ $$x_4=x_5+x_6+x_7,$$ which gives us vectors of the form $$\begin{bmatrix} x_3+x_5+x_7\\x_3+x_6+x_7\\x_3\\x_5+x_6+x_7\\x_5\\x_6\\x_7 \end{bmatrix}$$ or $$x_3\begin{bmatrix} 1\\1\\1\\0\\0\\0\\0\\\end{bmatrix}+x_5\begin{bmatrix}1\\0\\0\\1\\1\\0\\0 \end{bmatrix}+x_6\begin{bmatrix}0\\1\\0\\1\\0\\1\\0 \end{bmatrix}+x_7\begin{bmatrix} 1\\1\\0\\1\\0\\0\\1\end{bmatrix}.$$ We make a new matrix with these as rows to get $$\begin{bmatrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\0&1&0&1&0&1&0\\1&1&0&1&0&0&1 \end{bmatrix}.$$ This will be your parity check matrix, and you can check that it sends any combination of the rows of $G$ to zero by taking $GH^T.$

Answer 2

Say $C$ is your code with generator matrix $G$. If you reduce $G$ to echelon form, you obtain $$\begin{bmatrix} 1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\end{bmatrix}$$ which is unfortunately not in standard form.

BUT, we can put it in standard form by swapping the third and fourth column, so we get $$G^{\prime} = \begin{bmatrix} 1&0&0&1&1&0&1\\0&1&0&1&0&1&1\\0&0&1&0&1&1&1\end{bmatrix}$$

This $G^{\prime}$ is the generator matrix for a different (but equivalent) code $C^{\prime}$, where the 3rd and 4th positions of our codewords have been swapped. So $C^{\prime}$ has parity check matrix $$H^{\prime} = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$$ And we translate it back to a parity check for $C$ be swapping the third and fourth columns back again $$H = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$$