Ready for the solution to the bit check puzzle? If you haven’t already tried it, it is not too late. we have hidden the solutions in the details block below! We should mention that there was a slight gap in the puzzle as stated in that it did not specify whether the number of 1s in a parity check should be odd or even. The solution below assumes the parity should be even, and if we assume instead that it should be odd you get a different answer. Mea culpa for the error, but maybe you can consider it a bonus! Two puzzles for the price of one, and you can read the solution and still try to work out the answer with the odd parity convention instead! Have fun
Solution to Puzzle 3
Start by carrying out the three checks.
GOLD checks bits 1,2,4 and 7.
For the received message it sees 1,1,1,1 in those positions so the GOLD check passes.
]
There are four 1s, so the GOLD check passes.
BLUE checks bits 1, 3, 5 and 7.
It sees 1,1,0,1 in those positions so the BLUE check fails.
RED checks bits 2,3,6 and 7.
It fails because it sees 1,1,0,1 so there are only three 1s in the list.
So we know three things about the corrupted bit.
- It must affect the BLUE check.
- It must affect the RED check.
- It must NOT affect the GOLD check because that one is still reporting correct.
Now look at the positions covered by the checks. Only one of them is checked by BLUE and RED, but not checked by GOLD and that is Bit 3! (as in Bit three exclamation mark, not Bit (3!) as in Bit 6, just to be clear!)
That makes bit 3 the culprit, and since the received value in position 3 is 1, the original bit must have been 0.
The repaired message is therefore: 1101001 and the data being sent was 1101.
You can check the bit checks to make sure this is right.
GOLD sees 1111 so it counts four 1s.
BLUE sees 1001 so it counts two.
RED sees 1001 so it also counts two.
All three checks now pass.
Finally, the actual information is stored in positions 1, 2, 3 and 7.
Those bits are
[
\boxed{1101}.
]
So the damaged transmission has been repaired.
Why does this work?
The clever part is not this particular message. It is the way the seven positions have been assigned to the three checks.
Each bit has its own distinctive check pattern and no two positions have the same pattern, so if exactly one bit changes, the set of checks that fail acts like an address telling us which bit is wrong.
If only GOLD fails, the bad bit must be 4, while if only BLUE fails, it must be 5. If BLUE and RED fail but GOLD passes—as happened here—it must be 3 and so on.
The extra bits do more than tell us that the message is damaged they tell us how to repair it.
Error correcting codes
When most people hear the word “code” they think of a cipher or secret message system, but it really just means a way to encode information. Morse code and ASCII are classical examples. Early pioneers in telegraphy and radio transmission realised that encodings were important not just as a way to tell the operator what message was being sent, but also to help reduce or detect errors. If you choose codes carefully, like BOSS did here, then you can guarantee to detect at least a small portion of any mistakes in your message and increase reliability. The example we have just studied is a special kind of error correcting code called a Hamming code, named after the American mathematician and computer scientist Richard Hamming.
Hamming was thinking about this problem in the early days of computing: if a machine is carrying out a huge sequence of calculations, a single unnoticed error can spoil everything that follows so he wanted a way to reduce those errors. One way would be to carry out the computation several times and check to see if they agree, but that is expensive and Hamming codes give a way to detect and sometimes remove errors at much lower cost.
The particular system used in our puzzle stores four information bits in seven transmitted bits which is clearly cheaper than sending the 4 bit message twice (which would use 8 bits) and actually more secure, as even sending it twice could lead to the same mistake persisting and escaping detection.
Seventy-six years later, the underlying idea still plays a crucial role in computing and communications. When your computer reads data from memory, when information is transmitted through an unreliable channel, or when data is recovered from storage, Hamming style redundancy can be added so that errors do not necessarily destroy the precious information. And in the world of quantum information, where errors are part of the furniture, this will become even more important.
