Channel Capacity: How Much a Noisy Channel Can Carry

Suppose a line sends one bit at a time and flips it with probability 10%. Sending bits directly gives an average of one error in ten. Repeating each bit three times reduces errors, but the same message occupies the line three times as long. Channel capacity asks how much information each use can carry with arbitrarily small error probability when we are free to design the code.

Information theory and entropy introduces conditional entropy, mutual information, and compression. Here those ideas describe communication: compression reduces the bits needed to represent a source, while channel coding arranges redundancy so that a message can survive noise. All logarithms are base 2; discrete channel capacity is measured in bits per channel use.

Describe a channel with a conditional distribution

In Chapter 9 of MacKay's Information Theory, Inference, and Learning Algorithms, the Noisy channels section defines a discrete memoryless channel through its input alphabet, output alphabet, and conditional probabilities. Write $X$ for the sent symbol, $Y$ for the received symbol, and

$$W(y\mid x)=P(Y=y\mid X=x),\qquad \sum_y W(y\mid x)=1.$$

Each input $x$ has a distribution of possible outputs. Once the sender chooses an input distribution $P_X$, the joint and output distributions follow:

$$P_{X,Y}(x,y)=P_X(x)W(y\mid x),\qquad P_Y(y)=\sum_x P_X(x)W(y\mid x).$$

For now, assume finite alphabets, a channel law that stays fixed over time, no feedback, and a memoryless channel. Memorylessness means that outputs are conditionally independent given the entire input sequence:

$$P(y_1,\ldots,y_n\mid x_1,\ldots,x_n) =\prod_{i=1}^n W(y_i\mid x_i).$$

Coded input symbols can still be correlated. Memorylessness constrains the channel's noise mechanism. Burst noise or a channel that changes over time requires a different model.

Maximize mutual information over the input distribution

For a chosen $P_X$, mutual information measures how much information one output conveys about the input on average. MacKay's Chapter 9 section Maximizing the mutual information defines capacity as

$$C=\max_{P_X} I(X;Y) =\max_{P_X}\bigl[H(Y)-H(Y\mid X)\bigr].$$

Keep $W$ fixed during this maximization: choose how often to use each input symbol, rather than changing the noise probabilities. Sending the same symbol every time carries no choice of message, so its mutual information is zero even if the receiver recognizes it. Uniform inputs often achieve capacity for symmetric channels; that conclusion does not extend to every channel.

Binary symmetric channel: derive and calculate capacity

The binary symmetric channel (BSC), one of MacKay's Chapter 9 models, flips each input bit with probability $p$ and preserves it with probability $1-p$. Flips on separate uses are independent. Here inputs index rows and outputs index columns:

Input	$Y=0$	$Y=1$
$X=0$	$1-p$	$p$
$X=1$	$p$	$1-p$

Define binary entropy as

$$H_2(t)=-t\log_2 t-(1-t)\log_2(1-t),\qquad 0\log_2 0:=0.$$

Let $q=P(X=1)$. Both possible inputs face the same flip probability, giving $H(Y\mid X)=H_2(p)$. Also,

$$P(Y=1)=p(1-q)+(1-p)q=p+(1-2p)q,$$

so

$$I(X;Y)=H_2\bigl(p+(1-2p)q\bigr)-H_2(p).$$

A binary output has entropy at most 1. Choosing $q=1/2$ makes the output uniform and attains that bound. Therefore,

$$C_{\mathrm{BSC}}=1-H_2(p).$$

For the opening example, $p=0.1$:

$$\begin{aligned} H_2(0.1)&=-0.1\log_2 0.1-0.9\log_2 0.9 \approx 0.468996,\\ C_{\mathrm{BSC}}&\approx 0.531004\ \text{bits/use}. \end{aligned}$$

Capacity is different from the fraction $0.9$ of bits received correctly. The output does not identify which bits were flipped, so the code must provide enough structure to resolve that ambiguity. The formula holds for known $0\le p\le1$: capacity is 1 at $p=0$, zero at $p=1/2$ because input and output are independent, and 1 again at $p=1$ because the receiver can invert every bit.

Binary erasure channel: the missing positions are known

