Noiseless binary
C = 1 bit
No errors.
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.
This page is easier if you are comfortable with:
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.
Capacity is the highest rate at which information can be sent through a noisy channel with arbitrarily few errors.
Noise lowers the number of bits that can be sent reliably per use.
These examples are worked by hand, step by step, so you can compare your own working.
Find the capacity of a noiseless channel with 4 input symbols.
Find the capacity of a binary erasure channel with erasure probability 0.25.
Find the capacity of a binary symmetric channel with crossover probability 0.1 ().
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
C = 1 bit
No errors.
C = 1 − H(0.1) = 0.531
H = 0.469.
C = 0
Output independent of input.
bits per use below C can be sent reliably
Shannon’s theorem.
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.
Find H(0.1) = −0.1 log₂ 0.1 − 0.9 log₂ 0.9.
Find C for a binary symmetric channel with p = 0.1.
Find C when p = 0.5.
Rate 0.4 against C = 0.531.
bits via log ✗
use log₂ ✓
Capacity is in bits.
C = 1.2 ✗
C ≤ log₂ of the alphabet size ✓
Binary inputs carry at most 1 bit.
C = 0.1 ✗
C = 0.531 ✓
Flip the output; symmetric about 1/2.
low error possible ✗
impossible reliably ✓
Converse of Shannon’s theorem.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
0.1887
0.9192
1
0.278
0.131
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
The maximum rate of reliable communication.
Maximise mutual information over inputs.
0.
Not with vanishing error.
binary symmetric channel.
Singleton and Hamming bounds.
More in Advanced statistics and stochastic processes and the formula sheets.