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 http://unplugged.canterbury.ac.nz/ 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.

Materials:

  1. Deck of 49 two-color cards (one color on each side) for each pair of kids, plus a set of large cards for the teacher.  You may want to have the students make these.

Lesson Plan:

  1. Explain to the kids that you're going to do a magic trick, and that you'll tell them why you're doing it later. 
  2. Have the students gather around leaving a space large enough to lay out the cards. 
  3. Ask one or two students to lay out the cards in a 6 by 6 or larger grid, alternating up colors randomly. 
  4. Casually add another row and column to the layout "just to make it harder." The manner in which you add these cards is the key to the trick. Suppose your cards are colored blue and orange. Then each new card is added so that there are an even number of blue cards in each row and column. For example, if the students have placed 3 blue and 3 orange in a row of the layout, you would add a blue card to that row.  If there are 4 blue and 2 orange, you would add an orange.
  5. Explain to the students that you are going to close your eyes, they will turn over a card, and you will be able to determine "magically" which one they changed. 
  6. Choose a student to change a card, and close your eyes. The students will tell you when they're ready. 
  7. All you have to do to determine which card was flipped is to find the row and column which now contain an odd number of blue cards. The intersection of that row and column is the flipped card. 
  8. Flip the card back and repeat the game as many times as you want. 
  9. Be sure to have the students try to guess how the trick is done. 
  10. Finally, offer to show the children how it is done. They will say "YES!" 
  11. First demonstrate how the trick is done to the whole class.  You can do this fairly quickly since they will have an opportunity for deeper understanding after they each have a set of cards.
  12. Have the students pair up and distribute a deck of 25 cards to each. 
  13. Get each pair to lay out their own cards in a 4 by 4 square, choosing randomly which color faces up. 
  14. For younger students, check that they understand the notion of odd and even numbers, and that they know that zero is an even number. 
  15. Explain that the row and column of cards they are about to add are the "parity" cards. 
  16. Tell them to add a card to every row and column in such a way that there is an even number of colored cards in every row and column. Give them an example. 
  17. Finally, have them turn over any single card, and point out what happens to the number of colored cards in the row and column of that card. 
  18. Once they see how to find the flipped card, have them practice the trick on each other. 
  19. After they do it a couple times, have them get together with another pair to do the trick with more cards. 

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. 

Standards:

  • NCTM K-4:  1, 2, 3, 4, 6, 13.
  • NCTM 5-8:  1, 2, 3, 4, 6, 8.
  • NCTM 9-12:  1, 2, 3, 4, 6, 14.

Skills

  • Problem solving / reasoning / communication / connections
  • Odd/even recognition
  • Counting

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.