MacKay's Chapter 9 also defines the binary erasure channel (BEC). The output equals the input with probability $1-\varepsilon$ and becomes a special symbol ? with probability $\varepsilon$. Erasure probability does not depend on the input value, and separate uses are independent. A 0 is never falsely reported as a 1.

Again let $q=P(X=1)$. Receiving 0 or 1 determines the input exactly; receiving ? leaves the original input distribution unchanged. Thus,

$$H(X\mid Y)=\varepsilon H_2(q),\qquad I(X;Y)=(1-\varepsilon)H_2(q).$$

Uniform inputs give $H_2(q)=1$, so

$$C_{\mathrm{BEC}}=1-\varepsilon.$$

At $\varepsilon=0.1$, capacity is $0.9$ bits/use. With the same 10% probability of damage, erasures allow more information through than the BSC's $0.531004$: the receiver knows which positions are missing and can trust every surviving bit. For flips, it must also work out which positions are wrong. This comparison depends on what each model reveals to the receiver; the shared number “10%” does not make the channels equivalent.

What the noisy-channel coding theorem guarantees

Sections 13–14 of Shannon's 1948 paper establish the noisy-channel coding theorem and its long-message formulation. MacKay's Chapters 9–10 give the following form for the finite discrete memoryless model above.

An encoder maps $M$ possible messages to input codewords of length $n$; a decoder estimates the message from the output. The code rate is

$$R_n=\frac{\log_2 M}{n}\ \text{bits/use}.$$

For $k$ message bits, $M=2^k$ and the rate is $k/n$. A block error means the whole message was not recovered correctly, rather than a particular transmitted symbol being corrupted.

For any fixed target rate $0<R<C$ and any tolerated block error probability $\delta>0$, sufficiently large block lengths admit a code of rate at least $R$ and a decoder whose worst-case message error probability is below $\delta$. Block error probability can therefore tend to zero while maintaining a positive rate below capacity. Conversely, at a fixed rate above $C$, block error probability cannot tend to zero.

This is an existence result for coding schemes. It does not make every code effective, specify the required block length or an efficient decoder, or guarantee zero errors for a finite block. The achievability statement above requires strictly $R<C$; it gives no such guarantee at exactly $R=C$. For the BSC with $p=0.1$, a target rate $R=0.5$ is below $0.531004$ and satisfies the achievability condition; $R=0.6$ exceeds capacity.

Repetition codes: residual error and the rate cost

MacKay's Chapter 1 starts with threefold repetition: encode 0 as 000, encode 1 as 111, and decode by majority vote. If 000 was sent, receiving 010 still decodes to 0, while 011 is incorrectly decoded as 1.

Each codeword carries one message bit using three channel uses, so $R=1/3$. With independent flips of probability $p=0.1$, an error requires at least two flips:

$$\begin{aligned} P_{\mathrm{err}}&=\binom32 p^2(1-p)+p^3\\ &=3(0.1)^2(0.9)+(0.1)^3\\ &=0.027+0.001=0.028. \end{aligned}$$

The message block contains just one message bit, so decoded bit error and block error have the same probability here. Error falls from 10% to 2.8%, at the cost of reducing the rate to about $0.333333$ bits/use.

For odd repetition length $n$, use the binomial distribution to calculate the probability of a majority of flips:

$$R=\frac1n,\qquad P_{\mathrm{err}}=\sum_{j=(n+1)/2}^{n}\binom nj p^j(1-p)^{n-j}.$$

Repetitions $n$	Rate (bits/use)	Decoded error probability, $p=0.1$
1 (uncoded)	1.000000	0.10000000
3	0.333333	0.02800000
5	0.200000	0.00856000
9	0.111111	0.00089092

For $0<p<1/2$, increasing repetition length without bound drives majority-vote error toward zero, but also drives the rate $1/n$ toward zero, away from a fixed positive capacity. Codes near capacity must carry increasing numbers of message bits as their block length grows.

