Perfect codes
A couple days ago I wrote about Hamming codes and said that they are so-called perfect codes, i.e. codes for which Hamming's upper bound on the number of code words with given separation is exact.
Not only are Hamming codes perfect codes, they're practically the only non-trivial perfect codes. Specifically, Tietavainen and van Lint proved in 1973 that there are three kinds of perfect binary codes:
- Hamming codes
- One Golay code
- Trivial codes
I wrote about Golay codes a few months ago. There are two binary Golay codes, one with 23 bit words and one with 24 bit words. The former is "perfect." But odd-length words are awkward to use, and in practice you'd usually tack on one more parity bit, creating an "imperfect" but useful error-correcting code. The Voyager probes used the 24-bit Golay code to send photos of Jupiter and Saturn back to earth.
Trivial codesTrivial codes simply repeat each word of input n times. For example, 01100 would be encoded as 0110001100 in a trivial code with n = 2. In order to be a perfect code, a trivial code must have n odd.
Trivial codes are the first and simplest thing you'd think of if you wanted to create an error correcting code. You might, for example, send a message three times. Then if a bit in a single word is corrupted in one copy of the message, but the corresponding word is the same in the latter two copies, you use their common value as the assumed correct value.
While trivial codes are obvious, they're not efficient. For example, suppose we have message words of 5 bits, say to encode English letters and a few other symbols. If we triple each message word, it takes 15 bits of code word to transmit 5 bits of message.
But if we used a Hamming (15, 11) code, each 15-bit code word carries 11 message bits and 4 parity bits. This code has the same Hamming separation as the trivial code with n = 3, but it carries over twice as much information per code word, 11 bits versus 5 bits.
As word size increases, the efficiency of Hamming codes approaches 1. With trivial codes, the efficiency is constantly 1/n.
Trivial codes show that "perfect" does not mean optimal in a practical sense. Perfect codes are optimal with respect to the Hamming bound, but maybe not optimal in practice, depending on what criteria you're optimizing over. Trivial codes are optimal if you're optimizing for conceptual simplicity, but not if you're optimizing for efficiency.
More coding theory posts