[Math] How to find parity check matrix if generator matrix can’t be written in standard form

coding-theory

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

Best Answer

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