Warning
This chapter is still in development
Warning
This chapter hasn’t been written yet, but in the meantime there is a lesson plan that covers the material available from the NZACDITT site. The content of this chapter will mainly support this lesson plan.
Note
For teachers
This chapter supports the encoding part of the NZ achievement standard AS91074 (2.44).
You might or might not have heard of the parity magic trick. <iframe width=”560” height=”315” src=”http://www.youtube.com/embed/OXz64qCjZ6k?rel=0” frameborder=”0” allowfullscreen></iframe>
The magic in the trick is actually computer science, using the same kind of technique that computers use to detect and correct errors in data.
Error control coding is adding extra bits to data that allow Computers need to be able to detect and correct errors, because of how easily the 0’s and 1’s that the data consists of can get changed. Hard drives, CDs, and data going over a network all require error control coding.
By the end of this chapter, you should understand the basic idea of error control coding, the reasons why we require it, the differences between algorithms that can detect errors and those that can both detect and correct errors, and some of the possible limitations in error control coding. We will look at several examples, including the Unplugged parity magic trick, and the systems used to help ensure you enter credit card numbers, book numbers, and product barcode numbers correctly.
[Need to mention that it does go a little beyond the achieved requirements, but that we still recommend working through it all, except for the advanced bit at the end].
Students should include an explanation of when they carried out the parity trick with a friend, showing the original 5x5 layout, the parity bits they added, and the card their friend flipped, describing how it works in order to demonstrate understanding. More teacher guidance of this is given within the text when the activity comes up.
This is not the only option for achieved in error control coding. The algorithms in some of the other sections can easily be used for achieved, this is explained within those sections. This may be useful if you are getting sick of always seeing the parity trick and want to try something different for a change!
Please note that this section is not suitable for the merit/ excellence requirements for encoding. For these requirements students need to do a more advanced project on either compression, error control coding, or encryption that discusses and evaluates how a widely used technology i enabled by techniques from at least one of those 3 topics, whereas this section just focuses on a simplified version of an algorithm used in error control coding. If they choose error control coding to focus on for merit/ excellence, then later sections give ideas on how they could go about this.
If you have never seen the parity magic trick before, check out the video in the previous section. This section assumes that you know what is meant by the parity magic trick, but it isn’t assumed you know how it actually works! You will need a set of parity cards, either your teacher will provide these for you to use, or you can make your own. .. Might want to give a little more guidance about where to get parity cards.
Basically, a magician asks an observer to lay out a 5 by 5 grid of cards, and the magician then says they are going to make it a bit harder, and add an extra row and column to make the grid 6 by 6. The magician then faces the other way while the observer flips over one card. The magician turns back around again, and tells the observer which card was flipped!
The question now is, how did the magician know which card had been flipped without seeing the card being flipped, or memorising the layout?!
So now, assuming you at least know what the parity trick is, you will shortly be able to to show off your magic skills to a friend or classmate! Basically you just need to do the following. If you are confused by the instructions, you can find more indepth instructions here. .. TODO: add link to unplugged page 1) Ask your friend to layout 25 parity cards in a 5 by 5 grid, trying to have a reasonably random mix of blacks and whites. 2) Make sure they don’t have any cards in their hand still (as you don’t want their (well meaning) help with this next step!!!), pick up the pile of cards, and then say that actually, 5 by 5 is too easy so you are going to make it 6 by 6. Instead of adding the new row and column randomly though, you should add the new cards so that they make an even number of blacks in each column or row. This is the key thing that makes the trick work. 3) Tell your friend that you are going to face the other way, and you want them to flip over one card while you are not looking. 4) Turn around again once they have flipped a card, look through the rows and columns, identifying a row and then a column that has an odd number of blacks in it. The flipped card will be the one at the intersection of that row and column. Flip that card back over. It would take some practice to be able to add the extra cards, and identify the flipped card without the observer noticing that you are actually thinking rather than using some form of genuine magic, although it doesn’t matter for the purpose of this exercise. You might want to master the trick though so that you can fool your family or people at a party with it though! Or perhaps even try and be like the busker in the video!
erase the grid from their short term memory, meaning that they have to completely rely on the trick rather than any memorisation. The user should then click the card that has been flipped, and the computer will tell them if they are right or wrong, and why (if they got it wrong). Well, it might be better if it guides them to the right answer. .. This will allow the student to practice the trick with guidance, and then once they are confident they can test their “magic” skills with an actual person.
At this point, you should understand how to carry out the parity magic trick. The parity magic trick is based on a very simple form of using parity for error control coding. By carrying out the trick, you should hopefully have some idea of how it actually works.
So, how does this parity magic track actually work? And what does it have to do with computer science?
The black and white cards represent bits. The 5 by 5 grid that was initially laid out is essentially 25 bits of data. In this case it was random data, but the 25 bits could have been meaningful (for example, they could have represented 5 numbers using 5 bits for each number, or perhaps even an image or 5 character message using the 5 bit text representation system talked about in the bits and representations chapter).
When a card was flipped, this simulated an error occurring in the data.
The cards in the additional row and column that were added to make the grid 6 by 6 are called parity bits. These bits are what allowed the error that was created to be detected and then corrected.
The error detection is the process of identifying that there is a row and column that has an odd number of black bits in it. Remember that when you added the parity bits, you made it so that there was an even number of blacks in each column and row. So then when a single bit is flipped, this results in the row and the column that had that bit now having an odd number of black bits in it, making it really obvious which bit was flipped.
If for example, your friend who had the job of flipping one of the bits around while you were facing the other way decide to fool you and not flip any bits, when you then go to detect the error, you will find all columns and rows still have an even number of black bits in them. On the other hand, when they have flipped a bit, you can tell that they have, as there will be a row and/ or column that has an odd number of black bits in it. Using this rule, you can determine whether or not an error has occurred, i.e. error detection. This isn’t the entire truth, it is possible to have errors that the detection will say there are no errors, but we will look at this later!
Error correction requires knowing which bit has actually been flipped. This is done by identifying both the row and the column that have an odd number of black bit in them, and then flipping over the bit that is at the intersection, as it has to be the one that had the error.
You may be wondering why emphasis is being put on the errors being able to be corrected as well as detected, as in the above example it seems trivial to correct the error once it is detected. There are many algorithms that could be used to detect when an error has occurred, but they are unable to know what the exact error was, so cannot detect it.
Imagine if we have our 5 by 5 grid, but we only have a single parity bit. This parity bit should force there to be an even number of black cards, including the parity bit. So if there was an odd number of black cards in the original 5 by 5 grid, the parity bit should be black. Otherwise, if there was an even number of black cards, then the parity bit should be white. Lay out a 5 by 5 grid using your parity cards. In your 5 by 5 grid, what colour should your parity bit be? Put a 26th card next to your layout, displaying the correct parity bit colour. If somebody flips over a card, you should find that it is possible to tell that an error occurred, as there will now be an odd number of black cards (including the parity bit). However, it is impossible to know which bit was flipped using this simple system, meaning that while you could detect that an error occurred, you cannot correct the error. What happens if 2 cards were flipped over in this system? Can you detect that an error occurred still? Why/ Why not? And what about 3 cards? 4? 5? Did you notice a pattern in when this very simple error detection system can and cannot detect errors? .. Some of this is redundant, although I thought it could be good to get them thinking with analyzing this very simple system before analyzing the actual parity trick...
So going back to the actual parity trick that has the 5 by 5 grid, and 11 parity bits to make it 6 by 6, it is interesting to realise that only 1 bit was needed to detect that an error had occurred, but an extra 10 bits were needed to be able to correct the error. In terms of the cost of an algorithm, it costs a lot more space to be able to correct errors than it does to be able to simply detect them!
Now that you know the difference between error detection and error correction, you can analyze what kinds of errors can be detected, and which can also be corrected. Using your parity cards to experiment, try flipping over 2 cards instead of 1. Can the error be detected? Can it be corrected? Try flipping over 3 cards, and 4, and 5. Are there some specific examples of flipping over multiple card that error detection and possibly correction work on, wherea other examples of flipping over that same number of cards stop them from working?
You were carrying out the parity trick using a 6x6 grid (including the parity bits). Would it work with a 8x8 grid and a 10x10 grid? What about with a 5x5 or a 7x7 grid? (i.e. an odd number)
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
[explain where the material above has oversimplified things, and if there are any well-known concepts or techniques that have been deliberately left out because they are too complex for this age group. This may include things that require advanced maths, advanced programming, or things where students have seen the problem but not a thorough solution] Codes actually used, Reed-Solomon. Generalisation: Hamming(7,4) and Hamming codes, Hamming distance, 3D parity could correct more errors Hamming at : http://www.multiwingspan.co.uk/as1.php?page=error