Mutual Information and the Capacity of a Noisy Channel

A channel is a conditional distribution: given an input symbol, it produces an output symbol according to some fixed law. The receiver sees only the output. Capacity is the largest rate at which a sender can push symbols through that channel and still have the receiver recover them with arbitrarily small error, using a code long enough to matter. That quantity turns out to be a maximum of mutual information over input distributions, and the fact that a single number captures the entire reliable-rate question is the central result of the subject.

Why the maximum is over input distributions

The channel fixes $p(y \mid x)$; the sender chooses $p(x)$. Mutual information between input and output is then a function of that choice alone:

$$C = \max_{p(x)} I(X;Y)$$

The optimization is a concave maximization over a probability simplex, so a maximum exists and any local maximum is global. Concavity is the fact that $I(X;Y)$ is a concave function of the input distribution $p(x)$ for a fixed channel, which together with the compactness of the simplex is what guarantees that a unique set of maximizers exists.

The maximum can be strictly interior, and the binary symmetric channel is the clean demonstration. Let the channel flip each bit independently with probability $\epsilon$, with $0 < \epsilon < 1/2$. Write the input as a Bernoulli variable with $\Pr[X=1] = q$. Then

$$I(X;Y) = H(Y) - H(Y \mid X) = H(Y) - H(\epsilon)$$

because the conditional entropy of the output given the input is exactly the entropy of the flip, independent of $q$. $H(Y)$ is maximized at $q = 1/2$, giving

$$C_{\text{BSC}} = 1 - H(\epsilon) \text{ bits per channel use}$$

At $\epsilon = 0.1$ this is about 0.531 bits; at $\epsilon = 0.5$ it is zero, because the output is independent of the input and nothing can be transmitted; at $\epsilon = 0$ it is one bit, the noiseless case. Note the symmetry: a channel that flips with probability 0.9 is as useful as one that flips with probability 0.1, since the receiver can invert every bit. Capacity depends on the noise magnitude, not its sign.

The interior maximum is not an artefact of the binary alphabet. For a channel whose rows are permutations of one another, which is called a symmetric channel, the uniform input distribution is optimal and capacity reduces to $\log_2 |\mathcal{Y}| - H(\text{row})$, where the row entropy is the same for every input. For channels without that symmetry, the optimal input distribution can be non-uniform, concentrated on the inputs whose conditional output distributions are the most distinguishable, and finding it requires an algorithm rather than a formula.

Two channel models that behave differently

The binary symmetric channel models errors that are independent and affect symbols one at a time. The binary erasure channel instead replaces a symbol with a distinct erasure marker with probability $\epsilon$, and never corrupts it silently. Its capacity is

$$C_{\text{BEC}} = 1 - \epsilon$$

with the uniform input achieving it. The difference between the two formulas is large and instructive. At $\epsilon = 0.1$, the BSC carries about 0.531 bits per use while the BEC carries 0.9. At $\epsilon = 0.5$ the comparison goes the other way: a BSC is useless (capacity zero, since the output is independent of the input) while a BEC carries half a bit, because half the symbols arrive intact and the receiver knows which half. An erasure is a known loss: the receiver knows exactly which positions to repair, and a code needs only enough redundancy to fill the gaps. A substitution is an unknown loss: the receiver cannot tell a flipped symbol from a correct one, so every symbol must be protected. The gap between $1 - \epsilon$ and $1 - H(\epsilon)$ is the price of not knowing where the damage is.

This is why erasure coding is used for storage and packet transport, where a missing block or a dropped packet is detectable, and why forward error correction is needed on links where errors arrive silently. The two problems are not interchangeable even at equal loss rates.

The bandlimited Gaussian channel

Continuous channels replace entropy with differential entropy, and the maximization has a power constraint. For a channel with additive white Gaussian noise of power $N$ and a signal of average power $S$ limited to bandwidth $B$, the maximizing input distribution is Gaussian, and the result is the Shannon–Hartley formula:

$$C = B \log_2\left(1 + \frac{S}{N}\right) \text{ bits per second}$$

The formula is often misread as a hard speed limit on a link. It is a limit on the rate at which information can be conveyed with vanishing error probability, and it is asymptotic in block length. A system operating below capacity with a finite block length still has a nonzero error probability, and the gap to capacity at short block lengths is substantial; the normal approximation to the finite-block-length rate makes the penalty explicit as a term proportional to $\sqrt{V/n}$ where $n$ is the block length and $V$ the channel dispersion.

Two structural consequences follow from the formula and are frequently overlooked. Capacity grows only logarithmically in signal-to-noise ratio, so in the high-SNR regime a tenfold increase in transmit power buys about $\log_2 10 \approx 3.3$ extra bits per second per hertz, which is a poor return. And capacity grows linearly in bandwidth, so bandwidth is the cheaper resource when it is available. Neither statement involves any particular modulation scheme; they are properties of the channel model.

What the coding theorem actually asserts

The noisy-channel coding theorem has a direct part and a converse, and both are needed for the number to mean what people assume it means.

The direct part states that for any rate $R < C$ there exists a sequence of codes, with block length $n$ growing, whose maximum error probability tends to zero. The proof is a random-coding argument: choose codewords independently from the capacity-achieving input distribution, and show that the average error probability over the random codebook can be made small. The argument establishes existence and says nothing about how to construct such a code efficiently, which is why decades of coding research followed; Sparse Parity-Check Codes and Iterative Decoding describes the constructions that now operate within a fraction of a decibel of this bound.

The converse states that for any sequence of codes with rate $R > C$, the error probability is bounded away from zero, and in the strong form it approaches one as the block length grows. The proof uses Fano’s inequality, which relates the conditional entropy of the input given the output to the error probability:

$$H(X \mid Y) \le 1 + P_e \log_2(|\mathcal{X}| - 1)$$

Combining this with the data processing inequality and the capacity bound yields the converse. Fano’s inequality is the workhorse of converse proofs throughout information theory because it converts an error probability into an entropy statement and back.

Neither direction says anything about latency, complexity, or the error probability at a specific finite block length. Those are the questions engineering actually faces, and they are addressed by coding theory rather than by the capacity formula. The dual problem, where the rate is fixed and the acceptable error is a continuous distortion measure, is the subject of Rate-Distortion Theory and the Shape of Lossy Compression.

Computing capacity for a small channel

For a channel given as an explicit matrix, capacity can be computed numerically by maximizing a concave function. The Blahut–Arimoto algorithm alternates between the input distribution and the conditional output distribution, each step increasing the mutual information until it converges to the capacity. A direct numerical maximization over the simplex is simpler for small alphabets and is adequate when the dimension is low.

import math

def mutual_information(px, channel):
    """channel[x][y] = p(y|x). Returns I(X;Y) in bits."""
    py = [sum(px[x] * channel[x][y] for x in range(len(px)))
          for y in range(len(channel[0]))]
    mi = 0.0
    for x, p in enumerate(px):
        if p == 0.0:
            continue
        for y, q in enumerate(py):
            if q == 0.0:
                continue
            joint = p * channel[x][y]
            if joint > 0.0:
                mi += joint * math.log2(joint / (p * q))
    return mi

def bsc_capacity(eps):
    # Closed form for the binary symmetric channel
    h = 0.0 if eps in (0.0, 1.0) else -eps * math.log2(eps) - (1 - eps) * math.log2(1 - eps)
    return 1.0 - h

for eps in (0.0, 0.01, 0.1, 0.25, 0.5):
    print(eps, round(bsc_capacity(eps), 4),
          round(mutual_information([0.5, 0.5],
                [[1 - eps, eps], [eps, 1 - eps]]), 4))

The two columns agree for every $\epsilon$, which is the claim that the uniform input is optimal for this channel. Running the same mutual-information function with a skewed input such as [0.9, 0.1] produces a strictly smaller value, confirming that the maximum is at the symmetric point rather than at an extreme of the simplex, as long as the flip probability is neither 0 nor 1/2.

Reasons capacity is not reached in practice

The gap between the theorem and a working link has several distinct sources, and separating them matters when diagnosing a system.

Finite block length. The theorem’s guarantee is asymptotic. At short block lengths the achievable rate at a fixed error target falls below capacity by a margin that grows as the block shrinks, with the leading term proportional to the square root of the channel dispersion divided by the block length.

Constellation and input constraints. The capacity-achieving input distribution for a Gaussian channel is Gaussian, but practical modulators use finite constellations with equiprobable points. The resulting constrained capacity is lower, and the loss is not a fixed amount: it depends on the constellation order and on the operating points of the constellation relative to the noise.

Implementation loss. Soft-decision decoding, synchronization, channel estimation error, and imperfect equalization all consume margin. These are not theoretical limits but they are unavoidable, and a link budget usually allocates a fixed fraction of decibels to them.

Mismatched decoding. If the decoder’s metric does not match the true channel, the achievable rate is bounded by the mismatched capacity, which can be strictly below the true capacity even when the code is capable of more. The relevant generalization is the generalized mutual information, and its value depends on the decoding metric rather than on the channel alone.

The practical significance of the capacity formula is therefore as a reference point: it bounds what any scheme can do, it explains which resource (power or bandwidth) is the binding constraint, and it identifies which losses are fundamental. It is not a target that a real system can be tuned to hit.

Where the definitions become delicate

Several edge cases break naive use of the formulas.

Nonzero output entropy with zero capacity. The binary symmetric channel at $\epsilon = 1/2$ produces an output that is uniform and therefore carries a full bit of entropy, yet its capacity is zero because the output is independent of the input. Entropy of the output and information about the input are different quantities, and the channel coding theorem bounds only the second.

Continuous inputs without a constraint. Without a power or support constraint, differential entropy is unbounded above and capacity is infinite. The constraint is part of the channel model, not an optional refinement.

Feedback. Feedback cannot increase the capacity of a memoryless channel, a result that surprises people who expect retransmission to help. It can simplify coding and reduce latency, and it does increase capacity for channels with memory, but for the memoryless case the bound is unchanged.

Non-stationary channels. Capacity is defined for a fixed channel law. If the channel varies, the relevant quantity is the ergodic capacity, an average over channel states, and the outage capacity for the fraction of time the rate is not supported. The two differ, and quoting one when the other is meant is a common error in link budgets.

The maximum in the definition is over a single input distribution, and it presupposes that the sender knows the channel law. When it does not, the achievable rate is governed by the compound or arbitrarily varying channel model, and the answer can be strictly lower than the capacity computed under the true law.