The Hamming code is a perfect code. We have 16 codewords in the Hamming (7,4) code, out of 128 seven-bit words possible. We define a ball of radius 1 about each codeword as the set of all words that differ from the codeword in at most 1 bit. (Note: a ball of radius 2 would be the set of all words that differ from the codeword in at most 2 bits and so on). There are eight words in the ball of radius 1 about each codeword: the codeword itself and the seven words that differ from the codeword in the first, second, third, fourth, fifth, sixth, and seventh bit respectively. There is no overlap between the different balls and every seven-bit word lies in one of the 16 balls, since, as we have noted before, for any seven-bit word there is a unique codeword that can be obtained by changing a single bit. A code for which every possible word lies in exactly one ball about a codeword is called a perfect code.

Perfect codes are quite rare. There is no perfect code with eight-bit words for example. We can see this just from counting. A ball of radius 1 about an eight-bit codeword must contain nine words, the codeword itself and the eight words that differ from the codeword in the first, second, third, fourth, fifth, sixth, seventh, and eighth bit respectively. But there are 2⁸ = 256 possible eight-bit words, and you can't divide 256 words into balls of 9 words without any leftover, since 9 doesn't divide 256 evenly. This only shows that there are no perfect codes with eight bits using balls of radius 1, but you can similarly show there are no perfect codes with eight bits using balls of any radius. The numbers just won't work out right.

Even if the numbers work out right, the geometry may not. Even when you put balls together as tight as you can, there is still a little space between them. Just because the numbers work out right doesn't mean you will be able to fit balls together to get a perfect code with no word lost between the balls. These questions lead to problems in high-dimensional geometry. For example, the Hamming (7,4) code can be thought of as packing balls in 7 dimensional geometry, since each word is specified by 7 coordinates - the 7 different bits. Since perfect codes are rare, they aren’t common in practice. Being perfect isn’t necessary for a good code, though it is good to be close to perfect. To find close to perfect codes sometimes takes some geometric intuition. The codes used for cross Atlantic phone calls in the 80's involved working with geometry in space of more than 100 dimensions. If your students ever ask you if there are any applications to geometry in more than 3 or 4 dimensions, you now have an answer.

A code is cyclic if whenever a₁a₂a₃a₄a₅a₆a₇ is a codeword, so is a₇a₁a₂a₃a₄a₅a₆. Note that it wouldn't change anything to replace a₇a₁a₂a₃a₄a₅a₆ by a₂a₃a₄a₅a₆a₇a₁. One step in one direction is the same as taking six steps in the other direction. The Hamming code as I have presented it is not cyclic. For example, 0001011 is a codeword, but 1000101 is not a codeword. But this is a flaw of the presentation, not the code. The Hamming code is equivalent to a cyclic code. Suppose we just permute some of the bits. Rather than recording b₁b₂b₃b₄p₁₂₃p₁₂₄p₁₃₄, we use a slightly different set of partity bits b₁b₂b₃b₄p₁₃₄p₁₂₃p₂₃₄. Then the 16 codewords become

Many codes used in practice are linear cyclic codes because they are easy to build and implement. In order to build them, we will need to develop some new algebraic structures. This is a class in algebraic structures after all. So our next week or two will be devoted to developing properties of some different algebraic structures, that we will eventually use to build good error-correcting codes.