Good analogies for teaching error correcting codes

Question

I'm trying to find a good real-world analogy (or even good visualization) for teaching about error correcting codes and erasure encodings. The most natural way to talk about it really is in terms of the lower-order polynomials.

The examples / analogies that I have heard:

• Take a piece of information, split it into a bunch of puzzle pieces including some extra ones. That way, even if someone loses a piece, you can still put the puzzle back together.
  • I find this one a bit weak, as it doesn't really get across the point that the split is generic. You can use any subset that is large enough to get all the information back.
• Think about if you wanted to tell someone else about a line. Two points define a line, so you could just send them 4 points on the line. That way, even if some points got lost, you could figure out which points were missing.
  • I really like this one, but I find some students have a hard time extending their intuition on lines to polynomials immediately. It definitely does a good job of being precise, as it is exactly what is going on.
• It's like a checksum. Imagine you have a bunch of data in binary form, and at the end you put two digits. Both of them are the same, and are 0 if the number of 1s in the binary is even, and 1 if it is odd. That way, if exactly one binary digit changes in transit, you can always notice it. This example then goes into the process of checking the cases of no errors, error in data, and error in check-data.
  • This one is also pretty nice, but then at the end you still have to say "but imagine you could do that but more". Also, it's very data-oriented.

Are there better analogies that can be used to teach this concept?

Answer 1

I'm not sure what exactly a "real world analogy" is, but the idea of "error correcting codes" itself is rather ubiquitous. Just go to the nearest grocery store and, when hearing the usual "paper or plastic?" question, answer something like "plastious" or "vaper". You'll still be understood unless the cashier has really good ears. Orr tri two redd ths sntense. Thn ts vun. End saw on.

The whole point of error correction is that there is some well-defined expected subset of admissible messages and you choose the nearest one (in certain metric) to the message that was actually received. That's more or less how we actually read and listen and, I guess, everyone can come up with an example of a misread or misheard message in his or her life. Of course, if the erratic part is too large and the non-erratic one is too small to provide enough context, one can get perplexed a bit. If you only know that "c_l_nd_r" is an English word, you have at least 3 ways to recover the missing letters. However, if the previous text was about kitchen utensils, errand list for the week, or geometry, the choice becomes fairly clear.

So, if you want to introduce the concept, I would suggest just playing a game when you write or say some messages or draw some pictures that become gradually more and more incomplete or garbled and ask the students to guess the intended meanings. That will also bring up an opportunity to discuss various possible metrics to use when choosing the nearest word/image. You can also play hangman and "turn one word into the other" here with the emphasis on what is a good strategy in such games or to try an exercise like

You know that the actual word is either "file" or "ruin". Your receiving device printed out one of the following words:

file pile pale tale tall tail rail rain ruin

Which correction would you choose for each of them and why?

(with the emphasis that there is no "the only correct answer" here for the middle of the list but if you need to teach the machine to distinguish and correct automatically, you still have to formalize unambiguously how your choice is made).

Just my two cents.

Fedja

Answer 2

While it is too mathematically sophisticated for your course, continued fractions offer an analogue. If I tell you an initial part of the decimal expansion of a rational number, sometimes something as small as even $3\%$ of the repeating part of the decimal, then in practice the whole rational number (its numerator and denominator) can be recovered in two steps: (i) write the finite decimal as a continued fraction and (ii) truncate that continued fraction right before an unusually large entry and use the preceding part of the continued fraction as your guess for the correct rational number. Some reasons for wanting to guess rational numbers this way are in my answer here; see also the answer (and comments to it) by Andreas Blass here.

The analogy between what I just said and error-correcting codes is that continued fractions offers a way to reconstruct, in practice, a rational number from incomplete information about it (just a small part of the period of its decimal expansion). In fact, the analogy is closer than what I suggested: one of the methods of correcting errors in a BCH code can be described in terms of convergents to a continued fraction of a rational function $\mathbf F_q(x)$ where the coefficients of the denominator depend on the received message.

Answer 3

There are some well-known examples, like bank account numbers (at least in Belgium), which consist of twelve digits, something like:

$$\overline{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$$

There is the general rule:

$$\overline{a_{11}a_{12}} = \mod(\overline{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}}, 97)$$

As a result, when you type a bank account number and you miss a digit, that condition won't stand anymore and you'll get a warning about your mistake.

A same thing exists for books with so-called ISBN numbers: the last digit is the reminder of the rest while dividing by 11. If ever the result is 10, then an X is used.

Answer 4

Some easy examples I would probably use for error correction and information redundancy:

• Bad phone connection and people with hearing aids
  Most people naturally talk slower, intentionally elongating their words. This ensures that most of the information gets through to the recipient, even if occasionally bits and pieces get lost on the way.
• Explaining as a teacher
  We often try to explain concepts with different (and redundant) examples, knowing that not all of them reach each student.
  "The average rate of change can be used to calculate the average speed. Like monitoring how fast bitcoins are losing value or determining, if a video is trending."
• Marriage vows and love letters
  Lovers often struggle to express their feelings verbally, which makes them use more words than necessary, giving redundant information and often even repeating themselves, hoping to get the point across.
• Mafia comedy movies
  Trying to get the point across without actually saying it
  Fredo, go and take care of Antonio Balucci. I want him iced, you know? Accidents happen. Make him sleep with the fishes...

For two dimensional error correction it might be good to show a heavily compressed jpeg of a text. Yes, it's readable, but we have to add missing and change wrong pixels in our mind to reconstruct the letters. And since there are only 26 possible letters to choose from we automatically work the same tricks as, say, a prefix code.