Binary Hamming Codes Can anybody help me with this?
Write down the parity check matrix of the binary Hamming code of length 15 in standard form
Assuming at most one error can occur in transmission, decode the following received words:
(1) 010100101001000 
(2) 111000111000111 
(3) 110011100111000 
(4) 011111111111111 
(5) 000000000000001
 A: Hints:
(1) The check matrix $H$ of a Hamming code has a property that any two columns of $H$ are linearly independent. For a binary Hamming code with block length $2^r-1$ (where $r \ge 2$), a nice way to generate such a matrix is to write the binary representations of $1,2,3,\ldots,2^r-1$ as the columns.
For example, consider the binary Hamming code with block length $7$ (i.e., $2^3-1$). The binary representations of $1,2,3,4,5,6,7$ are $001,010,011,100,101,110,111$, so a check matrix for one binary Hamming code with block length 7 is:
$$
H = \left(\begin{array}{ccccccc}
0&0&0&1&1&1&1\\
0&1&1&0&0&1&1\\
1&0&1&0&1&0&1\\
\end{array}\right).
$$
To put this in standard form, swap columns around until $H$ is in the form $(A\quad I)$, where $I$ is an identity matrix. In this case, one such permutation of columns is the check matrix
$$
H' = \left(\begin{array}{ccccccc}
0&1&1&1 &1&0&0\\
1&0&1&1 &0&1&0\\
1&1&0&1 &0&0&1\\
\end{array}\right)
$$
Warning: There are multiple check matrices that satisfy standard form. You'll have to ask your instructor which one you should be looking for.
For your case, let $r=4$ so that you have block length $2^4-1=15$ (so your check matrix will have dimensions $4 \times 15$).
(2) There are several ways to decode a binary Hamming code, but the easiest to explain is syndrome decoding. Let's continue with the block length $7$ Hamming code I defined above with $H'$. Suppose $r = 1001010$ is the received word, a $1 \times 7$ matrix. Define the syndrome as
$$
s = H'r^\top = \left(\begin{array}{ccccccc}
0&1&1&1 &1&0&0\\
1&0&1&1 &0&1&0\\
1&1&0&1 &0&0&1\\
\end{array}\right)\left(1001010\right)^\top
 = \left(\begin{array}{c}
1\\1\\0
\end{array}\right).
$$
Note that sums and differences are performed mod 2, i.e., with the $\operatorname{xor}$ operation.
The received word $r$ is the sum of an error word $e$ and the transmitted codeword $c$, i.e., $r = e + c$. Since the Hamming code is a linear code, we have
$$H'r^\top = H'(e+c)^\top = H'e^\top + H'c^\top = H'e^\top + 0.$$
So, we need to find a word $e$ of Hamming weight $1$ such that $H'e^\top = \left(\begin{array}{c}
1\\1\\0
\end{array}\right)$. You can either try all 8 possibilities ($0000000$, $1000000$, $0100000$, ...) or try writing out the product and see if you can figure it out algebraically. See if you can find the pattern! The value of $e$ in this case will be $0010000$, so the decoded word $c = r-e = 1001010-0010000=1011010$.
