Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

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

share|improve this answer
    
thanks a lot for your help! –  mathnoob Feb 14 '13 at 1:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.