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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please assume that no more than two errors have occured during transmission using the [8,4] extended binary Hamming code.

Now, a received word using this code will have $2^{8-4}=16$ possible syndromes:

if no error has occurred, the coset leader corresponding to the syndrome is $00000000$;

if only one error has occurred, the coset leader corresponding to the syndrome is one of the eight possible weight-$1$ error words;

if two errors have occurred, there are $7$ possible syndromes (which will not correspond to any column of the check matrix) and $8\choose2$$=28$ possible weight-$2$ error words; I know that in this case the code will be unable to (uniquely) correct the received word (meaning that each syndrome will not correspond to a unique coset leader), but I'm interested to know how the $28$ weight-$2$ error words are distributed among the $7$ remaining syndromes. Without having to exhaustively construct the table myself, can someone please point me to a syndrome table/dictionary for the [8,4] Hamming code? In particular, I want to know if it is the case that each such syndrome corresponds to four error words, and how many coset leaders correspond to each such syndrome. Many thanks.

share|cite|improve this question
The number of cosets with leader of weight 2 is seven. Each coset has, indeed, four leaders, all of weight two. This follows from the fact that the automorphism group of this extended code is doubly transitive. Two different leaders of weight two are in the same coset, iff their sum is a codeword. Each vector of weight three can be paired up with the others in that way. I really recommend that you get your hands dirty with some of these questions. Then you will appreciate the use of symmetry groups more! – Jyrki Lahtonen May 3 '13 at 11:55
Another approach would be to puncture this code at one position (doesn't matter which). You will be left with a perfect code capable of correcting one error. So if you feed the decoder with a word $w$ of weight two, it will be corrected to a word of weight three. Add the punctured bit, and you will have produced a codeword of weight four at a distance two from $w$. Vary the punctured bit to prove that you get several words of weight four at distance two from $w$. – Jyrki Lahtonen May 3 '13 at 11:58
@JyrkiLahtonen Thanks, you have answered my queries perfectly! Would you post it as an Answer? – Ryan May 3 '13 at 12:11

Your Answer


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

Browse other questions tagged or ask your own question.