I was going to write a post about how to be a good human being, but I didn't really feel like preaching to my readers from atop a cyber soapbox. Then I thought I might cleverly disguise the lesson in some cool story or anecdote, but I realized that such an act would still qualify as preaching and my audience deserves better. I scrapped my sappy musings (in case you were interested, here's the gist: try to be nice to everyone) and decided to write about something cool: codes.
Suppose that you were talking to your friend over the phone in an area where the reception is poor. She says, "Let's meet up for beer-garitas!" but you hear "Let's meet up for deer fajitas!" Since
deer fajitas is not a word in your everyday vocabulary, and the reception is bad, you assume that you have misheard her.
Beer-garitas is a familiar word, and it sounds a lot like
deer fajitas. You automatically correct the mistake and reply with, "Sure. My place at six. Bring limes."
Now imagine a computer receiving a command with a small error in it. Since errors occur frequently during transmission, we expect quite a few of them. We want our computers to automatically detect and correct minor alterations in received messages. Our machines do not have the advantage of a human brain to help them sort out jumbled commands, so we accomplish our task by cleverly choosing a suitable code.
We will design a language of codewords that our computer can understand. Our computer (let's call it MAX) only understands two symbols, 0 and 1, so all of our codewords should use 0s and 1s. There are codes with different letters and symbols, but I'll save that discussion for another day. MAX can execute four commands:
standby,
turn off,
play music, and
fire the missiles. Errors occur every now and then.
Let's consider the following code for those tasks:
00 = standby
01 = turn off
10 = play music
11 = fire the missiles
This code is just fine in a perfect world, but errors occur here in the real world. Let's say that you sent the message 01 (turn off) but an error occurred and the message 11 (fire the missiles) was received. Catastrophe ensues.
We can improve our code by building in some extra digits. Consider the code:
0000 = standby
0011 = turn off
1100 = play music
1111 = fire the missiles.
Say we want to groove to some Micheal Jackson, so we send the computer the message 1100 (play music.) A single error occurs, and the computer receives 1101. MAX knows that an error has occurred because 1101 is not a codeword in its dictionary. However, MAX cannot tell if the original codeword was 1100 or 1111, since both are only different from 1101 by one digit. Should the computer play music or fire missiles? Tough call for a machine. A single error in
any codeword would produce some number outside the code. MAX would be able to detect any single error, so our second code is superior to the first. Unfortunately, if any single error occurs, MAX cannot tell which codeword was originally sent, and cannot automatically correct the command.
We can fix this problem by making our codewords just a little longer. Consider the code:
000000 = standby
000111 = turn off
111000 = play music
111111 = fire the missiles.
Say we want to send the message 000000 but MAX receives 001000. An error has clearly occurred since 001000 is not command that MAX recognizes. 001000 is different from 00
0000 at one digit, 00
0111 at four digits,
111000 at two digits, and
111
111 at five digits. Since 000000 is the closest codeword to 001000, MAX automatically corrects the command to 000000. In fact, any single error in any codeword could be automatically detected and corrected this way! Now, as long as two errors don't occur in the same command (come on, what are the chances?) MAX won't fire the missiles by accident.
Our CD players use similar principles to make sure that Billy Jean plays smoothly, even when the disc is scratched. The music is stored digitally as a numeric code, but imperfections on the CD surface cause errors when the laser reads the disc. The machine is able to automatically detect and correct these errors so that the music plays seamlessly. How? The numeric code that stores the information was cleverly chosen so that no two codewords were too similar.
The holy grail of coding theory is to find codes such that the codewords are different enough to be robust against errors, short enough to facilitate quick transmission, and diverse enough to accommodate as many commands as need.
If you've made it to the end of this very technical post, congratulations. This is the stuff of fourth year theoretical mathematics. You deserve a beer-garita, you brainiac (or a deer fajita if you are into that). Cheers!
Many thanks to the UVic discreet math department, specifically Dr. Dukes, for teaching me about codes. The information presented here was adapted from an introductory lecture on Coding Theory.