Use a parity check matrix for Ham(4,2) and syndrome decoding

Question

I have a coding theory question which I am confused about:

Use a Parity check matrix for Ham(4,2), with the columns in lexicographical order, and syndrome decoding to decode

a.) 00000 00000 11111

b.) 00000 11111 11111

c.) 11111 11111 11111

So I am trying to attempt a.)

I know that $ham(4,2)$ is a $[15,11]$ code and have found a question on-line which is similar and has

$H= \left( \begin{array}{ccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} \right) $

So to begin with, how did they get H as the above for $ham(4,2)$ as in what determines the matrix? I know why it is a [15,11] matrix but not how to determine the binary numbers inside it. Should I be reducing this to a parity check matrix?

Now I am unsure what to do - I am guessing you have to find $y_1H^T$ from what I have been reading but I am confused as how to do this. What is $y_1$? would it be

$y_1= 00000 00000 11111$ or would I put this into a matrix form? I am confused as to how to calculate $y_1H^T$. Should this give me a binary number which determines which letter in $x_j$ should be changed? Is this a coset leader? (Bit confused about what a coset leader means)

Any help much appreciated. Please write in plain English as I do not know much about Coding Theory and Binary numbers yet.

Thanks

Answer 1

The columns of $H$, read top to bottom, form the binary representations of the numbers $1, 2, \dots, 15$. This matrix is the parity check matrix for a Hamming $[15,11]$ code (length $15$, dimension $11$).

You are correct that to decode a received word, $y$, you compute $yH^T$ with operations done $\mod{2}$. This will give you a binary vector of length $4$. You may then immediately interpret it as an integer, or you may find the matching column of $H$ (it comes to the same thing), and then switch the indicated bit on the received word to get the nearest code word.

In your example with $y_1$, you get $y_1 H^T=1011$. This works out to the number $11$ (eleven) or it matches the $11$th column of $H$. So you switch the eleventh bit to find the nearest codeword $000000000001111$.

If $yH^T=0000$, then $y$ itself is a codeword, and (presumably) no errors occurred.