# A set of words from a code has been received with up to 1 error, use a parity-check matrix to correct them.

The problem:

We have a linear, binary code which is given by the parity-check matrix $$H=\left[ \matrix { 1&0&1&1&0 \\ 1&0&0&1&1 \\ 1&1&0&0&1 } \right]$$.

a) The words $(01010),(10101),(11011)$ have been received. Which code words were sent, if at most one error has occurred in every word?

b) Find a word which cannot be received if there is at most one error in the sent codeword.

My thoughts/what I've done

Not much, I've tried researching parity-check matrices online and I get that a word is in the code iff $Hc^T = 0$ and that's about it (most questions online are regarding generating parity-check matrices).

Further work after research

Okay so the comments and answers helped me by quite a bit. This is what I did to solve a) for the first received code $(01010)$:

Do $H(01010)^T = (111)$. Then find the column $h$ such that $h=(111)$, take its position (in this case 0) and flip that bit in the code received. Therefore the correction of $(01010)$ is $(11010)$ which is what the answers have given me thus far. Do this for every code received, if (000) is the result then that vector is correct.

For b) we check (thanks Zxu!) through the columns. We have $(111),(001),(100),(110),(011)$ but we don't have $(101)$. Consider how we error check, surely if we get $Hc^T=(101)$ then something's gone wrong, we can't correct that with our algorithm!

Thus we solve the equation $Hc^T=(101)$

$H(x1,x2,x3,x4,x5)^T=[x1+x3+x4,x1+x4+x5,x1+x2+x5]$

Which gives us the following equation system:

$x1+x3+x4 = 1$

$x1+x4+x5=0$

$x1+x2+x5=1$

This can be solved at a glance, the resulting vector is $(01100)$.

• Have you computed $Hc^\top$ for your matrix and words? What were the results? Commented Jan 5, 2017 at 14:34
• No, I haven't. My lectures were pretty bare-bones regarding this. If you have any good links then I'd be glad to read them.
– ejbs
Commented Jan 5, 2017 at 14:36
• Do you know how to do matrix-vector multiplication? That's all I'm asking about. Commented Jan 5, 2017 at 14:37
• Alright, yeah, I can do that.
– ejbs
Commented Jan 5, 2017 at 14:39
• Great! For part (b), with hindsight you could have noted that $H (01100)^{\top}$ yields the sum of the second and third column of $H$. Commented Jan 5, 2017 at 15:34

As indicated in his comment by Mees de Vries, you should compute the syndrome $H v^{\top}$ for each received vector. Let us consider $v = (01010)$, then $$H v^{\top} = (1,1, 1 )^{\top}.$$ This is the first column of $H$, so the error occurred in the first position, and the condeword that was sent was $c = (11010)$. You may check that indeed $H c^{\top} = 0$.

Do the same for the other vectors.

As to your second question, think of a vector $v$ such that $H v^{\top} \ne 0$ is not a column of $H$.

Hint

For instance you may aim at $H v^{\top} = (1,0,1)^{\top}$. Note that this is the sum of the second and third column of $H$.

The null space of H is [-x-y, y,x,y,x] (vertical) for some bits x,y (if you don't know how to do this look it up). This is the set of all solutions to your equation Hc=0.

Plugging in all combinations of x,y, we get [0,0,0,0,0],[1,1,0,1,0],[1,0,1,0,1] and [0,1,1,1,1].

Checking these against your values, we get 11010,10101, and 11010 again. Similarly, (b) is 00110 or 01001, because these are 2 bits different from each of the possible solutions for c.

• Thanks, your hint made me get it. Could you check what I wrote as solutions?
– ejbs
Commented Jan 5, 2017 at 15:24
• @ejbs Are you sure you don't mean Caranti?
– zzz
Commented Jan 5, 2017 at 15:28
• I did! Embarrassing, sorry.
– ejbs
Commented Jan 5, 2017 at 15:29