Skip to content

Appreciating the Hamming [7,4,3]-code

January 9, 2012

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.

The Base Card

Is your number on this side?

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

\begin{bmatrix}1&0&0&0&1&1\\ 0&1&0&1&0&1\\ 0&0&1&1&1&0\end{bmatrix}.

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.

The Six Cards

About these ads
2 Comments leave one →
  1. Duncan permalink
    January 30, 2012 8:07 pm

    John Bamberg writes: “attributed to Hamming (as he could publish his findings and Golay could not)”.

    Both Hamming and Golay published their findings: [1] and [2]. Hamming cites Golay’s 1949 correspondence writing: “The only previous work in the field of error correction that has appeared in print, so far as the author is aware, is that of M. J. E. Golay.”

    Hamming’s work was briefly described by Shannon [3] and Shannon’s paper was cited by Golay. It was the mention of Hamming’s work in Shannon’s paper that prompted Golay’s work on the code.

    Publication of Hamming’s work was apparently delayed due to a patent application [4].

    [1] R.W. Hamming, “Error Detecting and Correcting Codes”, The Bell System Technical Journal, Vol. 29, No. 2, April 1950, pp. 147–160.
    [2] M. J. E. Golay, Correspondence, “Notes on Digital Coding”, Proceedings of the IRE, Vol. 37, No. 6, p. 657, June 1949. doi: 10.1109/JRPROC.1949.233620.
    [3] C. E. Shannon, “A mathematical theory of communication”, Bell Sys. Tech. Jour., vol. 27, p. 418; July, 1948.
    [4] Richard W. Hamming and Bernard D. Holbrook, “Error-Detecting and Correcting System”, US Patent No. 2,552,629, May 15, 1951, Filed Jan. 11, 1950.

Trackbacks

  1. Catching a liar « Peter Cameron's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: