## Information is noisy

Submitted by Marianne on March 24, 2015*This article is part of our Information about information project, run in collaboration with FQXi. Click here to find out about other ways of measuring information. *

Our channels of communication aren't perfect. Whether you send a message by email or by smoke signal, there's always the chance that some random interference mangles it up on the way. Surprisingly though, you can always reduce the error rate to nearly zero, simply by choosing a clever way of encoding the message.

### Flipping bits

How do you cope with errors?

To get a feel for this, imagine you want to transmit the outcome of
a coin flip to me via some long-distance communication channel, writing a 0 for heads and a 1 for tails. You know there's a chance that a 0 will get
changed into a 1 on the way, and vice versa. Can you come up with a code that is
secure against such *bit flipping*? You might try using two bits per
outcome, writing 00 for heads and 11 for tails. If a 01 or a 10
arrives at the other end, then I will know that an error has
happened. But I won't know which of the two bits was flipped, so I
can't deduce whether you originally sent a 00 or a 11.

Let's instead try a code using three bits; 000 for heads and 111 for
tails. If I see a sequence that isn't one of those two I
won't only know that there has been an error. Assuming that only one
bit per three can be flipped, I will also know what triple
was the original: if the erroneous string has two 0s then the
original was 000, otherwise it was 111. Such a way of encoding, which
secures against errors, is called an *error correcting code*.

The example illustrates an important idea. You can get to
grips with errors by introducing *redundancy*: extra symbols
that reduce the chance that an error corrupts the
message. "This idea shows up all over the place," says Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology. "The
English language, or any other language, has lots of redundancy
built into it. If you miss one little piece of what I said you can
still understand the sentence. This is a property of human languages:
we don't maximally compress the information for a good reason."

### Errors versus redundancy

Just how error-proof can you make things using such error-correcting codes? In our example above the error rate would be zero if we could we sure that the
channel only
ever flips one bit per block of three. In reality things aren't
that predictable: you might know that your channel flips one bit per three
*on average*, but this doesn't mean
that it can't occasionally change a 000 standing for heads into a
011, leaving the receiver none the wiser as to what the intended
message was.
You might look for a
cleverer code to guard against this, but the point is that whatever code you use, there's still a chance
of ambiguity, leading to an error in the decoded message at the other end.

It seems that to reduce that chance, all you can do is add more redundancy. This would also make your transmission much less efficient since you need more bits to transmit a single symbol. It also puts you in danger of entering an arms race. If I ask you to produce a code that reduces the error rate to some small number, you need to add a certain amount of redundancy, if I reduce my required error rate further, you need to add more redundancy, an even smaller error rate requires even more redundancy, and so on, beyond all limits. A near-zero error rate would then require a near-infinite amount of redundancy, which means near-zero efficiency.

Radio transmissions can be noisy.

In the earlier days of long-distance communication this was indeed what people thought: when you're dealing with a noisy channel, you have no choice but trade your error rate for redundancy. In 1948, however, the mathematician Claude Shannon proved them wrong. In his ground-breaking *Mathematical theory of communication* Shannon showed that given any error rate, no matter how small, it's possible to find a code that produces this tiny error rate and enables you to transmit messages at a transmission rate that is only limited by the channel's capacity. This result is known as
Shannon's *noisy channel coding theorem*. It shows that near-error-free transmission doesn't lead to near-zero efficiency.

If you have read the previous article, you won't be surprised to hear that the noisy channel theorem involves the entropy of the source that produces the information (such as a coin flipping machine). Loosely speaking, the entropy measures the average amount of information carried by a symbol produced by the machine. Adding redundancy to a message reduces the amount of information per symbol and therefore lowers the entropy. What Shannon showed is that once the entropy is below some critical value, a code with an arbitrarily small rate of decoding error can always be found.

### Finding the best code

How do you find that magic code? Unfortunately, Shannon doesn't tell us. "Shannon didn't give a single concrete example of what code you would use," says Aaronson. His proof merely shows that if you pick a code at random from a set of suitable candidate codes, then with overwhelming probability that code will do. It's quite an amazing result, but not a very useful one. "Picking a code at random would not be computationally efficient. You might need a prohibitive amount of computational power to decode it." But Shannon wasn't concerned with that; his aim was to see what could be done with noisy channels in principle.

Which brings us right up to date. "A lot of the research in information theory in the 60-plus years since Shannon's paper, you can think of as an attempt to make Shannon's result explicit: trying to come up with an explicit error correcting code that is able to transmit information at close to the [maximal] rate that Shannon's theoretical construction gives you," says Aaronson. "There has been a lot of progress, especially in the last twenty-five years. There are now codes that can be encoded and decoded very efficiently and come close to [Shannon's limit]. These codes have major applications. They are used in CDs, in sending messages to space probes, etc. They are used all over the place in electrical engineering."

Shannon's ideas have been hugely influential, but his way of measuring information has a curious feature. The entropy measures the average information of a symbol produced by a particular information source. It tells us nothing about the information contained in one string of symbols produced by the source compared to another. Surely there must be a way of measuring that too? Find out more in the next article.

### About this article

Marianne Freiberger is co-editor of *Plus*. She would like to thank Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology, for a very useful conversation about information. And she recommends the book Information Theory: A Tutorial Introduction by James V. Stone as a mathematical introduction to the subject.