# Check a word given a generator matrix G

Take the binary code C with generator matrix: $$\left( \begin{array}{ccccc|cccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right)$$ And use it to correct the word that has at most one error: $$011000011$$.

Notice that this matrix is of the form $$(I_5 | P)$$, we obtain the parity matrix by transposition: $$(P^T|I_{9-5})=(P^T|I_{4})$$, this gives us the following parity matrix: $$\left( \begin{array}{ccccc|cccc} 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \right)$$ We obtain the four equations which each codeword must satisfy, where $$m_i$$ denotes the message bits and $$r_i$$ denotes the parity bit: $$m_1 + m_3 +m_4+m_5 + r_1 = 0$$ $$m_1 + m_2 +m_4+m_5 + r_2 = 0$$ $$m_1 + m_2 +m_3+m_5 + r_3 = 0$$ $$m_2 + m_3 +m_4+m_5 + r_4 = 0$$ We will use these equations to check the word: $$011000011= m_1 m_2 m_3 m_4 m_5 r_1 r_2 r_3 r_4$$, $$0 + 1 +0+0 + 0 \not \equiv 0$$ $$0 + 1 +0+0 + 0 \not \equiv 0$$ $$0 + 1 +1+0 + 1 \not \equiv 0$$ $$1 + 1 +0+0 + 1 \not \equiv 0$$

Here I ran into a problem because I do not gain any information from these equations as I cannot pinpoint the error. I've checked it several times but can't seem to find the error in my reasoning or how to proceed.

• Just set $m_5$ to be $1$. – Berci Jan 10 '19 at 14:07
• Because it appears in every equation? so it must be the error? – Algebra geek Jan 10 '19 at 14:08
• Yes, and because every equation is false originally. – Berci Jan 10 '19 at 14:10

Then, for correcting the word $$y = 011000011$$: simply calculate its Hamming distance from each code word. You should find one at distance zero or one.
To correct from the syndrome ($$H\,y$$): by considering all the error positions, you can establish a correspondence (a table) between error positions and the syndrome.