Channel Capacity Explained with Worked Examples

The capacity of a channel is , the largest mutual information between input and output over all input distributions. Shannon's theorem says reliable communication is possible at any rate below bits per use, and impossible above it.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Channel capacity means

The mutual information (mutual information) measures how much the output tells about the input. A noiseless channel with symbols has : for 4 symbols, bits. A binary erasure channel that loses each bit with probability has : for , . For a binary symmetric channel with flip probability 0.1 and equally likely inputs, , which is its capacity (the binary symmetric channel).

The maximisation matters: the best input distribution is not always uniform. Capacity is measured in bits per channel use, and a code of rate can make the error probability as small as we like, with long blocks, by the random-coding argument of the first moment method type. The entropy used is Shannon entropy.

Practical codes such as those limited by the Hamming bound trade rate against reliability, and the source side of the story is the Kraft inequality. The same concept links to KL divergence, since is the divergence between the joint law and the product of marginals.

What is it used for?

Capacity is the highest rate at which information can be sent through a noisy channel with arbitrarily few errors.

How to use channel capacity

  1. Write the transition probabilities .
  2. Express as a function of the input distribution.
  3. Maximise over the input distribution.
  4. The maximum is the capacity in bits per use.

Graph

Capacities in bits per use: noiseless 4-ary 2, erasure 0.75, BSC 0.531noiseless: 2erasure: 0.75BSC: 0.53100.511.522.533.5400.511.52Capacities in bits per use: noiseless 4-ary 2, erasure 0.75, BSC 0.531channelyGraph with x from 0 to 4 and y from 0 to 2.4. Shows bars (3); point noiseless: 2 at (1, 2); point erasure: 0.75 at (2, 0.75); point BSC: 0.531 at (3, 0.531).

Noise lowers the number of bits that can be sent reliably per use.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: a noiseless 4-symbol channel

Find the capacity of a noiseless channel with 4 input symbols.

Worked example
Answer
2 bits2\ \text{bits}
  1. Formula

Example 2: an erasure channel

Find the capacity of a binary erasure channel with erasure probability 0.25.

Worked example
Answer
0.750.75
  1. Formula

Example 3: a binary symmetric channel

Find the capacity of a binary symmetric channel with crossover probability 0.1 ().

Worked example
Answer
0.5310.531
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Noiseless binary

C = 1 bit

No errors.

Binary symmetric, p = 0.1

C = 1 − H(0.1) = 0.531

H = 0.469.

Useless channel, p = 0.5

C = 0

Output independent of input.

Rate

bits per use below C can be sent reliably

Shannon’s theorem.

Word problems

Channel capacity C = max over input distributions of the mutual information I(X; Y), in bits per channel use. Shannon’s coding theorem: any rate below C can be sent with arbitrarily small error probability; above C it cannot.

Binary entropy

Find H(0.1) = −0.1 log₂ 0.1 − 0.9 log₂ 0.9.

  1. 0.3322 + 0.1368
  2. Check: 0.469 ✓0.469.

Capacity

Find C for a binary symmetric channel with p = 0.1.

  1. 1 − 0.469
  2. Check: 0.531 ✓0.531.

Useless channel Higher

Find C when p = 0.5.

  1. 1 − 1
  2. Check: 0 ✓0.

Can we send 0.4? Higher

Rate 0.4 against C = 0.531.

  1. 0.4 < 0.531
  2. Check: yes, reliably ✓Yes.

Common mistakes

Using log₁₀

bits via log ✗

use log₂ ✓

Capacity is in bits.

Capacity above 1 bit

C = 1.2 ✗

C ≤ log₂ of the alphabet size ✓

Binary inputs carry at most 1 bit.

Thinking p = 0.9 is useless

C = 0.1 ✗

C = 0.531 ✓

Flip the output; symmetric about 1/2.

Rate above capacity is possible

low error possible ✗

impossible reliably ✓

Converse of Shannon’s theorem.

Exam tips

  1. C = max I(X; Y).
  2. Bits need log₂.
  3. p = 0.5 gives C = 0.
  4. p and 1 − p equal.
  5. Rate < C is achievable.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. H(0.5) in bits Foundation

1

2. C for p = 0.25 to 4 d.p. Foundation

0.1887

3. C for p = 0.01 to 4 d.p. Foundation

0.9192

4. C for p = 0 Higher

1

5. C for p = 0.2 to 3 d.p. Higher

0.278

6. Gap C − 0.4 for p = 0.1 to 3 d.p. Higher

0.131

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Channel capacity
Maximum reliable rate.
Mutual information
I(X; Y).
Entropy (H)
Uncertainty in bits.
Shannon’s theorem
Reliable below capacity.
Rate
Bits per channel use.
Binary symmetric channel
Flips bits with probability p.

Frequently asked questions

What is channel capacity?

The maximum rate of reliable communication.

How is it computed?

Maximise mutual information over inputs.

What is C for p = 0.5?

0.

Can I exceed capacity?

Not with vanishing error.

Which page covers the BSC?

binary symmetric channel.

Which page covers Hamming bounds?

Singleton and Hamming bounds.

More in Advanced statistics and stochastic processes and the formula sheets.