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.

Correct any error and decode $(1,0,0,1,0,0,1)$ encoded using Hamming $(7,4)$ assuming at most one error. The message $(a,b,c,d)$ is encoded $(x,y,a,z,b,c,d)$

The solution states $H_m = (0,1,0)^T$ which corresponds to the second column in the Standard Hamming (7,4) matrix which means the second digit, 0, is wrong and the corrected code is $(1,1,0,1,0,0,1)$. The resulting code becomes $(0,0,0,1)$

My question is: How do I get $H_m$?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

The short answer is that you get the syndrome $H_m$ by multiplying the received vector $r$ with the parity check matrix: $H_m=H r^T$.

There are several equivalent parity check matrices for this Hamming code, and you haven't shown us which is the one your source uses. The bits that you did give hint at the possibility that the check matrix could be $$ H=\pmatrix{1&0&1&0&1&0&1\cr0&1&1&0&0&1&1\cr0&0&0&1&1&1&1\cr}. $$ To be fair, that is one of the more popular choices, and also fits your received word / syndrome pair :-). The reason I'm bitching about this is that any one of the $7!=5040$ permutations of the columns would work equally well for encoding/decoding. Being an algebraist at heart, I often prefer an ordering that exhibits the cyclic nature of the code better. Somebody else might insist on an ordering the matches with systematic encoding. Doesn't matter much!

Here your received vector $r=(1,0,0,1,0,0,1)$ has bits on at positions 1, 4 and 7, so the syndrome you get is $$ H_m=H r^T=\pmatrix{1\cr 0\cr0\cr}+\pmatrix{0\cr 0\cr1\cr}+\pmatrix{1\cr 1\cr1\cr}=\pmatrix{0\cr 1\cr0\cr} $$ the modulo two sum of the first, fourth and seventh columns of $H$.

If $r$ were a valid encoded message, then the syndrome $H_m$ would be the zero vector. As that was not the case here, an error (one or more) has occurred. The task of the decoder is to find the most likely error, and the usual assumptions lead us to the goal of toggling as few bits of $r$ as possible.

The nice thing about the Hamming code is that we can always do this by toggling at most one bit. We identify $H_m$ as the second column of $H$, so to make the syndrome zero by correcting a single bit we need to toggle the second bit of $r$.

What makes the Hamming code tick is that all possible non-zero syndrome vectors occur as columns of $H$. Therefore we always meet our goal of making the syndrom zero by toggling (at most) a single bit of any received word.

share|improve this answer
    
My mistake, I thought the standard 7,4 hamming matrix was actually standard, but I guess not. The matrix I am using is identical to the one you wrote, except the first row and the third row are flipped - so reading numbers 1 to 7 in binary in my matrix reads downwards whereas yours reads upwards. But that doesnt make a difference in this case. And thanks, I see now how to get s. –  Arvin Nov 9 '11 at 10:11
    
Ok. That's fine. Happens easily unless you have seen several books. I switched the notation from $s$ to $H_m$ for the syndrome. Hopefully Dilip Sarwate shows up. He has seen more introductory coding theory books. For me coding theory has always been applied algebra. –  Jyrki Lahtonen Nov 9 '11 at 10:14
4  
@Jyrki An excellent explanation as usual and there is little I can add except to say that for engineers, the choice of $H$ is driven by implementation issues rather than by mathematical elegance. The "standard" $H$ has the property that the syndrome is effectively the address or index of the bit that has to be changed in the array storing the received bits. It can also be used to correct errors "on the fly" as the received word is read out of the decoder bit by bit. The syndrome, regarded as an integer, can be decremented to reach $0$ exactly as the bit to be corrected is leaving the decoder. –  Dilip Sarwate Nov 9 '11 at 15:26
4  
@Jyrki ...and to continue, for BCH codes etc that can correct more than one error, cyclic parity check matrices are the preferred choice especially when one wants to use things like the Chien search to correct errors "on the fly". It is just for the binary Hamming code that the "standard" $H$ matrix allows for error correction as the symbols are leaving the decoder. –  Dilip Sarwate Nov 9 '11 at 15:30
    
@DilipSarwate: Thanks for the extras. For me a Hamming code has more or less always been a special case of a BCH code, but your reasoning makes, of course, perfect sense. –  Jyrki Lahtonen Nov 9 '11 at 19:36

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.