Joining fixed threefold repetition codewords into a longer message does not supply the theorem's long-block coding either. For $m$ independently encoded message bits, the probability that at least one is wrong is $1-(1-0.028)^m$, which tends to 1 as $m$ grows. With $m=100$, this is $1-0.972^{100}\approx0.941571$, or about 94.16%. Repetition demonstrates that redundancy can correct errors; how the redundancy is arranged matters too.

Gaussian channels: specify power and units

A conditional distribution can also describe continuous inputs. In MacKay's Chapter 11 Gaussian model, $Y=X+Z$, where $Z\sim\mathcal N(0,\sigma^2)$ is independent of the input and noise samples are independent and identically distributed across uses. With average input power constrained by $E[X^2]\le P$ and real-valued inputs allowed, capacity per use of one real dimension is

$$C_{\mathrm{real}}=\frac12\log_2\left(1+\frac{P}{\sigma^2}\right) \ \text{bits/use}.$$

A zero-mean Gaussian input of variance $P$ maximizes mutual information. The power constraint is essential: without it, increasing input amplitude makes capacity unbounded. Restricting the input to two levels also changes the problem; the formula allows arbitrary real-valued inputs.

Theorem 17 in Section 25 of Shannon's paper gives the bandlimited additive white Gaussian noise form. With bandwidth $B$ Hz, average signal power at most $S$, and total noise power $N$ within that band,

$$C_{\mathrm{band}}=B\log_2\left(1+\frac SN\right) \ \text{bits/s}.$$

These formulas use different units: one counts real dimensions and the other counts seconds. MacKay's Chapter 11 represents the ideal bandlimited model with $2B$ real dimensions per second. Allocating signal and noise power per dimension preserves their ratio, so multiplying by $2B$ cancels the first formula's factor of $1/2$. For a linear signal-to-noise ratio of 9, the first gives $\tfrac12\log_2 10\approx1.660964$ bits/use. With $B=10^6$ Hz, the second gives $10^6\log_2 10\approx3321928.094887$ bits/s, or about $3.321928$ Mbit/s.

Capacity is an asymptotic limit under a channel model. Short blocks require a separate calculation of error probability at the chosen rate and block length. Low latency or limited computing resources also require comparing the runtime and memory needs of actual encoders and decoders. Shannon's Section 14 observes that the proof's method of approaching ideal coding is generally impractical. The capacity formula alone cannot determine a device's achievable throughput.

Recompute with Python

This example requires Python 3.8 or later because it uses math.comb. It calculates capacities and binomial sums with floating-point arithmetic using only the standard library. The results are model probabilities, with no random sampling.

from math import comb, log2


def h2(t):
    if not 0 <= t <= 1:
        raise ValueError("Probability must be between 0 and 1")
    if t in (0, 1):
        return 0.0
    return -t * log2(t) - (1 - t) * log2(1 - t)


p = 0.1
epsilon = 0.1
print(f"H2({p}) = {h2(p):.6f}")
print(f"BSC capacity = {1 - h2(p):.6f} bits/use")
print(f"BEC capacity = {1 - epsilon:.6f} bits/use")
for n in (1, 3, 5, 9):
    error = sum(comb(n, j) * p**j * (1 - p)**(n - j)
                for j in range((n + 1) // 2, n + 1))
    print(f"n={n}: rate={1/n:.6f}, error={error:.8f}")
threefold_error = 3 * p**2 * (1 - p) + p**3
print(f"100-bit message error = {1 - (1 - threefold_error)**100:.6f}")
snr = 9.0
bandwidth = 1_000_000
print(f"Real Gaussian capacity = {0.5 * log2(1 + snr):.6f} bits/use")
print(f"Bandlimited capacity = {bandwidth * log2(1 + snr):.6f} bits/s")

Output:

H2(0.1) = 0.468996
BSC capacity = 0.531004 bits/use
BEC capacity = 0.900000 bits/use
n=1: rate=1.000000, error=0.10000000
n=3: rate=0.333333, error=0.02800000
n=5: rate=0.200000, error=0.00856000
n=9: rate=0.111111, error=0.00089092
100-bit message error = 0.941571
Real Gaussian capacity = 1.660964 bits/use
Bandlimited capacity = 3321928.094887 bits/s

My reading · Opened notes are remembered in this browser.