Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Channel Capacity

Mutual Information and Discrete Channels

Model a noisy channel as a probability matrix, compute joint entropy and mutual information in Python, and see how much a received symbol tells you about the sent one.

So far you have measured how much information a source produces. A communication system also has a channel between the sender and the receiver: a wire, a radio link, a scratched disc, a memory chip. The channel is noisy, so what comes out is not always what went in. The central question of this chapter is: how much information about the input survives the trip?

The answer is a single number called mutual information. In this lesson you describe a discrete channel with a matrix, compute mutual information from a joint distribution, and learn why it is the right measure of "what the output tells you about the input". It builds directly on entropy and conditional entropy from the earlier chapters.

A channel is a conditional probability table

A discrete memoryless channel has an input alphabet X, an output alphabet Y and a table p(y | x): given that the sender used symbol x, the probability that the receiver sees y. "Memoryless" means every use of the channel is independent of the others.

If you also choose how often the sender uses each input, p(x), then everything else follows:

  • the joint distribution is p(x, y) = p(x) * p(y | x);
  • the output distribution is p(y) = sum over x of p(x, y).

The table is written as a matrix with one row per input and one column per output. Each row sums to 1, because something always comes out.

flowchart LR
  S["Sender: X"] --> C["Channel p(y given x)"]
  N["Noise"] --> C
  C --> R["Receiver: Y"]

A channel turns each input symbol into a random output symbol.

Mutual information

Mutual information I(X;Y) measures how much knowing Y reduces your uncertainty about X:

TEXT
I(X;Y) = H(X) - H(X|Y)
       = H(Y) - H(Y|X)
       = H(X) + H(Y) - H(X,Y)

All three forms are equal. The last one is the easiest to compute: you only need three entropies. Two extremes help you build intuition:

  • If the output is independent of the input, H(X,Y) = H(X) + H(Y) and I = 0. Nothing gets through.
  • If the output determines the input, H(X|Y) = 0 and I = H(X). Everything gets through.

Mutual information is always between 0 and min(H(X), H(Y)), and it is symmetric: I(X;Y) = I(Y;X).

Python Mutual information from a joint table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "check" line shows the original definition: the average of log2( p(x,y) / (p(x) p(y)) ). It compares the real joint probability with what you would see if X and Y were unrelated. That ratio is exactly one when they are independent, so the logarithm is zero.

From a channel matrix to I(X;Y)

In practice you are given the channel matrix and you choose the input distribution. Here is a reusable function: it builds the joint from p(x) and the matrix, then returns the mutual information.

Python A channel matrix and its mutual information

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the same channel gives different numbers for different input distributions. Mutual information depends on both the channel and how you use it. The next lessons exploit this: the best possible value over all input distributions is the channel's capacity.

Why it is "information"

Mutual information has a neat operational meaning. If you use the channel n times with inputs drawn independently, the outputs let you narrow down the input sequence from about 2^(n H(X)) typical possibilities to about 2^(n H(X|Y)). The reduction, 2^(n I(X;Y)), is how many distinguishable messages you can send. Shannon's noisy-channel theorem turns this counting argument into a precise promise.

Mutual information is measured in bits when you use log2, in nats with the natural logarithm. Machine learning code usually uses nats; communication theory usually uses bits. The values differ by the constant factor ln 2.

Data processing inequality

If X -> Y -> Z forms a chain, so that Z depends on X only through Y, then I(X;Z) <= I(X;Y). Processing the received data, by filtering, compressing or computing features, can never create information about the original input. It can only throw some away. This explains why you want to keep the raw received signal as long as possible in a decoder, and why a second noisy relay never helps.

Python Processing cannot add information

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Chaining two channels multiplies their matrices, and the second value is always smaller.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which expression equals the mutual information I(X;Y)?

    I(X;Y) = H(X) + H(Y) - H(X,Y). The other expressions are a sum of marginals, a conditional entropy and a sum of conditional entropies.
  2. 2. What is I(X;Y) when X and Y are independent?

    If they are independent, the joint entropy is the sum of the marginals, so the difference is zero: the output tells you nothing about the input.
  3. 3. A channel matrix has rows that each sum to what?

    Each row is the distribution p(y | x) for one input, so it must sum to 1.
  4. 4. What does the data processing inequality say?

    For a chain X -> Y -> Z, I(X;Z) <= I(X;Y). Post-processing cannot create information that the channel did not deliver.

Summary

  • A discrete memoryless channel is a matrix of probabilities p(y | x) whose rows sum to 1.
  • With an input distribution, you get the joint distribution and the output distribution.
  • I(X;Y) = H(X) + H(Y) - H(X,Y) measures how much the output reveals about the input.
  • It is 0 for independent variables and H(X) for a perfect channel.
  • It depends on both the channel and the input distribution; the maximum over inputs is the capacity.
  • Processing data after the channel can never increase mutual information.

Next: The Binary Symmetric and Erasure Channels