3.6. Error Detection¶

Time Estimate: 45 minutes

3.6.1. Introduction and Goals¶

As we have learned from Blown to Bits, "everything is bits" -- i.e., all data are represented as binary 0s and 1s.

Suppose your bank is doing an electronic funds transfer and one of the bits involved switches from 0 to 1 or vice versa? This is known as a flipped bit. It could happen because of an error during transmission or while the data is being written to a disk drive. And the error could make a significant difference. For example, if we use only 8 bits then flipping the leftmost bit 00000001 to 10000001 changes the value from $1.00 to $129.00. But if we used 16 bits, then flipping the leftmost bit of 0000000000000001 to 1000000000000001 changes the value from $1.00 to $32,769.00.

When something like this happens would it be possible to detect the error? In this video based on this Computer Science Unplugged project, you'll see a card trick that shows that it is possible to detect when a bit is flipped. In the video, the face-up and face-down cards are analogous to 1s and 0s.

Watch carefully to see if you can figure out how the flipped card is detected!

(Teacher Tube version)

Learning Objectives: I will learn to

execute an algorithm to determine if, in a given binary sequence, a bit has been flipped
understand the conditions under which a flipped bit can be detected and corrected
explain the consequences of using bits to represent data

Language Objectives: I will be able to

use target vocabulary, such as parity and parity bit while describing how errors in data can be detected, with the support of concept definitions and vocabulary notes from this lesson

3.6.2. Learning Activities¶

What's the Algorithm?
Here's a bit more explanation about the card trick.
	The widget on the left was created by Mobile CSP student Richard Zheng of Westhill High School in Stamford, CT, to help figure out how the card trick works. To follow up on the hint given in the video, after the demonstrator has added an extra row and column to a 5x5 array of cards (or Androids in this case) -- supposedly to make the problem more difficult -- the Androids will appear as they do in the widget. Try shuffling and then flipping one of the cards and to see if you can figure out the trick. Examine the rows and columns. What changes for the 6x6 array when a robot if flipped?
Try to figure out the algorithm that is used to identify the flipped Android.

POGIL Activity for the Classroom (30 minutes)

Break into POGIL teams of 4 and assign each team member one of the following roles. Record your answers using this worksheet.

Role	Responsibility
Facilitator	Manages interaction with the Parity Magic widget to help test the team's algorithms.
Spokesperson	Reports the teams results to the teacher and other teams.
Quality Control	Records all answers & questions, and provides the team's reflection to team and instructor.
Process Analyst	Considers how the team could work and learn more effectively.

Error Detection: Critical Thinking Questions

For this activity, each group should have 36 playing cards (or 25 for a smaller square) or use this virtual deck or use the widget above. For a regular card deck you can use face-up/face-down to represent 0/1. A satisfactory outcome for this activity is that the team can successfully demonstrate the trick to the class. That means, someone will lay out a 5x5 array of cards randomly. Then a member of the team will layout the 6th row and column and will successfully identify the flipped card when some from the class secretly flips a single card.

In the video, are the 6th row and 6th column being laid out in a truly random way or is some kind of rule or algorithm being used? If so, what's the rule?
HINT: Count the number of face cards in each row and column? What pattern or rule do you see if you do that?
Practice: Everyone on the team should practice the "trick" using the widgets or the deck of cards.
(Portfolio) What is the "trick"? Of course, it's not really a trick. It's an algorithm. So, describe an algorithm in pseudocode that solves the problem of identifying the flipped card.
(Portfolio)The card "trick" shows that it is always possible to identify the card that was flipped as long as only one card was flipped. Would it be possible always to determine if an error occurred if two cards were flipped? Experiment with the cards or widgets to help answer this question.
In this case, the 25 original cards (bits) are data and the 11 additional bits are for error detection, meaning that 25/36 = 69% of the bits are data and 31% are redundant bits used for error detection. Suppose the original array was 3x3. How many error detection bits would you need in that case and what percentage of the total bits would now be data bits?

Parity Bit Error Detection

As you learned in the POGIL activity, the card "trick" is really not a magic trick at all. It is a very precise algorithm of error checking based on the concept of parity. In mathematics, parity refers to the evenness or oddness of a number. In the card trick, a parity bit - which is a bit that is added as the leftmost bit of a bit string to ensure that the number of bits that are 1 in the bit string are even or odd - was added to each row and column such that the additional bit would make the row or column have an even number of 1 bits. It's important to realize that the parity bit is not part of the data. It is redundant, an extra bit, added to the data to allow us to detect if one of the data bits has been flipped from its original value.

3.6.3. Summary¶

In this lesson, you learned how to:

3.6.4. Still Curious?¶

This lesson has shown that it is possible to detect certain kinds of error in digital documents. The technique used here, called parity checking, uses redundancy. That is, extra bits are added to the data to enable us to detect the error.

What about detecting errors that involve more than 1 bit? Is it possible to not only detect an error but to automatically correct it? The answers to these questions is 'Yes' and 'Yes.'

If you want to learn more about this topic, here are a couple of reading suggestions:

3.6.5. Self-Check¶

Vocabulary

Here is a table of some of the technical terms we've introduced in this lesson. Hover over the terms to review the definitions.

parity
parity bit

Check Your Understanding

Complete the following self-check exercises.

Q-1:

Find the flipped bit.
For this table, identify the bit that was flipped.

1	0	0	1
1	1	1	1
0	0	1	1
0	1	0	0

The bit in row 4 column 4.
The bit in row 4 column 3.
Don’t worry, it’s hard! Let’s go back and try it again.
The bit in row 1 column 2.
Don’t worry, it’s hard! Let’s go back and try it again.
The bit in row 2 column 2.
Don’t worry, it’s hard! Let’s go back and try it again.

Q-2:

Complete the trick.

For this 3 x 3 table of bits, which of the choices below would be the correct 4 x 4 table for being able to detect when bit is flipped.

1	0	0
1	1	1
0	0	1

1 0 0 1

1 1 1 1

0 0 1 1

0 1 0 0
Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
1 0 0 1

1 1 1 1

0 0 1 1

0 1 1 1
Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
1 0 0 1

1 1 1 0

0 0 1 1

0 1 0 1
Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
1 0 0 1

1 1 1 1

0 0 1 1

0 1 0 1

3.6.6. Reflection: For Your Portfolio¶

Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File/Make a Copy to make your own editable copy.

You have attempted of activities on this page