Photocopiable for classroom use only.

31
© 2002 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

Activity 4

Card Flip Magic—Error Detection & Correction

Summary

When data is stored on a disk or sent from one computer to another, we usually assume it arrives unchanged. But sometimes something goes wrong, and the data gets altered by accident. This activity uses a magic trick to show how you can detect when data has been corrupted—and how to fix it.

Curriculum Links

• Mathematics: Number, Level 3 and up. Exploring computation and estimation.
• Algebra, Level 3 and up. Exploring patterns and relationships.

Skills

• Counting
• Recognizing odd and even numbers

Ages

• 9 years and up

Materials

• A set of 36 "fridge magnet" cards, colored on one side only
• A metal board (a whiteboard works well) for the demonstration

Each pair of students will need:

• 36 identical cards, colored on one side only

---

32

Photocopiable for classroom use only.
© 2005 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

The "Magic Trick"

Demonstration

Here's your chance to be a magician!

You'll need a pile of identical, two-sided cards. (To make your own, cut up a large sheet of card colored on only one side.) For the demonstration, it's easiest to use flat magnetic cards with a different color on each side—fridge magnets work great.

1. Choose a student to lay out the cards in a 5 × 5 square, with a random mix of sides showing.

Casually add one more row and one more column, "just to make it a bit harder."

These extra cards are the secret to the trick. You must choose them so that every row and every column ends up with an even number of colored cards.

1. Have a student flip over just one card while you cover your eyes. The row and column that contain the flipped card will now show an odd number of colored cards—and that's how you'll spot which card was changed.

Can the students figure out how the trick works?

---

Photocopiable for classroom use only.

33
© 2002 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

Teach the trick to the students:

1. Working in pairs, students lay out their cards in a 5 × 5 grid.
2. How many colored cards are in each row and column? Is that number odd or even? (Remember, 0 counts as even.)
3. Now add a sixth card to each row, choosing its color so that the total number of colored cards in that row is always even. This extra card is called a parity card—a card added purely to make a count come out even.
4. Add a sixth row along the bottom so that each column also has an even number of colored cards.
5. Now flip one card. What happens to its row and column? (They will now show an odd number of colored cards.) Parity cards are what let you know a mistake has happened.
6. Take turns performing the trick for each other.

Extension Activities

1. Try other objects. Anything with two possible "states" works—playing cards, coins (heads or tails), or cards printed with 0 or 1 (to connect this to the binary number system, which computers use).

1. What happens if two or more cards are flipped? (You usually can't tell exactly which two cards changed, though you can tell something changed. Normally you can narrow it down to one of two possible pairs. If four cards are flipped, it's even possible for every parity card to look correct afterward—meaning the error could go completely undetected.)

1. Here's an interesting puzzle: look at the card in the bottom right corner. If you choose its color so that it's correct for the column above it, will it also be correct for the row to its left? (Yes—always.)

1. This activity uses even parity, meaning we always aim for an even number of colored cards. Could we use odd parity instead? (Yes, but then the bottom-right card only works correctly for both its row and column when the number of rows and the number of columns are either both even or both odd. For example, a 5 × 9 grid works fine, and so does a 4 × 6 grid, but a 3 × 4 grid won't.)

---

34

Photocopiable for classroom use only.
© 2005 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

A Real-Life Example for Experts!

This same checking method is used in book codes. Every published book has a ten-digit code, usually printed on the back cover. The tenth digit is a check digit—a digit calculated from the others, used to catch mistakes—just like the parity cards in the activity.

This means that when you order a book using its ISBN (International Standard Book Number), the publisher can check whether you made a typing mistake, simply by recalculating the checksum. That way, you don't end up waiting for the wrong book!

Here's how the checksum is calculated:

Multiply the first digit by ten, the second by nine, the third by eight, and so on down to the ninth digit, which is multiplied by two. Add all of these results together.

For example, the ISBN 0-13-911991-4 gives this value:

(0 × 10) + (1 × 9) + (3 × 8) + (9 × 7) + (1 × 6) + (1 × 5) + (9 × 4) + (9 × 3) + (1 × 2) = 172

Next, divide your total by eleven and find the remainder.

172 ÷ 11 = 15 remainder 7

If the remainder is zero, the checksum is zero. Otherwise, subtract the remainder from 11 to get the checksum.

11 − 7 = 4

Now check: is this the final digit of the ISBN? Yes!

If the last digit of the ISBN weren't a 4, we would know a mistake had been made somewhere.

Occasionally the checksum calculation produces the value 10, which can't be written as a single digit. In that case, the letter X is used instead.

A barcode (UPC) from a box of Weet-Bix™

Grocery store barcodes (UPCs) use a similar idea with a different formula. If a barcode is scanned incorrectly, the final digit won't match its calculated value. When that happens, the scanner beeps, and the checkout worker re-scans the item.

---

Photocopiable for classroom use only.

35
© 2002 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

Check that book!

Detective Blockbuster Book Tracking Service, Inc.
We find and check ISBN checksums for a small fee.

Join our agency—look in your classroom or library for real ISBN codes. Are their checksums correct? Sometimes errors slip through.

Common types of errors include:

• a digit's value is changed;
• two digits next to each other are swapped;
• an extra digit is inserted; or
• a digit is removed.

Can you find a book whose checksum is the letter X (standing for 10)? It shouldn't be too hard—roughly one in every eleven ISBNs should have it.

What kinds of errors might slip past undetected? Can you change one digit and still end up with the correct checksum? What if two digits are swapped—a common typing mistake?

---

36

Photocopiable for classroom use only.
© 2005 Computer Science Unplugged (www.unplugged.canterbury.ac.nz)

What's it all about?

Imagine depositing $10 in cash into your bank account. The teller types in the amount, and it's sent to a central computer. Now suppose some interference occurs on the line while the amount is being transmitted, and the code for $10 gets changed to $1,000. That's no problem if you're the customer—but it's a real problem for the bank!

That's why detecting errors in transmitted data matters so much. A receiving computer needs to check that incoming data hasn't been corrupted by electrical interference along the way. Sometimes, if an error is detected, the original data can simply be sent again. But that's not always possible—for instance, if a disk or tape has been damaged by magnetic fields, electrical exposure, heat, or physical wear. And if data is being sent from a deep-space probe, waiting for a retransmission would be painfully slow! (A radio signal takes just over half an hour to reach Earth from Jupiter, even at its closest point.)

So we need two abilities: recognizing when data has been corrupted (error detection) and figuring out what the original data should have been (error correction).

Computers use the same basic technique as the card-flip game. By arranging bits (the 1s and 0s that make up digital data) into imaginary rows and columns, and adding parity bits to each row and column, a computer can not only detect that an error occurred but pinpoint exactly where. The faulty bit is then flipped back to its correct value—that's error correction in action.

Of course, real computer systems often use more advanced error-control methods capable of detecting and correcting multiple errors at once. A computer's hard disk, for example, dedicates a large portion of its storage space just to error correction, so it keeps working reliably even if parts of the disk fail. These systems are closely related to the parity method you just learned.

And to finish, here's a joke that's much funnier after doing this activity:

Q: What do you call this: "Pieces of nine, pieces of nine"?
A: A parroty error.

---

Solutions and hints

Errors that would slip past undetected are those where one digit increases while another decreases by a matching amount—since the total sum could end up the same either way.