Copyright © University of Cambridge. All rights reserved.
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?
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?