How many errors can a code fix?
Tonight's idea
Noise can flip a bit on its way to you. So agree on a short list of allowed strings, the codewords, and send only those. The receiver picks the codeword closest to what arrived.
The Hamming distance between two strings is the number of places where they differ: 10110 and 11100 are at distance 2.
Around each codeword draw its ball: the codeword and every string at distance 1 from it, \(1 + n\) strings for length \(n\). One flipped bit leaves a codeword inside its own ball. So a single error can always be fixed when no two balls overlap, which means every two codewords are at distance 3 or more.
Now count. There are \(2^n\) strings, and \(M\) separate balls use \(M(1 + n)\) of them.
\(M \le \dfrac{2^n}{1 + n}\): the sphere-packing bound for fixing one error.
For \(n = 3\) the bound is \(8/4 = 2\), and 000, 111 reach it. For \(n = 7\) it is \(128/8 = 16\), and the seven cards of The mind reader who survives a lie are a code with exactly 16 codewords. Such codes, with no string left over, are called perfect.
Watch one: length 5
The bound is \(32/6 = 5.33\ldots\), so at most 5 codewords. Try four:
\[00000, \quad 11100, \quad 00111, \quad 11011.\]
The six distances are 3, 3, 4, 4, 3, 3, so any single error can be fixed. If 10100 arrives, its distances to the four are 2, 1, 3, 4, and it is decoded as 11100.
Can a fifth be added? A computer search says no. Four balls hold 24 of the 32 strings and the other 8 go to waste. The bound is a ceiling, not a promise.
Play the length-7 code, and try to fool it with two lies: mathdetours.com/demos/hamming.html.
Your turn
- Find the Hamming distance between 0110101 and 1010110. How many strings of length 7 are in the ball around 0110101?
- Work out the bound for \(n = 4\), \(n = 6\) and \(n = 15\), rounding down when it is not whole. For which lengths \(n\) is \(2^n/(1 + n)\) a whole number?
- A code contains 0000 and 0011, which are at distance 2. Find a string that could arrive after one error and that the receiver cannot decode. Then explain why this can never happen when the two codewords are at distance 3.
- The length-7 code has 16 codewords, every two at distance 3 or more. (a) Explain why each of the 128 strings lies in exactly one ball. (b) Two bits are flipped on the way. Explain why the receiver decodes to the wrong codeword and gets no warning.
Stretch: bigger balls
To fix two errors the balls have radius 2 and hold \(1 + n + \tfrac{n(n-1)}{2}\) strings. Show that 00000, 11111 meets the new bound for \(n = 5\). For three errors and \(n = 23\), a ball also holds the \(1771\) strings at distance 3. Count the ball and find the bound.
Answers
- They differ in places 1, 2, 6 and 7, so the distance is 4. The ball holds the string itself and the 7 strings one flip away: 8.
- \(16/5 = 3.2\), so at most 3. \(64/7 = 9.14\ldots\), so at most 9. \(32768/16 = 2048\) exactly. The bound is whole when \(1 + n\) divides \(2^n\), so \(1 + n\) must be a power of 2: \(n = 1, 3, 7, 15, 31, \ldots\) These are the lengths of the perfect Hamming codes (\(n = 1\) is the trivial code with one codeword).
- 0001 (or 0010). It is one flip from 0000 and one flip from 0011, so the receiver cannot tell which was sent. If a string were within one flip of two codewords, you could get from one codeword to the other in two flips, so their distance would be at most 2. At distance 3 that is impossible.
- (a) No two balls overlap, because the codewords are at distance 3 or more. Each ball holds 8 strings, and \(16 \times 8 = 128\), which is every string there is. So each string is in one ball and only one. (b) After two flips the string is at distance 2 from the true codeword, so it is outside that ball. By (a) it is inside some other ball, at distance 0 or 1 from a wrong codeword. (Distance 0 is impossible, since codewords are 3 apart.) The receiver sees what looks like a single error, fixes it, and is wrong. A perfect code has no spare strings to act as a warning.
Stretch. For \(n = 5\) a ball holds \(1 + 5 + 10 = 16\) strings, so \(M \le 32/16 = 2\). The codewords 00000 and 11111 are at distance 5, so two errors still leave a string closer to the right one: the bound is met. For \(n = 23\): \(1 + 23 + 253 + 1771 = 2048 = 2^{11}\), so \(M \le 2^{23}/2^{11} = 2^{12} = 4096\). A code that reaches this exists. It is called the Golay code.