Error Correcting Codes

First, I have six treatments to go; 12 in total.

Since I'm just laying in bed right now with nothing else to do I will do my best to explain what an error correcting code is. There is a decent Wikipedia article on Forward Error Correction, which is a place where ECC find their application. You would be amazed how many things in your life utilize ECC (hard drives in computers, portable flash/thumb drives, CDs, DVDs, everything you do on the Internet, etc.). It is an aspect of communications systems. Basically, in a communication system, you can never really be sure that the person you're talking to heard you right... and if you're listening, you can't be sure that what you heard was right.

Human speech is a sort of example of a communication system but it's hard to use as a good example because it is highly redundant to begin with (you don't really need to hear all of what someone says to know what they're talking about). And our brains are exceptional computers and we have a hard time abstracting the process of discerning what it is that someone said. So to use speech in my next example, I will contrive an example that doesn't use English words.

Imagine that there are two people in a crowded food court at a mall and they are separated by some distance. One of them knows the winning lottery numbers and needs to tell the other so he can buy a ticket. You really want to be pretty certain you heard the numbers right. One option is to have the sender scream loudly (which in actual terms means increasing the power of the transmission). Say he's got a sore throat though so he can only get so loud (which is analagous to the very real scenario of something like a cell phone, where it can only be so powerful given that it's a handheld device running on a small battery). You can hear him but not great. Another option is to have him repeat each number twice. If you hear two different numbers, you know there's been a mistake. You don't which number is correct though. You can yell back and ask him to repeat it (which is a form of communications protocol, known as a negative acknowledgement or NACK). But that takes time to do, and maybe you've lost your voice or something so you can't do it to begin with (a simplex or one-way communications channel). The sender could say each number three times, and you could take a majority vote of the three copies you received. This way you can detect and correct one error. (actually the "detection" part might be more, but it's complicated because my example isn't bits, it's words).

The fact that you send the "data" three times and take a majority vote at the receiver is a rudimentary and highly suboptimal example of an error correcting code. There are many thousands of pages that have been written about the various clever ways one can mathematically encode data such that errors can be detected and in some cases corrected in a communication system. Pretty much all modern forms of communication would fall apart without error correcting codes. So they're pretty interesting and useful.

Forward error correction is a way of preemptively putting information in that will enable the receiver to detect and possibly correct errors. If you can't detect that an error has likely occurred, you wouldn't know to ask for that piece of information again. And if you can correct it without any intervention from the sender, you don't have to go through the process of asking for the piece again and verifying it was correct. There are many applications where the penalty for asking for information again is great and you would really prefer that it all just get there right the first time.

A good real life example of this is geosynchronous satellites. That is, satellites whose orbit matches that of the earth (they are always appear to be over the same spot on the earth, not orbiting around it since they have an orbit that matches that of the earth). The physics of it means that all such satellites are about 22,200 miles above the earth. If you are trying to communicate over a satellite channel, the speed of light becomes annoying. The fastest you can possibly hope to get data to the satellite is about 0.12 seconds (thanks to the speed of light). Now the satellite has to beam it back down to earth as presumably you are not talking to an astronaut on said satellite. That takes another 0.12 seconds. So to send anything, it takes 0.24 seconds for the receiver to receive it. So you say "Hi", it takes him 0.3 seconds to receive it. He says "Hey there to you too", and it takes another 0.24 seconds for the "Hey" to make it back to you. You can imagine it is very annoying to have a 0.5 second delay in your conversation. It will be very awkward and you'll be asking each other to repeat things and stopping in the middle because you realize you're both talking at the same time. It's even worse when you're dealing with digital data. If you send one letter at a time, and the receiver can't correct an error, he has to ask for a retransmit, meaning it will take 0.72 seconds just to get the second copy (0.24 to send/receive the letter, 0.24 for the receiver to transmit a NACK and for the transmitter to receive said NACK, 0.24 for the sender to send the letter again). You can see that the penalty for failure adds up quick. You want it right the first time.