The Magic of Error Correcting Codes
by Todd Mateer (tmateer@howardcc.edu)
Download Talk Slides
Trick 1: Binary Number Cards

Many people have probably seen some form of this trick before. I was introduced to this trick myself through a magic set that my brother got for Christmas one year.

The basic idea is that a volunteer is asked to choose a number from 1-63. He or she is then shown a set of cards and asked to tell whether or not the number appears on each card. After the volunteer has responded to all 6 cards, the magician tells the audience the number chosen by the volunteer.

A good description of this trick can be found at: Binary number magic trick

There are cutouts here that one can use to perform the trick.

In my talk, I do a simplified version of this trick using only 4 cards and the numbers 1-15 so that my focus is explaining to the audience how the trick works.

Trick 2: Ternary Number Cards

Error correcting codes involve other number system besides binary. I was first introduced to this next trick at the 2014 Joint Math Meetings to illustrate a different number system. This trick is credited to Nancy Blachman (www.mathdelights.org and www.JuliaRobinsonMathFestival.org).

This time a volunteer selects a number from 1-80. He or she is shown a set of cards and asked to tell whether the number appears on a blue cat, a green dog, or a red mouse. After the volunteer has responded to the 4 cards, the magician tells the audience the chosen number.

This trick works just like the binary cards, just with three possible states for each card (blue/green/red) or (cat/dog/mouse).

Below is a description of how the trick works and cutouts one can print out to do the trick.

Marin Math Circle - ternary cards

Here is an alternative presentation of the trick

Mathematical Magic by Gerald Michon (search for Ternary cards)

Trick 3: Hamming Code Trick

So far, we have considered two codes used to encode numbers, but neither of them correct any errors. The next trick illustrates one of the earliest and simplest error correcting code.Wikipedia describes the origins of this code as follows:

[Richard] Hamming worked at Bell Labs in the 1940s on the Bell Model V computer, an electromechanical relay-based machine with cycle times in seconds. Input was fed in on punched cards, which would invariably have read errors. During weekdays, special code would find errors and flash lights so the operators could correct the problem. During after-hours periods and on weekends, when there were no operators, the machine simply moved on to the next job.

Hamming worked on weekends, and grew increasingly frustrated with having to restart his programs from scratch due to the unreliability of the card reader. Over the next few years, he worked on the problem of error-correction, developing an increasingly powerful array of algorithms. In 1950, he published what is now known as Hamming Code, which remains in use today in applications such as ECC memory.

I originally found this trick in a Math Horizons article by Richard Ehrenborg. I signed up to do this trick at talent show at my church and found that some adjustments needed to be made with the Enrenborg cards to do the trick in public. My children and I spent weeks coloring large pieces of posterboard to design new cards. This performance wasn't effective either, partially due to an easel that kept falling over. I redesigned the trick some more, but abandoned the posterboard cards when I learned that it would cost $60 to get them laminated. Now I use a computer simulation when I perform the trick in public.

This trick uses 7 cards. The first four cards are equivalent to the four cards used in the binary card trick (Trick 1 above). The last three cards allow a single error to be detected and corrected using specially designed holes in the cards.

The improved trick was first presented at the 2012 MAA Mathfest convention in Madison, WI and subsequently written up and published by Math Horizons at the suggestion of one of the conference participants. While at the 2012 Mathfest, I also had the privilege of taking a math magic course by Colm Mulcahy which I highly recommend if anyone gets the chance. Dr. Mulcahy publishes a bimonthly column "Card Colm" and has recently published a book containing his tricks using a standard deck of cards.

Bruce Torrence of Math Horizons kindly allowed an electronic copy of a draft of my paper to be shared with others.

"A Magic Trick based on the Hamming Code" by Todd Mateer, Math Horizons, November 2013.

He also created cutouts that one can use to perform the trick as well as a Mathematica computer simulation of the trick.

Math Horizons Supplements to "A Magic Trick based on the Hamming code" by Bruce Torrence

In order to run the computer simulation, you need to download a free CDF file player from Wolfram.

By the way, both Bruce Torrence and Colm Mulcahy are organizers of the Math, Magic, and Mystery website for the 2014 Math Awarness Month campaign.

Trick 4: Double Error-Correcting Code Trick

I then extend the idea of the Hamming Code trick to a code which can correct up to 2 errors. Instead of a single hole on each tab of the card, I use a cross pattern instead. This allows a second color to be visible when the cards are stacked. Most error correcting codes used in practice can correct more than 1 error. This trick allows people to see how things get a little more complicated when the goal is to correct multiple errors.

I have written up this trick, but not yet been successful in getting it published. The feedback that I have been getting from math journals is that it is too similar to the Hamming Code magic trick to warrant an additional publication when I've already had several related papers published recently (they would like to give others an opportunity to share their work). So below, I've included the yet unpublished writeup describing this trick.

Double error correcting code magic trick

Trick 5: Reed-Solomon Code Trick

Next, I do a trick that I invented to illustrate the Reed-Solomon code. This is the most popular form of error correcting code found in the world today, primarily because it is used to correct errors found on CDs. It is also used in the Quick Response codes frequently scanned by smartphones.

Handouts

This magic trick was published in the April 2014 issue of Mathematics Magazine. Walter Stromquist who worked hard as the editor of my article to polish the writeup kindly allowed me to put a copy of a draft of the article on this website.

A Reed-Solomon Code Magic Trick by Todd Mateer, Mathematics Magazine, April 2014.

You can download and print the cards for this trick. Each file has all the cards on the first page and then each card individually on the other pages.

The mathematics of this trick is significantly more complicated than the previous two tricks. It works with a more advanced number system of mathematics called a Finite Field.

Longer versions of the code (e.g. the Reed-Solomon code used on CDs) can correct significantly more errors than the simpler ones considered in these magic tricks.

As an aside, the main focus of my PhD dissertation (available at amazon.com or the free version) was a new Fast Fourier Transform, specially designed to implement one of the steps used for Reed-Solomon decoding. A mathematical discussion of the Reed-Solomon code appears in one of the later chapters of the dissertation. This technique has been improved in the years following the dissertation through the following two articles:

Simple algorithms for decoding Reed-Solomon codes by Todd Mateer; Designs, Codes, and Cryptography; October 2013

Efficient Algorithms for Decoding Reed-Solomon Codes with Erasures by Todd Mateer; unpublished article

Trick 6: Parity Bit Card Trick

I conclude the talk with a magic trick involving a simple product code. Some web pages that describe this trick can be found at:

Parity Bit Card Trick (Computer Science Unplugged)

Parity Bit Card Trick (by LETHALDONUT)

If one replaces the partity check with the Reed-Solomon code (Trick 5) in the product code, then you get the error correction system on DVDs. This type of error-correction method allows errors to be corrected using the codes in both the rows and columns. The two codes work together to correct a greater number of errors than the two codes could correct working separately. For those interested in the technical detiails of how this works, see this paper.


Page content: Todd Mateer (tmateer@howardcc.edu)
Page design: Nate Black (website)