We usually think that if a message arrives with an error, at most we can detect that something went wrong. But some codes do something more elegant: they point to exactly where the error is and correct it.
The File That Corrects Itself
Riddle statement
You want to send a 4-bit message, for example:
During transmission, a single bit may accidentally change.
You may add some extra bits before sending the message.
How many extra bits are enough so that the receiver can detect and correct any one-bit error?
Show solution
Solution
Three extra bits are enough. The result is the Hamming $(7,4)$ code.
Number the seven positions of the block:
Reserve positions 1, 2, and 4 for the check bits. Place the four message bits in positions 3, 5, 6, and 7.
Each check bit monitors the positions whose binary number contains a 1 in a particular coordinate:
- check bit 1 checks $1,3,5,7$;
- check bit 2 checks $2,3,6,7$;
- check bit 4 checks $4,5,6,7$.
The check bits are chosen so that each group has even parity.
Suppose that during transmission the bit in position 6 changes. On receiving the block:
- check 1 passes;
- check 2 fails;
- check 4 fails.
The failed checks add up to:
That result identifies exactly the damaged position. We simply flip bit 6 to correct the message.
If no check fails, there was no error. Since the seven positions have distinct binary signatures, any one-bit error produces a distinct syndrome.
It is also minimal: with $r$ check bits, we must distinguish eight states: no error and seven possible erroneous positions. Therefore we need:
and the smallest value is $r=3$.
Answer: three extra bits are enough.