More Secret Transmissions
Problem
This problem follows on from Secret Transmissions, so if you haven't had a go at it yet, you should try it first.
In the problem Secret Transmissions, you were invited to explore a system for detecting and correcting errors in transmissions.
Imagine you now had to send five 'bits' (0 or 1) of information, instead of just four. Can you devise a system of error detection and correction that will allow your message to be corrected if there is at most one error in transmission?
How many check digits would you need?
What if you had more than five 'bits'? Can your method be generalised?
If you were sending an n-bit message, how many check digits would you need?
Extension:
Suppose there were two errors in transmission. Can you find an error detection system that would alert you to this, and enable you to correct the message?
Very challenging extension
Suppose each digit of the message might be 'flipped' (a 0 switched to a 1 or vice versa) with probability p=0.1. Explore the likelihood of messages appearing to be transmitted correctly but actually arriving with errors that can't be detected. Can you devise a system where the correct message could be retrieved 99.99% of the time?
Getting Started
In Secret Transmissions, the check digits were in position 1, 2 and 4 of the 7 digits, and the message digits were in position 3, 5, 6 and 7.
Digits 1, 3, 5 and 7 contained an even number of 1s.
Digits 2, 3, 6 and 7 contained an even number of 1s.
Digits 4, 5, 6 and 7 contained an even number of 1s.
What do you notice about the position of the check digits in the message?
Where might you put the next check digit in a longer message?
How can you determine which message digits 'belong' to each check digit?
Teachers' Resources
Why do this problem?
This problem continues the theme of error detection and correction from the field of Information Theory explored in the problem Secret Transmissions.
Possible approach
Begin by giving students some time to try the problem Secret Transmissions. Once they have had a go at making sense of and understanding the error detection and correction method, set them the challenge:
"What if I wanted to send more than four digits? Can you come up with a way of extending the error detection and correction method?"
Invite students to work together in small groups to try out their ideas, and once they have come up with a possible solution, encourage them to compose simple binary strings and 'transmit' them with one bit switched for someone else in the group to detect and correct.
Finally, allow some time for discussion of the methods that emerged.
Key questions
What do you notice about the position of the check digits in the message?
Where might you put the next check digit in a longer message?
How can you determine which message digits 'belong' to each check digit?
Possible extension
The extension tasks suggested in the problem should offer a challenge to any student who wants to explore further.
Possible support
See the Teachers' Notes to Secret Transmissions for some suggestions of how to scaffold the original task.