Error Detection and Correction

In our first exploration of the intersection of algorithms and data representation, we consider some problems in error detection and correction.

Setting

The table contains a grid of red and blue cards. Sam (or an assistant) will leave the room. You can replace any red card with a blue card, or vice versa. (But just one!)

Sam (or an assistant) will identify which card you switched.

Initial Questions

• How did we tell which cards you switched? (Discuss with a partner.)
  • We did not have a partner in the room signal to us.
  • We did not memorize the layout of the cards.
  • Think about the organization of the cards. (representation)
  • Think about how we check for swaps. (algorithms)
• Can we notice two switches? Three? More?
• Can we restore two switches? Three? More?

Context

• Data gets changed. Sometimes there's a "hic-up" in the system. Sometimes someone mis-transcribes. Sometimes ...
• We need to design mechanisms for checking for errors (aka error detection).
  • We might also design mechanisms for resolving those errors (aka error correction).
• In designing such systems, we consider
  • Efficiency: How much extra information do we have to record in order to detect or correct errors?
  • Limits: How many errors can we detect? Are there particular combinations of errors that are harder to detect?
  • Correction: Can we just detect errors, or can we also correct them?
• What are times in which a sequence of numbers is important, and a switch in the digits would be problematic?
  • We'll make a list of important sequences you've encountered recently or are likely to encounter in the next week or so.

Designing Numeric Algorithms

• Working with your partner, design an algorithm we can use to decide whether a nine-digit number has changed.
  • Optional improvement: Identify which digit has changed.
  • Optional improvement: Identify the correct value for that digit.
  • Optional improvement: Decide whether two digits have changed.

The Luhn Algorithm

The Luhn algorithm is a common algorithm for simple error detection that is used with credit card numbers, among other things.

Adding a Check Digit

• Treat each digit as a separate number.
• Double every other digit, starting from the rightmost.
• Add the digits (including the digits in the doubled numbers).
• Place an aditional digit at the right (the check digit) so that the sum of the digits is evenly divisible by ten.
• For example, consider 387
  • The three digits are 3, 8, and 7.
  • We double the 7 (rightmost) and the 3 (two to the left)
  • We now have 6, 8, and 14.
  • We sum the digits: 6 + 8 + 1 + 4 = 19.
  • To make it divisible by 20, we put a 1 at the end.
  • The result is 3871.

Validating

• Double every other digit, starting from the next-to-rightmost.
• Add the digits of the result.
• Make sure that it's evenly divisble by 10.
• Let's check 5284.
  • The four digits are 5, 2, 8, and 4.
  • We double the 5 and the 8, giving us 10, 2, 16, and 4.
  • We add the digits: 1 + 0 + 2 + 1 + 6 + 4 = 14.
  • The number is not valid.

Questions

• Does this technique let us recover from an error?
• If there are multiple errors, can the number still validate?
• How can we do better?

Citations

Many parts of this exercise were inspired by the CS Unplugged exercise on error detection. That exercise is available at http://csunplugged.org/error-detection/.

Wikipedia reminded me that credit cards use the Luhn Algorithm. https://en.wikipedia.org/wiki/Luhn_algorithm.