The Hamming (7, 4) code
The Hamming (7, 4) code: encode four bits into seven, find the broken bit by the syndrome, and recover the message that was sent.
How to solve it
The Hamming code adds three check bits to four message bits so that one error can be not only noticed but corrected. The check bits sit at positions $1, 2, 4$ — the powers of two — and each watches its own group of positions. The position of a broken bit is the sum of the numbers of the checks that fail.
Step by step
- Put the message bits at positions $3, 5, 6, 7$.
- Check bit $1$ watches positions $1, 3, 5, 7$ (circle A), bit $2$ watches $2, 3, 6, 7$ (circle B), bit $4$ watches $4, 5, 6, 7$ (circle C). Each is chosen to make the number of ones in its circle even.
- Finding an error: test all three circles. The circles with an odd number of ones give the syndrome: A is $1$, B is $2$, C is $4$. The sum is the error's position; $0$ means no error.
- Decoding: flip the bit at the syndrome's position and read positions $3, 5, 6, 7$.
Common mistakes
- Putting the message bits at the start instead of positions $3, 5, 6, 7$.
- Mixing up which positions a check watches: bit $2$ watches $2, 3, 6, 7$ — the positions with a one in the second binary digit.
- Adding the numbers of the checks that pass instead of those that fail.
- Answering with the whole word when decoding — only the four bits at positions $3, 5, 6, 7$ are needed.