# Decoding a binary linear code given its generator matrix

Let $C$ be the binary linear code with the following generator matrix

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

I need to decode the received word $r$, $\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I am really strugggling with this. I know a message $m$ is encoded as $mG$.

So $mG$=$\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$.

I have tried doing this by eye but couldn't find a single $m$ that I could multiply $G$ by to give me $r.$ Is there another method? Also I know that there must be $2^4=16$ codewords and when I wrote them out this one wasn't in them? Not sure if that helps or maybe I did that wrong?

If you don't want to check all possibilities, you can use row operations to convert four columns of the matrix (of your own choosing) to the identity matrix, which will enable for very quick decoding. The code generated is exactly the same.

In more details, each row operation corresponds to multiplying the generator matrix from the left by some invertible matrix. In all, the effect of row operations is to multiply the original generator matrix by some invertible matrix from the left, say $H = AG$ is the new generator matrix. Since $A$ is invertible, both generator matrices generate the same code. If $r = xH$ then $r = (xA)G$, so if you decode $r$ for $H$, you can also decode it for $G$ very easily.

In your case, the row operations result in the following matrix: $$\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$

To decode $\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$, we simply add the first two rows to get the vector $\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}$. This shows that the original vector doesn't belong to the code.

• I have followed what you said by using row operations to convert four columns of the matrix (of your own choosing) to the identity matrix and got: $$G= \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}$$ But I'm not quite sure where to go from here? – harry55 Feb 27 '17 at 13:51
• Well, this makes it very easy to find out exactly which vector in the code starts with $1100$: this vector must be the sum of the first two rows. – Yuval Filmus Feb 27 '17 at 13:56
• I don't quite follow. Summing the first two rows gives me $\begin{pmatrix} 1 & 1 & 0 &0 & 0 &1 &1\end{pmatrix}$ which is in fact $r$ but still can't see what $m$ would give me that – harry55 Feb 27 '17 at 14:06
• How is the first row $1011100$? This would not give columns of the identity matrix – harry55 Feb 27 '17 at 14:16
• This is exact decoding. If you manipulated the matrix correctly, then $r$ must have been a codeword after all. If it's not a codeword, then you must have made some mistake when manipulating the matrix. Row operations just don't change the code generated by the matrix. – Yuval Filmus Feb 27 '17 at 14:47