Today’s post is a bit about coding theory, and how a good code can detect and even correct errors from transmission.
A code is k-error-detecting if and only if the minimum Hamming distance between code words is at least k+1.
A code is k-error-correcting if and only if the minimum Hamming distance between code words is at least 2k+1.
Hamming distance is the number of bits in which the code words differ. For instance, the Hamming distance between 1000 and 1001 is 1 since they only defer in the last bit.
Proof of Theorem 1
Lets assume a code is k-error-detecting. Suppose to the contrary the there is a pair of code words c_1 and c_2 with Hamming distance k or less. Then, given the code word c_2, we don’t know if it is a valid code word, or it arose from c_1 due to errors in k-bits. This contradicts the fact that the code is k-error-detecting.
If the minimum Hamming distance is at least k+1, then given a code that differs from a code word by k bits, we know that it is not a valid code word, and hence we have detected a error!
Proof of Theorem 2
Assume the code is k-error-correcting. Suppose to the contrary there is a pair of code words c_1 and c_2 whose Hamming distance is 2k or less. Then if there is a code word whose Hamming distance is k from c_1 and c_2, then it is equally likely to have arose from c_1 or c_2, hence we can’t correct the error!
If the Hamming distance is 2k+1 or more, then any code word with Hamming distance of k (or less) will be closer to one of the code words, and hence has higher probability of having arose from that code word.
During the winter of 1952, British authorities entered the home of mathematician, cryptanalyst and war hero Alan Turing (Benedict Cumberbatch) to investigate a reported burglary. They instead ended up arresting Turing himself on charges of ‘gross indecency’, an accusation that would lead to his devastating conviction for the criminal offense of homosexuality – little did officials know, they were actually incriminating the pioneer of modern-day computing. Famously leading a motley group of scholars, linguists, chess champions and intelligence officers, he was credited with cracking the so-called unbreakable codes of Germany’s World War II Enigma machine. An intense and haunting portrayal of a brilliant, complicated man, The Imitation Game a genius who under nail-biting pressure helped to shorten the war and, in turn, save thousands of lives.