Copyright © University of Cambridge. All rights reserved.
'Secret Transmissions' printed from https://nrich.maths.org/
Show menu
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.