When sending a message between two people, or two computers, the message can often be distorted in the process. One person can mishear another and likewise the signal being transferred between computers can be distorted by electrical interference. Humans can often detect errors when presented with new information if the information doesn’t make sense or doesn’t fit the context. However, computers do not possess this intuition and require methods of error checking when transferring information; the simplest of these methods is called “bit parity”. This activity explores distortion of messages transferred between humans and between computers and how each can evaluate if the message sent is the same as that received.
Learn more in this video!
- As humans, we can often tell if when a message is distorted in transmission.
- Computers don’t have an intuitive sense of what is a reasonable message is - they need a way of checking if it makes sense.
- Computers rely on simple mathematical concepts to verify information.
Class game of telephone
- Have the class sit in a circle and tell them they are going to form a human telephone and transmit a message
- One instructor whispers a message into a student's ear (having an instructor do this ensures a camp-appropriate message)
- That student must whisper that message to the next in the circle, exactly as they heard it
- Students are not allowed to ask for clarification or for the person before them to repeat the message
- This continues until the message is passed all the way around the circle, the last student announces the message out loud to the class (which is likely somewhat nonsense by this point in time)
- Ask the campers if they think this was the message that the instructor started out with (the answer will likely be no)
- Compare the final message to the original, announced by the instructor who began the game
- Ask the campers why they thought the final message couldn’t me the original (because it didn’t make sense)
- Explain the messages can also be distorted when they are passed between computers
- Ask how students think computers can verify if a message has been distorted or not (we need to tell a computer how to do this)
Parity Magic Trick
- Parity is an important concept used in Computer Science and communication technology to ensure that the data that was sent is the same as the data that was received.
- Consider an email. It is essentially a set of bytes each containing 8 bits (1 or 0). These bits are streamed over a variety of communication mediums to get from source to destination, including wireless radios (Wifi), wired ethernet cables, traditional cables lines, and fibre optic lines.
- All of these transmission media have some error rate, meaning that they permute the bits travelling over their lines.
- The error rate is related to many things, often tied to the physics of the communication medium and it’s surrounding environment. Consider that wireless transmissions are sent through the electromagnetic (EM) field that is all around us. Waves in EM fields often collide and interfere with each other. We call this interference or noise.
- We use concepts like parity to check for errors that might occur in transmission of a message to determine if we need to send the message again.
- Parity (and more advanced error checking schemes) are the reason we are able to have error free communication over the internet!
- Consider how much cable/wire/distance a signal from somewhere in Europe must travel through in order to get to somewhere in Canada?
- How high is the chance that an error might occur?
- Yet, we regularly communicate with people from other countries without a second thought! All because we have concepts like parity that help detect errors in our communication!
- That is really cool when you stop and think about it…
- The parity of a number describes essentially whether that number is even or odd.
- We can represent whether a number is even or odd with a single bit, 0 for even and 1 for odd. This single bit is referred to as a parity bit.
- If we look at a byte (in binary) we can figure out the associated parity.
- 0111 0010 has a parity of 0 (even) as the number of 1’s is an even number.
- 0000 0010 has a parity of 1 (odd) as the number of 1’s is odd.
- If we compute the parity before we send the message, and then send the additional parity bit with our message, the receiver can recompute the parity on the other side and then check the parity bit. If the two values don’t match then we know there was an error in the transmission.
- Parity has a limitation however, it can only detect an odd number of errors. If an even number of bits are mutated then it is possible that the parity of the message will remain the same even though the message itself changed!
- We have other more advanced error checking schemes that use the concept of a checksum that is based on the concept of parity, is more advanced.
To Do in Advance:
- Review the conceptual material about parity.
- Ensure the parity cards are prepared for the activity. Order sets from: http://exchange.actua.ca/form/actua-swag-shop
Introduce this activity by describing how communications have “loss” or “noise” associated with them, and that we need a way to ensure that our messages (email, text messages, phone calls etc.) get from the sender to the receiver without errors.
- Announce that the class will send a coded message to one instructor, who is sent out of the room
- Introduce the parity magic cards, which have Url on one side and Bitsy on the other
- Set out the cards so that everyone can see in a 4x4 grid, make sure that there is a mix of Url and Bitsy cards
- Go around the class and let each student take a turn flipping a card
- Once everyone has had a turn, announce that this is the class’ message to the other instructor
- Lay out one more row and column (the parity row and column - making it so that there is an even number of Url icons in each row and column)
- Choose one camper as the “interference” and let them flip one final card
- Call in the instructor who has been patiently waiting outside and watch as they can instantly tell which card was interfered with (they simply match up the row with an odd number of Urls with the column that has an odd number of Urls)
Try this trick several times with the entire group. After a few times, assure them it’s not magic.
- Instead say it's MATH and it's exactly how a computer verifies incoming messages!
Ask to see if the group can determine how you are able to always figure out which card was flipped.
- Keywords/phrases are “pattern”, “even and odd”, “parity”.
If the group has not figured it out, introduce the concept of parity in the context of communications as a hint, repeat the trick and see if that helps them.
- Draw on the board a 4x4 grid of 0s and 1s and see if the class can determine what the extra row and column should be (to make an even number of 1s in each row and each column)
Eventually describe how the card trick works.
- Ground the “answer” in the context of parity and error checking for computers communicating.
- Allow the group to try it themselves in pairs or small groups.
As an extension for older groups, ask them to tell you whether they think there are errors that bit parity cannot detect? Could they detect an even number of errors?
- Note the limitations of pure parity schemes for error detection, explain we have more advanced methods that rely on checksums.
- Note that computers use bit parity to check if a byte has been correctly transmitted but they cannot detect which bit has been changed, the entire byte needs to be resent
Additionally, ask how students think you could correct errors using parity? Refer to the magic trick.
- Since the cards represent binary numbers they only have two values. If you know a particular card is not correct, it must be the other value.
Are there any limitations to error correction using parity?
- Yes, we can only be guaranteed to correct one error if only one error is present.
- Depending on how the errors are distributed in the card game we might be able to correct more than one error, but this is not true in every case, therefore we cannot make that assumption.
- Review the concept of parity.
- Describe how all messages in computers are reduced to 1’s and 0’s that represent the message.
- Describe how parity bits can be computed and sent with the message
- Describe how these messages can be sent over communication mediums that have an error rate.
- Describe how errors can be created by noise.
- Review how we can catch errors in a message if we know the parity, just like in the magic trick.
- Ask about limitations of error detection schemes using parity.
Modifications and Extensions
- Try changing the number of errors introduced in the card game to two, can you detect all errors?
- Do a large person sized version of the card trick with the entire class (if your class has at least 25 people).
- Campers must work in defined groups
- Increase the number of rows and columns in the card trick.
- Make your own parity cards!