Appreciating the Hamming [7,4,3]-code
You might be familiar with Richard Ehrenborg’s beautiful game where your friend chooses a number from 0 to 15, and you proceed to show in turn seven cards, asking which side of the card the number is on, and then placing each card down carefully on a base card. Each card has a funny shape, with squares poking out at the edges.
Your friend can lie at most once, and so once the cards have been placed down, the number on the base card which is covered at most once by a protruding square, is the number your friend has chosen. What is so cool about this trick is that you have an excellent information rate — seven questions, sixteen numbers to choose from and one lie. What makes this tick is a perfect code, which was known earlier by Golay but is attributed to Hamming (as he could publish his findings and Golay could not). (See Chapter 1, Section 6 of Thomas Thompson’s book). This code has code length 7, dimension 4 and minimum distance 3. So it can correct single errors and detect two errors. However, in demonstrating the glory of the Hamming code to the uninitiated, I felt something was missing; a crappier precursor.
I’ve come up with a simpler game based on a [6,3,3]-code which has a (poor) information rate of 0.5, and is certainly not perfect (the Hamming bound here is 64/7). The generator matrix for this linear code is
Your friend chooses a number from 0 to 7, and you proceed to present six cards in turn, asking which side of the card the number is on, and then placing each card down carefully on a base card. It still works like the Hamming code, but makes the Hamming code look so much better in comparison. The cards are attached.