Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 37 ยท Channel Capacity

Channel Capacity and Shannon's Noisy-Channel Theorem

Define channel capacity as maximum mutual information, compute it with the Blahut-Arimoto algorithm in Python, and understand Shannon's promise of reliable communication.

In 1948 Claude Shannon made a claim that sounded impossible: over a noisy channel you can communicate with an error probability as small as you like, without slowing down to a crawl, as long as your rate stays below a number called the capacity. Before this, engineers assumed that more reliability always meant a lower rate, for example repeating every bit many times.

This lesson defines capacity, shows how to compute it for any discrete channel with the Blahut-Arimoto algorithm, and explains what the theorem does and does not promise. It uses mutual information and the BSC and BEC.

Capacity

The capacity of a discrete memoryless channel is the largest mutual information you can get by choosing the input distribution:

TEXT
C = max over p(x) of I(X;Y)      (bits per channel use)

For the BSC and BEC the maximizer is the uniform input, and you can write the answer down. For other channels the best input distribution is not uniform. A channel where one symbol is much noisier than the others should use the noisy symbol less often.

The theorem

Think of a code of block length n and rate R = k / n bits per channel use: you map one of 2^(nR) messages to a codeword of n symbols, send it, and let a decoder guess the message.

Shannon's noisy-channel coding theorem has two halves:

  1. Achievability. For every rate R < C and every tolerance ฮต > 0, there is a code, for large enough n, whose probability of decoding error is below ฮต.
  2. Converse. For every rate R > C, the error probability is bounded away from zero, and it tends to 1 as n grows.

The proof of the first half is by random coding: pick codewords at random, and show that on average the decoder errs rarely. It does not say how to build a practical code. It took about 45 years until turbo codes and LDPC codes came close to capacity.

flowchart LR
  M["Message: nR bits"] --> E["Encoder"]
  E --> X["n channel inputs"]
  X --> CH["Channel"]
  CH --> Y["n channel outputs"]
  Y --> D["Decoder"]
  D --> MH["Message estimate"]

A block code of rate R: reliable as n grows if R < C.

Capacity is not a speed limit for a single bit. It is a limit on the rate of a code with long blocks. Longer blocks mean more delay and a more complex decoder; this is the price of reliability.

Computing capacity: Blahut-Arimoto

When the maximizing input distribution is not obvious, use the Blahut-Arimoto algorithm. Start with any input distribution q(x). Repeat:

  1. Compute the output distribution p(y) = sum_x q(x) W(y|x).
  2. For each input compute D(x) = sum_y W(y|x) log2( W(y|x) / p(y) ), the information that input provides.
  3. Update q(x) proportional to q(x) * 2^D(x).

Inputs that provide more information than average get used more often. The algorithm converges to the capacity-achieving distribution.

Python Blahut-Arimoto from scratch

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.

A channel where uniform is not best: the Z-channel

In a Z-channel a 0 is always received correctly, but a 1 turns into 0 with probability p. The two inputs are not equally risky, so you should send 1s less than half of the time. For p = 0.5 the capacity has the closed form log2(5/4) โ‰ˆ 0.3219, and the best fraction of ones is 0.4.

Python The Z-channel prefers fewer ones

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.

Using the uniform input would waste a little capacity, 0.3113 bits versus 0.3219. That is the whole reason Blahut-Arimoto exists: to find the input distribution automatically.

Reliable, but how reliable?

The theorem says error probability can go to zero. How quickly depends on how far below capacity you are. Roughly, error probability falls like 2^(-n E(R)), where E(R) is the error exponent, which is positive for every R < C and shrinks to zero as R approaches C. Practical codes, therefore, trade rate, block length and decoding complexity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How is the capacity of a discrete memoryless channel defined?

    C = max over p(x) of I(X;Y). The uniform input is optimal for symmetric channels like the BSC, but not in general.
  2. 2. What does the converse part of the noisy-channel theorem say?

    Above capacity the error probability stays bounded away from zero, no matter how clever the code is.
  3. 3. Which statement about the theorem's proof is true?

    Shannon's argument averages over random codebooks and proves that good codes exist; finding practical ones took decades.
  4. 4. In the Z-channel, why is the best input not uniform?

    The inputs are not equally reliable, so using the unreliable symbol 1 less often yields more mutual information.

Summary

  • Capacity C = max I(X;Y) is the best reliable rate per channel use.
  • Shannon: rates below C are achievable with vanishing error; rates above C are not.
  • The proof uses random coding and says nothing about decoding complexity.
  • Blahut-Arimoto finds the best input distribution of any discrete channel.
  • Error probability decays exponentially in block length for rates below capacity.

Next: The Gaussian Channel and Bandwidth