# 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

• Which standard form? There are several. Any check matrix in the form $(A\quad I)$ is in standard form (where $I$ is the identity matrix). The columns of $A$ can be permuted to produce many check matrices in standard form. – Snowball Feb 12 '13 at 8:04

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$.

• thanks a lot for your help! – mathnoob Feb 14 '13 at 1:55