Secret Transmissions
Problem
Agent X is a secret agent in the field. She needs to transmit enemy movements back to base. Her opportunities to send messages are limited so she has to transmit the data as accurately and efficiently as possible.
To transmit the compass direction of the enemy movements, she uses this diagram:
Agent X sent the message 0010 because the enemy were travelling North-East. Unfortunately one of the digits was altered in transmission so her base camp received the message 1010, South-West, instead!
Before reading on, you may wish to think of ways of sending extra information to try to get the message through even if a digit might get altered.
One method of sending communications is to include an extra "check" digit.
Agent X decides to send one extra digit on the end so that the message always contains an even number of 1s. She claims that if at most one digit is incorrect (which could be the check digit), it is always possible for her team to tell if the message is correct or not. Is she right?
Here are the messages she sends. Which ones are error-free?
For each message containing an error, how many different starting messages could Agent X have sent?
With a single check digit, the agents know when there is a mistake but can't work out what the original message should be, so Agent X decides to introduce some more check digits so that her team can recreate her message even if there is an error.
If you would like to try creating a system of check digits, have a go now before reading the hidden text below to see what Agent X did. You can assume that there will be at most one error.
Agent X wants to send the message abcd, where each letter represents 0 or 1.
She works out:
- a check digit x (either 0 or 1) so there are an even number of 1s in xabd
- a check digit y (either 0 or 1) so there are an even number of 1s in yacd
- a check digit z (either 0 or 1) so there are an even number of 1s in zbcd
Agent X then transmits the message xyazbcd.
For example, if Agent X wants to send 0110, she calculates that x= 1, y=1 and z=0. She then transmits 1100110.
If you receive Agent X's message, how can you check whether there is an error?
If you find that there is an error, is it possible to recreate the original message?
Read the hidden text to find out how the agents back at base check and correct Agent X's messages.
The base camp can check whether the message they receive has been transmitted correctly by counting the number of 1s in xabd, yacd and zbcd.
If these are all even numbers, the message has been transmitted correctly, and they can read off the message Agent X sent by reading the 3rd, 5th, 6th and 7th digits.
If one or more of these strings xabd, yacd, zbcd contains an odd number of 1s, the base camp can work out which digit has been altered in transmission.
For example, suppose b has been altered in transmission:
xabd and zbcd will contain an odd number of 1s.
The fact that yacd has an even number of 1s in it means y, a, c and d must have been transmitted correctly.
The only digit that is in both xabd and zbcd, but not in yacd, is b, so they can deduce that b is the incorrect digit.
They can then correct the error and read off the message Agent X transmitted.
Another example: suppose base camp receives the message 0100111.
| x | y | a | z | b | c | d |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 |
xabd: Even
yacd: Odd
zbcd: Odd
This means that x, a, b and d are all correct, one of y, a, c and d is incorrect, and one of z, b, c and d is incorrect. The digits that appear in both yacd and zbcd are c and d, but we know d is correct, so c must be the incorrect digit. So the message should have read 0100101, so Agent X sent 0101, or North-North-West.
Here are the messages that Agent X sent using the new system. Again, you can assume that there is at most one altered digit.
Which ones have been transmitted error-free?
Can you correct the incorrect messages?
Is it always possible to correct a message that contains an error?
How do you know?
You can follow up these ideas in the problem More Secret Transmissions.
Error detection and correction is an important part of Information Theory. You can read more about some of the ideas explored in this problem in this Wikipedia article.
Getting Started
This Venn diagram shows the relationship between the check bits and the message bits. We can use this to work out which digit has been altered. Suppose we find that yacd and zbcd contain an odd number of 1s, and xabd contains an even number of 1s. We look at the intersection of y, z and not-x (any region that x isn't in), which is c. This therefore tells us that c has been altered in transmission.
Student Solutions
Donald, from Verulam, had a good idea to try to ensure the message went through uncorrupted:
Repeat the original message after the true message and the check digit. For example, if 1110 is the original, and 11101 is the original and check, then 111011110 is the original and check and original again. Transmit this message. We can split this up, 1110 1 1110. If each number is changed, e.g. 1111 1 1110, then we look at the 1st original message '1111' and the 2nd original message '1110'. If they are the same, then this is probably the correct message. If not, then look at the check digit.
This question was a 'Toughnut' until Michael sent in this excellent solution. Click here to see it. Well done Michael!
Teachers' Resources
Why do this problem?
This problem introduces the important idea of error detection and correction from the field of Information Theory, which has applications in Computer Science.
Possible approach
Begin by introducing the compass wheel and explaining the problem:
"Agent X needs to transmit that the enemy were travelling North East, but she knows that one of the digits might be flipped in transmission, from a 1 to a 0, or vice versa. Talk to your partner and see whether you can come up with any ways she could send her base camp some extra information to ensure the message gets through."
Possible suggestions that might emerge are sending the message multiple times, or perhaps sending a check digit.
Then introduce the idea of check digits:
"Agent X decides to add one extra digit to the end so that the message always contains an even number of 1s. She claims that if at most one digit is incorrect (which could be the check digit), it is always possible for her team to tell if the message is correct or not. Is she right?"
Allow some time for discussion. Then give students the following nine messages with check digits and ask them to work out which are error-free, and how many different possible starting messages there are for those which include an error:
Next, hand out this worksheet.
"A single check digit can only tell us if there has been an error, but not what the error is. Here is a system of three check digits that Agent X claims can be used to detect AND correct an error in her message, as long as there is no more than one."
Give students time to make sense of the check digit system in small groups and to have a go at recreating the correct messages for the four transmissions on the sheet.
"Decide on a direction to send, and work out the three check digits. Then swap with your partner, after making a change to one of the seven digits. Can they work out what your message should say?"
Finally, allow some time to discuss how and why the check digit system allows error detection AND correction for any message with at most one error. The hint shows a diagram that may help students to make sense of how the check digits interact.
Key questions
If digit a is changed from a 1 to a 0, what is the effect on xabd, yacd, and zbcd?
What if digit b, c or d is changed?
What if digit x, y or z is changed?
Possible extension
More Secret Transmissions invites students to consider an error detection and correction system for longer strings of binary digits.
Possible support
This worksheet contains a couple of examples showing how Agent X's code works.
For a simpler introduction to the ideas of error detection, see Book Codes which looks at ISBN codes.