19.1: Introduction
( \newcommand{\kernel}{\mathrm{null}\,}\)
When information is transmitted, it may get garbled along the way. Error-correcting codes can make it possible for the recipient of a garbled message to figure out what the sender intended to say.
Assumption 19.1.1
For definiteness, we assume the message to be sent is a string (or “word”) of bits (0s and 1s). (Information stored in a computer is always converted to such a string, so this is not a serious limitation.)
Example 19.1.1
Perhaps the word 0110 tells an automated factory to close the 2nd and 3rd valves. If we send that message over a wireless network, interference (or some other issue) might change one of the bits, so the factory receives the message 0010. As a result, the factory closes only the 3rd valve, and leaves the 2nd valve open. This could have disastrous consequences, so we would like to do something to avoid such problems.
Example 19.1.2
One simple solution is to append a check-bit to the end of the message. To do this, we set three rules:
- We require all messages to have a certain length. (For example, let’s say that all messages must have exactly 5 bits.)
- We require all messages to have an even number of 1s.
- We agree that the final bit of the message (called a “parity check-bit”) will not convey any information, but will be used only to guarantee that Rule 2 is obeyed. (Thus, each message we send will have 4 bits of information, plus the check bit.)
In particular, if we wish to send the message 0110 (which already has an even number of 1s), then we append 0 to the end, and send the message 01100. If, say, the 2nd bit gets changed in transmission, so the factory receives the message 00100, then the factory’s computer control can see that this cannot possibly be the intended message, because it has an odd number of 1s. So the factory can return an error message, asking us to send our instructions again.
Note
As a real-life example, bar-code scanners used by cashiers employ the above principle: if the check-bit is not correct, then the scanner does not beep, so the cashier knows that the item needs to be rescanned.
Exercise 19.1.1
Under the rules of Example 19.1.2, which of the following strings are allowed to be sent as a message?
00110,10101,00000,11011.
It is sometimes not feasible to have a message re-sent (for example, if it spends a long time in transit), so it would be much better to have a system that enables the recipient to correct transmission errors, not just detect them.
Example 19.1.3: (Triple-Repetition Code)
We could agree to send each bit of our message 3 times. For example, if we want to send the message 0110, then we would transform (or “encode”) it as 000111111000. If, say, the 2nd bit gets garbled, so the factory receives 010111111000, then it knows there was a problem in the transmission of the first 3 bits, because they are not all the same. Furthermore, since most of these bits are 0, the factory can figure out that we probably meant to say 000, and correctly decode the entire message as 0110.
The triple-repetition code works, but it is very inefficient, because only one-third of the bits we send are conveying information — most of the bits are check-bits that were added to correct the possible errors. After developing some theory, we will see some codes that are able to correct every single-bit error, but use far fewer check bits.
Exercise 19.1.2
Let Tn be the set of all ternary sequences of length n (so every entry is 0, 1, or 2). Write a recurrence relation for cn, the number of code words from Tn that have no 2 consecutive zeros. Use generating functions to solve your recurrence relation, deriving an explicit formula for cn.