|Lesson A: Error Detection|
This lesson was adapted from a freely available sample lesson in
Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See
for more information.
Motivation:When data is transmitted from one computer to another, it usually gets there correctly. But sometimes things go wrong and the data is changed accidentally. This activity shows a way to detect an error in data transmission, and to correct the error. What is presented here is a brief summary of the Card Flip Magic activity described in Computer Science Unplugged. Please refer to that document for more details.
Conclusion:Remind the students that they can think of the colored and white cards as 1s and 0s. Also, that each row could be a number, a piece of an image, or text. They can probably see now after the magic card trick that by simply adding an extra bit of information they can correct errors in transmitted data. This check bit is already built into credit card numbers, UPC symbols, and ISBNs. In fact, the check digit in an ISBN is the last digit. You check it by taking 1 times the first digit, 2 times the second, 3 times the third, etc. (through the ninth digit) and summing these values. Divide this sum by 11 and take the remainder. This number should match the 10th digit of the ISBN. Notice that the remainder when dividing by 11 could be 10 which is not a digit! If this is the case, the 10th digit of the ISBN will be 'X'. (See for example Flatland, ISBN 0-486-27263-X.)
Extensions:A student will probably ask "what if we flip 2 cards?" This question leads to interesting exploration. Have the students try it and see if they can figure out what's happening. If two cards are flipped it is not possible to determine exactly which two cards were flipped, although it is always possible to tell that something has been changed. Have them experiment with 3 flips, as well. They should be able to figure out how to flip 4 cards so that the parity cards will still be correct. Point out to them that this means 4 errors could get through without detection.
The corner card of the parity row and column is worth discussing with the students. Experimentation should show them that the parity row and column both have an even number or an odd number of colored cards (we say that they "have the same parity'').
Have the students explore what would happen if you performed this same magic trick using 3 different colors of cards. How is the check bit assigned? Can errors be detected? How? Can errors be corrected?
Students may find it interesting to research the number theoretic process of "casting out nines" which provides error detection in arithmetic.
Finding errors is often easier than fixing them. There is a vast literature on error correcting codes containing some materials suitable for middle school and above. Refer to CS Unplugged for some starting points.
This lesson was adapted from a freely available sample lesson in Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for more information.