Simplest error detecting/correcting codes for math newbies

Question

Suppose you have been given the task of teaching some basic coding theory to folks who are interested in math but have not taken algebra, number theory, etc. If you want to introduce codes, you might start out with codes that are just based on overall parity - for example, you might start out assuming serial communication, and introduce a code in which $11$ and $00$ were codewords while $01$ and $10$ were not. You can obviously extend this example to any number of bits, but the idea remains the same - and this is a pretty terrible code.

In the spirit of introducing as little abstraction, group theory, etc as possible, what is or are the next logical code(s) to introduce?

Answer 1

I second what @RobertIsrael writes.

I have a talk for high-school students based on the Seven Questions, One Lie game, which involves the $(7,4)$ Hamming code and the Fano plane, and it's always quite successful. It's a good way to teach about the codes without appealing too much to algebra. See this post of Peter Cameron for an account.

I have also some slides for it, but they are in Italian. These other slides deal with the Fano plane. They are also in Italian, but it's mostly geometry, there's little talking. They show how you can decode just by doing geometry, like, the line through two distinct points.

Answer 2

Why not show them a perfect binary $(7,16,3)$-code based on the Fano plane? Not much theory required, just a picture like http://en.wikipedia.org/wiki/File:Fano_plane.svg

Answer 3

I think the binary Hamming $(7,4,3)$ code is far and away the next best step because it has this simple visualization using three circles that you can find at the Wiki article. It doesn't require any background besides being able to do binary arithmetic. (Incidentally, my advisor was fond of calling this the "Mickey Mouse code" both because the circles can be arranged to resemble the character and because it can be taught to elementary schoolers.)

This really helps to graphically drive home how the parity bits interweave the information from the information bits. It also helps students get a better feel for how erronious bits can be corrected and detected by the redundancy. The next best thing about the binary Hamming codes in general is that they have easy-to-understand and easy-to-use parity check matrices.

If you want to take a break from binary codes and explore codes under different moduli, you might consider going with some of the simple codes with parity check matrices $[1,1,\dots,1]$ or $[1,1,\dots, 1,-1]$. They are only very simple codes with a single parity check, but they are used in a lot of places (none of which I can remember instantly.)

It also makes it easy to segueway into codes with slightly more complicated but still 1-dimensional parity checks like $[1,3,1,3,\dots]$. I'm not a big fan of For all practical purposes but it does contain a lot of nice examples along these lines from everyday life, like UPC codes and ISBN codes.

Answer 4

The Hamming code is a good suggestion, but, going back to your question where you mentioned the code with words 00 and 11, I suggest you also mention the code with words 000 and 111, so that you can point out the difference between detecting a (single) error and correcting it. Then, when you continue with more respectable codes, you'll have a framework for saying how good they are.

Answer 5

Maybe the ISBN-Code, demonstrating that it can detect any single altered digit and any transposition of two adjacent digits. Note that only the older ISBN-10 has this property, but not the newer ISBN-13.