-
Let’s say you’re going to the moon and you only have the ability to send email messages back and forth to the earth (no talking). Someone on earth has a computer with an email program running, and the astronauts have their own computer with email running.
They have decided to use three-letter acronyms as messages. For example, RTD means “ready to dock” and “ELF” means “Error light flashing”.
So they start writing out all the acronyms they want to use. Unfortunately, they discover a problem with the quality of the transmissions. Because of the unreliability of the signal, there is better than a 50% chance that one of the letters in the transmission will accidentally be received as a different letter. For example, when transmitting “RTD” (ready to dock) there is better than a 1-in-2 chance that one of those letters will be received incorrectly (maybe “RTN” meaning “Ready for Tang”)
They have to be careful what they choose. Let’s say they allow RTD and RTN to be in their vocabulary of acronyms. Houston receives a transmission from the astronauts that says “RTD”, and they interpret that to mean “ready to dock”. What they don’t realize is that the astronauts really sent the message “RTN”, and there was an error during transmission – the “N” was changed to a “D”. Houston can’t have 100% certainty that the astronauts are ready to dock, so they are unable to act on the message. The “D” that was received MIGHT HAVE started as an “N”, but was changed to a “D” due to an error.
There are some ways to help Houston and the astronauts communicate under these conditions.
Houston, We Have Fewer Problems
One way would be to make sure no two acronyms differ by only a single letter. RTD and RTN would not be accepted, because of the potential of the third letter being transmitted incorrectly and being identified as the wrong acronym. RTD and RNG would be better, because a single error for either acronym would still give 100% certainty of the original message.
Another way would be for the sender to send every message twice. The odds are small that the same error will occur to the same message sent twice. If Houston receives the message RTD, followed a minute later by another message RTD, they can be confident that the message sent by the astronauts was, in fact, RTD. There is still a possibility, though, that the same error occurred twice during transmission, so Houston could never be completely sure.
Sending Self-Verifying Messages
Another way would be for the sender to send an additional set of information about the message. Consider that R is the 18th letter of the alphabet, T is the 20th, and D is the 4th. If you add those positions together, you get 42. Adding the letters RTN together the same way, you get 18+20+14 = 52. Using this formula, we could have the astronauts first send the acronym (RTD) followed by the sum of their alphabet positions (42). When Houston receives this transmission, they can compare the letters they get with the number that follows, and make sure they match up. If they don’t, Houston will know they did not receive the correct transmission. For example, if Houston receives RTD44, they will know one of the letters is incorrect. (It is possible to have the correct numeric value and the wrong letters, but since only one mistake can happen per transmission, this won’t be an issue.)
Binary Messages
Going back to recent lessons (here and here) in binary math, let’s create a vocabulary of binary messages and see if we can find a way to know if the message was garbled as it made its way to earth.
Starting with a vocabulary of three messages: 010100 means “Ready to Dock”, 011101 means “Ready for Tang” and 010101 means “Moon Buggy Battery Dead”. These messages are different, but they’re similar to each other - there is a possibility a 1 or 0 that is transmitted incorrectly will be interpreted as the wrong message. “Ready to Dock” (010100) is very close to “Moon Buggy Battery Dead” (010101).
What can we do to make sure Houston knows whether an error occurred during transmission or a binary message?
Parity Bit Concert Friday! Cover Charge $1010
A tried-and-true method in computer communications is called a “parity bit.” The parity bit is an additional bit (1 or 0) that is appended to the message. (“Parity Bit” is also a great name for a rock band.)
Here’s how we’ll use a parity bit: with each of the binary values we send to earth, we’ll add a ‘1’ to the end if there is an odd number of ‘1’s in the original message. If there is an even number of 1s in the original message, we’ll add a zero. In other words, we always send a complete message with an even number of 1s in it, and we either add a 1 or a 0 to the end of the original message to satisfy that rule.
For example, sending the Ready to Dock message: we’ll send 010100 and add a 0 to the end (because there is already an even number of 1s in the message.)
0101000
Houston will receive this value and will count the 1s. If there is an even number of ones, they have a good feeling about it and accept it as valid.
Let’s say an error occurs during transmission, and Houston receives 0101010. Checking the number of 1s, they will find an odd number, and know that an error occurred.
If the astronauts sent the message “Moon Buggy Battery Dead” 010101 they will need to add the parity bit 1 to the end because there is an odd number of 1s in the original message. So they will the message 0101011. Houston will, as before, count the 1s in the message they receive and decide if it’s valid.
Another way to use binary values to send messages is to do what we did with letters above, and set up the “words” we send so that they are not close enough to one another that one error in transmission can cause confusion.
Making Good Choices Up Front
Better values for the three binary messages would be 110000, 001100, and 000011. There would have to be more than one error during transmission for each of these to be received incorrectly by Ground Control. 110001 could still be interpreted as 110000, assuming that at most one error can occur. 010000 would also be interpreted as 110000 because in order for either of the other two values to be incorrectly received that way there would have to have been at least 3 errors in transmission.
These types of alphabets/languages are referred to as “error-correcting codes.” They are set up in such a way that they can be received and translated with a set amount of certainty. Part of this branch of mathematics has to do with the minimum length of a message in order to allow for a given amount of errors. For example, the set of binary messages 110000, 001100, and 000011 will allow 1 or 2 errors to occur before it is impossible to tell what the original message was. (110000 is the original message, and 100001 was received. Two errors occurred during transmission, and Houston will not be able to tell whether the original message was 110000 or 000011, since the message received is an equal “distance” from those two possible messages.)
One of my favorite classes in college was a math class that dealt exclusively with the ways to create these kinds of alphabets, and ways to determine the likelihood of errors. Our textbook was Introduction to the Theory of Error-Correcting Codes by Vera Pless.
-
No comments:
Post a Comment