19.1: Introduction

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 \(\PageIndex{1}\)

For definiteness, we assume the message to be sent is a string (or “word”) of bits (\(0\)s and \(1\)s). (Information stored in a computer is always converted to such a string, so this is not a serious limitation.)

Example \(\PageIndex{1}\)

Perhaps the word \(0110\) tells an automated factory to close the \(2^{\text{nd}}\) and \(3^{\text{rd}}\) 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 \(3^{\text{rd}}\) valve, and leaves the \(2^{\text{nd}}\) valve open. This could have disastrous consequences, so we would like to do something to avoid such problems.

Example \(\PageIndex{2}\)

One simple solution is to append a check-bit to the end of the message. To do this, we set three rules:

1. We require all messages to have a certain length. (For example, let’s say that all messages must have exactly \(5\) bits.)
2. We require all messages to have an even number of \(1\)s.
3. 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 \(1\)s), then we append \(0\) to the end, and send the message \(01100\). If, say, the \(2^{\text{nd}}\) 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 \(1\)s. 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 \(\PageIndex{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 \(\PageIndex{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 \(2^{\text{nd}}\) 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 \(\PageIndex{2}\)

Let \(\mathbb{T}^n\) be the set of all ternary sequences of length \(n\) (so every entry is \(0\), \(1\), or \(2\)). Write a recurrence relation for \(c_n\), the number of code words from \(\mathbb{T}^n\) that have no \(2\) consecutive zeros. Use generating functions to solve your recurrence relation, deriving an explicit formula for \(c_n\).