What Is Information? A Noisy Channel and a Puzzle

Foundations of Information Theory · Part 1

What does information really mean in communication? An intuitive introduction: information as a reduction in uncertainty, explained with a simple noisy channel.

A noisy signal reaches your phone. How much information actually got through?

Not how many bits were sent, but how much the phone actually learned. This sounds like a simple question, yet answering it properly leads to the three central ideas of information theory: entropy, conditional entropy and mutual information. In this series we build all three from scratch, using one small channel from start to finish.

Before and after

Think about what a receiver knows at each stage of a transmission.

Before the transmission, it does not know which bit is going to be sent. It knows how likely each bit is, but not which one will actually come. During the transmission, it observes a noisy, corrupted version of the signal. Yet even a corrupted copy carries clues, so after the observation the receiver is less doubtful than it was before.

This gives us the idea on which everything else rests:

Information Transferred = Initial Uncertainty − Remaining Uncertainty

Information is a reduction in uncertainty. The rest of this series is about turning this sentence into numbers.

The model

Let us keep the channel as simple as possible. A transmitter sends a bit x, which is 0 or 1, each with probability \tfrac12. On the way, noise w is added, and the receiver observes only

y = x + w.

Block diagram: a transmitter sends x, noise w is added, and the receiver observes y equals x plus w. — Figure 1: The communication model used throughout this series. The receiver never sees x directly; it only sees y.

The noise has nothing to do with the bit being sent, and the receiver knows all the probabilities involved. What it does not know is which bit was actually sent this time.

In a real system the noise is Gaussian and can take any value. To see the ideas clearly, we will let it take only two values. This keeps every calculation small enough to do by hand.

Two channels

Example 1. Let the noise be either -1 or +1. If the transmitter sends 0, the receiver sees -1 or 1; if it sends 1, it sees 0 or 2. These two sets never overlap: every value of y points to exactly one value of x. Whatever the receiver observes, it can decide the bit with complete certainty, so a full 1 bit of information gets through with every transmission, even though there is noise.

Example 2. Now change the noise only slightly, so that it is either 0 or 1. If the transmitter sends 0, the receiver sees 0 or 1; if it sends 1, it sees 1 or 2. Now the two sets overlap at y = 1.

Two number lines. Left: x = 0 gives y = -1 or 1, x = 1 gives y = 0 or 2, no overlap. Right: x = 0 gives y = 0 or 1, x = 1 gives y = 1 or 2, overlapping at y = 1. — Figure 2: Received values for the two channels. In Example 1 the sets for x = 0 and x = 1 never meet. In Example 2 they overlap at y = 1 (shaded).

If the receiver sees 0, it knows the bit was 0. If it sees 2, it knows the bit was 1. But if it sees 1, it cannot tell: the bit could have been 0 with noise 1, or 1 with noise 0. This overlap is where information is lost.

The puzzle

So here is the question that will guide the rest of the series:

In Example 2, how much information gets through per transmission? (A) 1 bit (B) 0 bits (C) somewhere in between

Take a moment and choose your answer. We will not guess: we will calculate it exactly. To do that, we first need a way to measure uncertainty with a number, and that is where the logarithm, and entropy, come in.

Next: Why does the entropy formula have a logarithm?

Back to the series: Foundations of Information Theory

Read the full chapter, with worked problems: Chapter 1 (PDF)