Capacity and Shannon's Theorem

The previous chapter, Compression in Practice, ended on a comparison. A binary source that emits a 1 with probability 0.1 compresses to $h(0.1) = 0.4690$ bits per letter, and a binary symmetric channel that flips each bit with probability 0.1 was said to carry $1 - h(0.1) = 0.5310$ bits per use with an error probability as small as desired. Since $0.4690 < 0.5310$, the source can cross that channel at one use per letter. The first number was earned in Source Coding and Prefix Codes, and this chapter earns the second.

Two earlier chapters supply the tools. Channels, Signals and Likelihoods built the binary symmetric channel $\text{BSC}(p)$, the binary erasure channel $\text{BEC}(\varepsilon)$ and the Z-channel $\text{Z}(p)$ in Three Discrete Channels, and the Gaussian channel in The Gaussian Channel and BPSK. Information and Entropy supplied the mutual information $I(X;Y) = H(Y) - H(Y \mid X)$, the number of bits one channel use conveys about its input, and its section Mutual Information of the Binary Symmetric Channel showed that a uniform input conveys the most over that channel.

The chapter counts noise patterns to see where $1 - h(p)$ comes from, computes capacity for the binary symmetric, erasure and Gaussian channels, and follows the trade of bandwidth against power to the Shannon limit of $-1.59$ dB. Typical sequences, random coding and Fano's inequality then prove the theorem in both directions.

Every number in the chapter is recomputed by ch07_capacity_and_shannons_theorem.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch07_charts.py in the same folder.

01.Counting Noise Patterns

Send a block of $n = 1000$ bits through $\text{BSC}(0.1)$. Each bit flips independently with probability 0.1, so about 100 bits flip, as the binomial count of Counting Errors with the Binomial Distribution predicts, but which 100 is unknown. There are $\binom{1000}{100}$ ways to choose them, whose base-2 logarithm is 464.42, and a receiver that undoes the noise must in effect learn which of these patterns occurred. Table 1 repeats the count for three block lengths.

Per symbol, the count climbs toward $h(0.1) = 0.4690$ and never passes it. To see why, write $k = pn$ and take the single term of the binomial expansion for that $k$. Every term of the expansion is positive and the terms add to $(p + (1 - p))^n = 1$, so

$$\binom{n}{pn} p^{pn} (1 - p)^{(1 - p)n} \le 1 .$$

The power of $p$ and $1 - p$ is $2^{pn \log_2 p + (1 - p)n \log_2 (1 - p)} = 2^{-n h(p)}$, so the inequality says $\binom{n}{pn} \le 2^{n h(p)}$. The shortfall grows far more slowly than $n$, so per symbol it vanishes. Typical Sequences shows that the patterns the noise is likely to produce, of any weight, number about $2^{n h(p)}$ as well.

Now turn the count around. A code for this channel is a list of $M$ codewords, each a string of $n$ bits. When codeword $c$ is sent, the received word lies, with high probability, in a cloud of about $2^{n h(p)}$ words around $c$, one for each likely noise pattern. For the receiver to name the codeword without confusion, the clouds of different codewords must not overlap, as Figure 1 draws. There are only $2^n$ binary words of length $n$ to share, so

For $n = 1000$ and $p = 0.1$ this is $2^{1000}/2^{469} = 2^{531}$, so at most 531 bits of message fit in 1000 uses, or $1 - h(0.1) = 0.5310$ bits per use. The argument is a heuristic, since clouds could overlap a little, and Fano's Inequality and the Converse turns it into a proof. The surprise, proved in The Random Coding Argument, is that the bound can be reached.

Figure 2 names the pieces of the argument. A message $W$ is one of $M$ equally likely values. The encoder maps it to a codeword $X^n = (X_1, \dots, X_n)$, the channel is used $n$ times and delivers $Y^n = (Y_1, \dots, Y_n)$, and the decoder forms an estimate $\hat W$ from $Y^n$. The rate is

and the error probability $P_e = P(\hat W \ne W)$ is averaged over the $M$ messages, or replaced by its maximum over messages when the worst case matters. The source of the previous chapter, at 0.4690 bits per letter, needs only $0.4690/0.5310 = 0.8832$ uses of this channel per letter.

02.Channel Capacity

The general definition replaces the count with the mutual information of Information and Entropy.

The definition is a formula about one use of the channel, with no codes in it. Its operational counterpart is the achievable rate. A rate $R$ is achievable if, for every $\epsilon > 0$ and every large enough $n$, some code of length $n$ with at least $2^{nR}$ codewords has error probability below $\epsilon$. The coding theorem says the largest achievable rate is $C$.

Shannon stated the theorem in 1948 [1] and treated the Gaussian channel geometrically the following year [2]. Feinstein gave an early rigorous proof of the direct half [3], and Gallager derived bounds on how fast the error falls with $n$ [4]. The proofs in this chapter follow the typical-sequence route of Cover and Thomas [5], specialized to the binary symmetric channel so that every step can be checked with numbers.

03.The Binary Symmetric Channel

Start with a channel whose capacity should come out close to one half, $\text{BSC}(0.11)$, and with an input that is not uniform.

The example generalizes at once. With $P(X = 1) = q$, the probability of a received 1 is

and $H(Y \mid X) = q\,h(p) + (1 - q)\,h(p) = h(p)$, because each input meets the same flip probability. The mutual information is therefore $I(X;Y) = h(r) - h(p)$. Only the first term depends on the input, and the binary entropy function is at most 1, reached only at $r = \frac12$. Setting $q = \frac12$ gives $r = \frac12(1 - p) + \frac12 p = \frac12$, so the uniform input reaches the maximum, as Information and Entropy found. Hence

For $p = 0.11$, $h(0.11) = 0.4999$ and $C = 0.5001$, and the flip probability whose capacity is exactly one half is 0.110028. For $p = 0.1$ the capacity is the 0.5310 promised at the start. Table 2 lists the mutual information for several inputs, beside the same quantity for the erasure channel of the next section.

Both channels peak at $q = \frac12$. Figure 3 plots each capacity against the noise parameter. The binary symmetric curve is symmetric about $p = \frac12$, because a receiver facing a channel that flips almost every bit simply inverts what it sees, and at $p = \frac12$ the output is independent of the input and the capacity is zero.

04.The Binary Erasure Channel

The erasure channel $\text{BEC}(\varepsilon)$ delivers each bit intact with probability $1 - \varepsilon$ and otherwise delivers an erasure mark, written $?$, which tells the receiver that the bit was lost but not what it was. Here the easier route to the mutual information runs through the input, $I(X;Y) = H(X) - H(X \mid Y)$, the other form from Mutual Information.

With $P(X = 1) = q$, the input entropy is $H(X) = h(q)$. An output of 0 or 1 leaves no uncertainty. An output of $?$, which happens with probability $\varepsilon$ whatever was sent, says nothing about the input, which keeps its entropy $h(q)$. Averaging over the outputs gives $H(X \mid Y) = \varepsilon\, h(q)$, and

$$I(X;Y) = h(q) - \varepsilon\, h(q) = (1 - \varepsilon)\, h(q) .$$

The largest value of $h(q)$ is 1, at $q = \frac12$, so

The last column of Table 2 is $0.5\, h(q)$, for instance $0.5 \times 0.4690 = 0.2345$ at $q = 0.1$. A fraction $\varepsilon$ of the uses are lost, and the theorem promises that the rest can be used in full, as if the transmitter had known in advance which uses would be erased.

Figure 3 shows that $\text{BSC}(0.11)$ and $\text{BEC}(0.5)$ have the same capacity, although the first damages 11 bits in a hundred and the second 50. Each flipped bit costs $h(0.11)/0.11 = 4.54$ bits of capacity against exactly 1 for each erased bit, because a flip must also be located.

05.The Gaussian Channel

The Gaussian channel of The Gaussian Channel and BPSK adds to each real input $X$ an independent Gaussian noise $Z$ with mean 0 and variance $N$, so $Y = X + Z$. Inputs spaced far enough apart could always be told apart, so the input power is limited to $E[X^2] \le P$, and the ratio $P/N$ is the signal-to-noise ratio per real dimension.

The output is continuous, so the entropies become the differential entropies of The Rate–Distortion Trade in the previous chapter, $h(X) = -\int f(x) \log_2 f(x)\, dx$ for a density $f$. With a capital letter inside, $h(X)$ is a differential entropy, while $h(p)$ stays the binary entropy function. Table 3 compares three densities of variance 1.

The three values are $\log_2 (2\sqrt3)$, $\log_2(\sqrt2\, e)$ and $\frac12 \log_2(2\pi e)$. The Gaussian leads the uniform density by $\frac12 \log_2(\pi e/6) = 0.2546$ bits, the gap that separated entropy-coded quantizer indices from the rate-distortion bound in The Rate–Distortion Trade, and the lemma says no density of the same variance does better.

Proof. Let $f$ be any density with mean $\mu$ and variance $\sigma^2$, and let $\phi$ be the Gaussian density with the same mean and variance. Gibbs' inequality, from Relative Entropy and Gibbs' Inequality, holds for densities as it does for probability lists, so $\int f \log_2 (f/\phi)\, dx \ge 0$, which rearranges to

$$h(f) = -\int f \log_2 f \, dx \le -\int f \log_2 \phi \, dx .$$

The logarithm of the Gaussian density is a quadratic,

$$-\log_2 \phi(x) = \frac12 \log_2 (2\pi\sigma^2) + \frac{(x - \mu)^2}{2\sigma^2} \log_2 e .$$

Averaging it under $f$ uses only the variance of $f$, since $\int f (x - \mu)^2 dx = \sigma^2$, so the right side equals $\frac12 \log_2 (2\pi\sigma^2) + \frac12 \log_2 e = \frac12 \log_2 (2\pi e \sigma^2)$ for every such $f$. For $f = \phi$ the inequality holds with equality, so this value is $h(\phi)$, and $h(f) \le h(\phi)$. $\blacksquare$

The capacity follows in three steps. First, $I(X;Y) = h(Y) - h(Y \mid X)$. Given $X = x$, the output is $x + Z$, a shifted copy of the noise, and shifting a density does not change its differential entropy, so $h(Y \mid X) = h(Z) = \frac12 \log_2 (2\pi e N)$. Second, $X$ and $Z$ are independent, so the variance of $Y$ is at most $P + N$, and the lemma gives $h(Y) \le \frac12 \log_2 (2\pi e (P + N))$. Third, a Gaussian input with variance $P$ makes $Y$ Gaussian with variance exactly $P + N$ and reaches that bound. Subtracting,

A signal-to-noise ratio of 3 buys 1 bit per use and 15 buys 2, which are 4.77 and 11.76 dB.

Figure 4 gives Shannon's geometric reading of the formula [2]. Over $n$ uses the received vector has squared length close to $n(P + N)$, by the law of large numbers, so it lies near a sphere of radius $\sqrt{n(P + N)}$. The noise moves each codeword to a point near a sphere of radius $\sqrt{nN}$ around it. In $n$ dimensions volume grows as the $n$th power of the radius, so at most $\left(\sqrt{(P + N)/N}\right)^n = (1 + P/N)^{n/2}$ noise spheres fit without overlapping, and the rate is at most $\frac12 \log_2 (1 + P/N)$. It is the noise-cloud count of Equation 1 again, with volume in place of number.

BPSK Against the Gaussian Input

The capacity formula assumes a Gaussian input, which can take any real value. BPSK, from The Gaussian Channel and BPSK, sends only $+a$ or $-a$ with $a^2 = P$. Scale the amplitude to $a = 1$, so the noise variance becomes $\sigma^2 = N/P$, the reciprocal of the signal-to-noise ratio. With equally likely inputs the output density is $p(y) = \frac12 p(y \mid +1) + \frac12 p(y \mid -1)$, and the mutual information is the average of $\log_2 \bigl(p(y \mid x)/p(y)\bigr)$. For $x = +1$,

$$\frac{p(y \mid +1)}{p(y)} = \frac{2}{1 + p(y \mid -1)/p(y \mid +1)} = \frac{2}{1 + e^{-2y/\sigma^2}} ,$$

because the ratio of the two Gaussian densities is $\exp\bigl(-\bigl((y + 1)^2 - (y - 1)^2\bigr)/(2\sigma^2)\bigr) = e^{-2y/\sigma^2}$. Its exponent is minus the log-likelihood ratio $L = 2y/\sigma^2$ of Likelihoods and Log-Likelihood Ratios. Taking $\log_2$ and averaging over $Y$ given $X = +1$, and noting that $x = -1$ gives the same average by symmetry,

The expectation has no closed form, and the companion script evaluates it by Simpson's rule. A receiver that keeps only the sign of $Y$ makes hard decisions, in the language of Hard and Soft Decisions, and turns the channel into a binary symmetric channel with flip probability $Q(1/\sigma) = Q\bigl(\sqrt{P/N}\bigr)$, so

Table 4 and Figure 5 show two regimes. At low signal-to-noise ratio, BPSK with soft decisions loses almost nothing to the Gaussian input, 0.0687 against 0.0688 at $-10$ dB, while hard decisions keep only about two thirds. At high signal-to-noise ratio, two input levels can never carry more than 1 bit, and BPSK saturates while the Gaussian input keeps climbing. Signal sets with many levels exist to follow the Gaussian curve upward.

The low-ratio loss of hard decisions has a clean limit. Write $s = P/N$. For small $s$, the Gaussian capacity is $\frac12 \log_2(1 + s) \approx s/(2 \ln 2)$, and soft BPSK matches it. For hard decisions the flip probability is $Q(\sqrt s) \approx \frac12 - \sqrt{s/(2\pi)}$, and near one half the binary entropy function behaves as $h(\frac12 - \delta) \approx 1 - 2\delta^2/\ln 2$, so $C_{\text{hard}} \approx 2 \cdot \frac{s}{2\pi} / \ln 2 = s/(\pi \ln 2)$. The ratio is $\pi/2 = 1.571$, and at $-10$ dB the table already gives $0.0687/0.0449 = 1.53$. To make up the difference, a hard-decision receiver needs $\pi/2$ times the power, or 1.96 dB.

06.Bandwidth and Power

Real links are specified by bandwidth $B$ in hertz and signal power $S$ in watts, not by uses of a channel. A signal confined to bandwidth $B$ is fixed by $2B$ real samples per second, the Nyquist rate, so the band offers $2B$ channel uses per second. If the noise has power spectral density $N_0/2$ per real dimension, its power in the band is $N = N_0 B$. Each sample then carries energy $S/(2B)$ against noise variance $N_0/2$, a signal-to-noise ratio of $S/(N_0 B) = S/N$ per sample. Multiplying the capacity per sample by $2B$ samples per second gives the Shannon–Hartley formula.

Power sits inside the logarithm, so doubling it adds at most one bit per second per hertz, while bandwidth multiplies the logarithm but also admits more noise. The worked example A 20 MHz Link puts numbers on the trade. At the other extreme, hold $S/N_0 = 10^6$ Hz fixed and widen the band. The capacity is 0.3459 Mbit/s at $B = 10^5$ Hz, 1.0000 at $10^6$, 1.3750 at $10^7$ and 1.4355 at $10^8$, and it never passes a ceiling. Since $\log_2(1 + x) = \ln(1 + x)/\ln 2 \approx x \log_2 e$ for small $x$,

$$B \log_2 \left( 1 + \frac{S}{N_0 B} \right) \longrightarrow \frac{S}{N_0} \log_2 e \quad \text{as } B \to \infty ,$$

which here is 1.4427 Mbit/s, so unlimited bandwidth buys only a bounded rate.

The trade is usually drawn in terms of the spectral efficiency $\eta = R_b/B$, the bit rate per hertz, and the energy per bit $E_b$ of Energy per Bit and the Decibel. A rate $R_b$ at power $S$ spends $E_b = S/R_b$ joules per bit, so $S/N = E_b R_b/(N_0 B) = \eta\, E_b/N_0$. Reliable transmission needs $R_b \le C$, that is $\eta \le \log_2 (1 + \eta\, E_b/N_0)$, and solving for the energy per bit,

Table 5 and Figure 6 trace the boundary. Spectrally efficient links pay steeply in energy, 15.03 dB at 8 bit/s/Hz, while slow links approach a floor near $-1.59$ dB. Uncoded BPSK sends one bit per real sample, so $\eta = 2$ in this counting, and Energy per Bit and the Decibel found that it needs 9.59 dB for a bit error probability of $10^{-5}$. The bound at $\eta = 2$ is 1.76 dB, so 7.83 dB separates uncoded BPSK from what the theorem allows at the same spectral efficiency, and that gap is what the codes of the rest of this book compete for.

07.The Shannon Limit

The floor in Table 5 is a limit, and it can be taken one step at a time. Write $2^\eta = e^{\eta \ln 2}$ and expand the exponential as a power series,

$$2^\eta = 1 + \eta \ln 2 + \frac{(\eta \ln 2)^2}{2!} + \frac{(\eta \ln 2)^3}{3!} + \cdots .$$

Subtracting 1 removes the constant term, and dividing by $\eta$ lowers every remaining power by one,

$$\frac{2^\eta - 1}{\eta} = \ln 2 + \eta\, \frac{(\ln 2)^2}{2} + \eta^2\, \frac{(\ln 2)^3}{6} + \cdots .$$

As $\eta \to 0$ every term but the first vanishes, and the boundary tends to $\ln 2 = 0.693147$. Every coefficient is positive, so the boundary falls steadily with $\eta$ and never goes below $\ln 2$. The slope of the series at zero is $(\ln 2)^2/2 = 0.2402$, so at $\eta = 0.1$ the first two terms give $0.6931 + 0.1 \times 0.2402 = 0.7172$, against the exact 0.7177. Converting to decibels takes one logarithm, $\log_{10}(0.693147) = -0.15917$, so

The wideband limit reaches the same number by another road. With unlimited bandwidth the capacity is $(S/N_0) \log_2 e$, and a rate $R_b$ at that capacity spends $E_b = S/R_b = N_0/\log_2 e = N_0 \ln 2$ per bit. Uncoded BPSK at $10^{-5}$ sits 11.18 dB above the Shannon limit, 7.83 dB for having no code and the rest for running at $\eta = 2$.

A code of rate $R$ bits per real dimension has $\eta = 2R$, and with BPSK as the signal set the boundary comes from Equation 6 and Equation 7 instead of the Gaussian capacity. A channel use spends energy $P$ to carry $R$ bits, so $E_b = P/R$, and with $N_0 = 2N$, $E_b/N_0 = (P/N)/(2R)$. The least signal-to-noise ratio whose capacity reaches $R$ fixes the least $E_b/N_0$, collected in Table 6.

These are the targets a code designer quotes. A rate one half code with BPSK cannot work below 0.19 dB with soft decisions, or 1.77 dB with hard ones. As the rate falls, soft BPSK approaches the Shannon limit, while hard decisions settle about 1.96 dB above it, the $\pi/2$ penalty found above.

08.Typical Sequences

The noise-cloud count needs a precise statement of which noise patterns are likely. Take the source of the previous chapter, which emits a 1 with probability $p = 0.1$, and look at blocks of $n = 20$ symbols, where everything can be counted exactly. A block with $k$ ones has probability $p^k (1 - p)^{20 - k}$, and there are $\binom{20}{k}$ such blocks. Table 7 lists the first few weights.

The most likely block is all zeros, yet the most likely weight is $k = 2$, because its 190 blocks outweigh the single block of zeros. The last column, the surprise per symbol, equals the entropy $h(0.1) = 0.4690$ exactly when $k/n = p$. In general,

$$-\frac1n \log_2 \bigl( p^k (1 - p)^{n - k} \bigr) = -\frac{k}{n} \log_2 p - \left( 1 - \frac{k}{n} \right) \log_2 (1 - p) = h(p) + \left( \frac{k}{n} - p \right) \log_2 \frac{1 - p}{p} ,$$

where the last step adds and subtracts $h(p) = -p \log_2 p - (1 - p) \log_2 (1 - p)$. With $(1 - p)/p = 9$ and $\log_2 9 = 3.1699$, each extra one raises the surprise per symbol by $3.1699/20 = 0.1585$ bits.

For the binary source, the identity above turns the condition into $|k/n - p| \le \delta/\log_2 9$. A window of 0.05 in the fraction of ones is $\delta = 0.05 \log_2 9 = 0.1585$. At $n = 20$ the typical weights are $k = 1$, 2 and 3, so the typical set holds $20 + 190 + 1140 = 1350$ blocks, about $2^{10.399}$, with total probability 0.74547. Their surprises lie between $h - \delta = 0.3105$ and $h + \delta = 0.6275$ bits per symbol, so each has probability between $2^{-20 \times 0.6275}$ and $2^{-20 \times 0.3105}$, and their number lies between $2^{20(h - \delta)} = 74.03$ and $2^{20(h + \delta)} = 5996.2$, around $2^{20 h} = 666.25$. Table 8 follows the typical set as the block grows.

The probability rushes toward 1 while the size stays between the bounds, and the asymptotic equipartition property says this always happens.

Proof. The probability of a block of independent symbols is a product, so its surprise per symbol is an average, $-\frac1n \log_2 p(X_1, \dots, X_n) = \frac1n \sum_i \bigl(-\log_2 p(X_i)\bigr)$, of independent terms whose mean is $H$. The weak law of large numbers, from The Law of Large Numbers, says such an average falls within $\delta$ of its mean with probability tending to 1, which is $P(T) \to 1$. For the upper bound on the size, every typical block has probability at least $2^{-n(H + \delta)}$, and the probabilities of all blocks add to at most 1, so there are at most $2^{n(H + \delta)}$ of them. For the lower bound, every typical block has probability at most $2^{-n(H - \delta)}$, and once $P(T) \ge 1 - \epsilon$ there must be at least $(1 - \epsilon)\, 2^{n(H - \delta)}$ of them to hold that much probability. $\blacksquare$

Chebyshev's inequality makes the first step quantitative, though loosely. The fraction of ones has variance $p(1 - p)/n = 0.09/n$, so the probability of a fraction more than 0.05 from $p$ is at most $0.09/(0.0025\, n) = 36/n$, which is 0.036 at $n = 1000$. The exact value there is $2.8 \times 10^{-7}$, because the true probability falls exponentially in $n$, as the Chernoff Bound of Probability for Coding shows. Figure 7 plots $P(T)$ for two windows. A narrower window pins the size closer to $2^{nH}$ but needs longer blocks before it holds most of the probability.

Numbering the typical blocks takes about $n(H + \delta)$ bits, which recovers the compression rate of Source Coding and Prefix Codes. The noise pattern of $\text{BSC}(p)$ is a block from exactly this source, so it is very likely one of about $2^{n h(p)}$ typical patterns, the cloud size of Equation 1.

09.The Random Coding Argument

The bound of Equation 1 says no code beats $1 - h(p)$. Shannon reached it without building a code. He chose the codebook at random and showed that the error averaged over all codebooks is small, so some codebook does at least as well.

Walk through it with numbers. Take $n = 1000$ uses of $\text{BSC}(0.1)$ and rate $R = 0.4$, below the capacity 0.5310. The codebook has $M = 2^{400} \approx 2.58 \times 10^{120}$ codewords, and every bit of every codeword is chosen by a fair coin flip, independently. The decoder uses the Hamming distance, the number of positions in which two words differ. Given the received word $y$, it lists the codewords within distance $r = 140$ of $y$. If there is exactly one, it outputs that codeword's message, and otherwise it declares an error. It is not the best decoder, but whatever it achieves the best decoder achieves too.

Suppose message $w$ is sent. Two things can go wrong. The first is that the noise flips more than 140 bits, so the sent codeword is not on the list. The number of flips is binomial with $n = 1000$ and $p = 0.1$, and the exact tail is $P(K > 140) = 2.424 \times 10^{-5}$. The second is that some other codeword also lies within 140 of $y$. Here the randomness of the code does the work. Each other codeword was drawn independently of $w$'s codeword and of the noise, so it is uniform over all $2^{1000}$ words whatever $y$ is, and the chance that it lands within 140 of $y$ is the size of that ball divided by $2^{1000}$,

$$\frac{1}{2^{1000}} \sum_{k=0}^{140} \binom{1000}{k} = 2^{-420.29} .$$

There are fewer than $2^{400}$ other codewords, and by the union bound of The Union Bound the chance that any of them intrudes is at most $2^{400} \times 2^{-420.29} = 2^{-20.29}$, about $7.8 \times 10^{-7}$. Adding the two failures, the error probability averaged over messages and codebooks is at most $2.424 \times 10^{-5} + 7.8 \times 10^{-7} = 2.50 \times 10^{-5}$.

The radius balances the two failures. At $r = 125$ the tail grows to $P(K > 125) = 0.00453$ while the intruder term shrinks to $2^{-60.93}$, and minimized over every radius the bound is $2.1 \times 10^{-5}$. Figure 8 repeats the calculation for three rates and many block lengths.

To pass from one example to every rate below capacity, the ball needs a bound that shows its exponent.

Proof. Expand $1 = (\rho + (1 - \rho))^n$ and keep only the terms with $k \le \rho n$, which gives $1 \ge \sum_{k \le \rho n} \binom{n}{k} \rho^k (1 - \rho)^{n - k}$. Write each term's probability factor as $(1 - \rho)^n \bigl(\rho/(1 - \rho)\bigr)^k$. Because $\rho \le \frac12$, the ratio $\rho/(1 - \rho)$ is at most 1, so its power can only shrink as $k$ grows, and for $k \le \rho n$ it is at least its value at $k = \rho n$. Every kept term is therefore at least $\binom{n}{k} \rho^{\rho n} (1 - \rho)^{(1 - \rho) n} = \binom{n}{k} 2^{-n h(\rho)}$. Summing and multiplying through by $2^{n h(\rho)}$ gives the lemma. $\blacksquare$

For the example, $\rho = 0.14$ gives $1 - h(0.14) = 0.4158$, so the lemma bounds the intruder chance by $2^{-415.76}$ against the exact $2^{-420.29}$, and the union term by $2^{-15.76}$, about $1.8 \times 10^{-5}$. The lemma loses a few bits and keeps the exponent, which is all the general argument needs.

Proof. Since $h$ is continuous and increasing on $[0, \frac12]$, there is a $\rho$ with $p < \rho < \frac12$ and $R < 1 - h(\rho)$. Decode with radius $\rho n$. The flips exceed $\rho n$ with probability tending to zero by the weak law of large numbers, since their average fraction is $p < \rho$, and the Chernoff bound of Chernoff [6] shows the fall is exponential. By the lemma and the union bound, an intruder appears with probability at most $2^{nR} \, 2^{n h(\rho)}/2^n = 2^{-n(1 - h(\rho) - R)}$, and the exponent is negative. Both terms vanish. $\blacksquare$

Three refinements complete the direct half. A codebook average below $\epsilon$ means some codebook has average error below $\epsilon$. At most half of its codewords can have error above $2\epsilon$, so discarding the worse half leaves rate $R - 1/n$ with every message's error at most $2\epsilon$, which in the example is rate 0.399 and $5.0 \times 10^{-5}$. And a general discrete memoryless channel needs only a new decoder. The codewords are drawn from the input distribution that achieves capacity, and the decoder picks the unique codeword jointly typical with $y$, meaning that the pair looks like a typical input and output of the channel. A wrong codeword, independent of $y$, passes with probability about $2^{-n I(X;Y)}$, so the union over $2^{nR}$ codewords vanishes when $R < I(X;Y)$ [5]. Gaussian codebooks do the same for the Gaussian channel [2].

10.Fano's Inequality and the Converse

The converse needs a link between error and entropy. If a decoder rarely errs, its input must leave little uncertainty about the message, and Fano's inequality [7] makes that precise.

Take numbers first. A message takes one of $M = 4$ values, and a decoder guesses it from $Y$ with error probability 0.1. Fano's inequality says the remaining uncertainty is at most $h(0.1) + 0.1 \log_2 3 = 0.4690 + 0.1585 = 0.6275$ bits, out of the 2 bits the message held. The first term pays for not knowing whether the guess is right, and the second, when it is wrong, for not knowing which of the other 3 values is correct.

Proof. Let $E$ be 1 when $\hat W \ne W$ and 0 otherwise. Expand the uncertainty of the pair $(E, W)$ given $Y$ by The chain rule from Information and Entropy in two orders. In the first, $H(E, W \mid Y) = H(W \mid Y) + H(E \mid W, Y)$, and the last term is zero, because $W$ and $Y$ fix both $W$ and $\hat W$, hence $E$. In the second, $H(E, W \mid Y) = H(E \mid Y) + H(W \mid E, Y)$. By the theorem Conditioning reduces entropy, $H(E \mid Y) \le H(E) = h(P_e)$. The term $H(W \mid E, Y)$ averages two cases. When $E = 0$, $W = \hat W$ is known and the uncertainty is zero. When $E = 1$, which has probability $P_e$, $W$ is one of the $M - 1$ values other than $\hat W$, and How Large Entropy Can Be caps its uncertainty at $\log_2 (M - 1)$. Equating the two expansions gives the inequality. $\blacksquare$

Now the converse. Let $W$ be uniform over $M = 2^{nR}$ messages, so $H(W) = nR$. Split it into what the output reveals and what it leaves,

$$nR = H(W) = H(W \mid Y^n) + I(W; Y^n) .$$

Fano bounds the first part. Since $h(P_e) \le 1$ and $\log_2(M - 1) < nR$, $H(W \mid Y^n) \le 1 + P_e\, nR$. For the second part, the encoder fixes $X^n$ once $W$ is known, and the channel output depends on $W$ only through $X^n$, so $H(Y^n \mid W) = H(Y^n \mid X^n)$ and $I(W;Y^n) = I(X^n;Y^n)$. The chain rule and the memoryless channel give $H(Y^n \mid X^n) = \sum_i H(Y_i \mid X_i)$, while the chain rule and Conditioning reduces entropy give $H(Y^n) \le \sum_i H(Y_i)$. Together,

$$I(X^n;Y^n) = H(Y^n) - \sum_{i=1}^{n} H(Y_i \mid X_i) \le \sum_{i=1}^{n} \bigl( H(Y_i) - H(Y_i \mid X_i) \bigr) = \sum_{i=1}^{n} I(X_i;Y_i) \le nC .$$

Combining, $nR \le 1 + P_e\, nR + nC$, and dividing by $nR$,

For $\text{BSC}(0.1)$ at rate 0.6, above the capacity 0.5310, the bound is 0.0983 at $n = 100$ and 0.1133 at $n = 1000$, approaching $1 - 0.5310/0.6 = 0.1150$. So no code of rate 0.6 and length at least 1000 has block error below 0.1133. This is the weak converse, which only keeps the error away from zero. The finite-length bounds of Polyanskiy, Poor and Verdú imply the stronger statement that above capacity the error probability of a discrete memoryless channel tends to 1 [8]. With $P_e \to 0$ the converse gives $R \le C$, the cloud count of Counting Noise Patterns made rigorous.

Sources over Channels

The opening comparison of the chapter can now be made exact. A source of independent letters with entropy $H$ bits per letter is to be sent over a channel of capacity $C$, using $\rho$ channel uses per letter.

Proof sketch. For the first half, compress blocks of $k$ letters to about $kH$ bits, as in Source Coding and Prefix Codes, and send them with a channel code of rate between $H/\rho$ and $C$. For the second half, Fano's inequality on a block of $k$ letters from an alphabet of size $A$, with the argument of the converse, gives $H \le \rho C + 1/k + P_e \log_2 A$, which forces $H \le \rho C$ as $k \to \infty$ and $P_e \to 0$. $\blacksquare$

Compression and protection can therefore be designed separately without loss, which is why this book treats source codes and channel codes in different Parts. For the source with $p = 0.1$ over $\text{BSC}(0.1)$, 0.8832 uses per letter is the least. Without exact reproduction the condition becomes $R(D) \le \rho C$, with $R(D)$ the rate-distortion function of The Rate–Distortion Trade [5], and the worked example Sending a Gaussian Source Without a Code meets that bound with no code at all.

11.What the Theorem Promises and What It Leaves Open

The theorem promises that codes exist at every rate below capacity with error probability as small as desired, and that a code chosen at random is good with high probability. It gives no way to find one. Four gaps separate the promise from a working system.

The first is construction. The random code of the walk-through is a table of $2^{400}$ codewords of 1000 bits, about $2.58 \times 10^{123}$ bits with no shorter description, and a practical code needs structure that generates its codewords from a short one.

The second is decoding. The radius decoder and the maximum-likelihood decoder both compare the received word with every codeword, $2.58 \times 10^{120}$ comparisons per block, so the structure must also be one a decoder can exploit.

The third is block length. The proof makes the error small by making $n$ large, and the curves of Figure 8 fall slowly near capacity. Long blocks mean delay, since a decoder waits for the whole block, and memory to hold it.

The fourth is the finite-length penalty, which says how far below capacity a code of a given length must stay. Polyanskiy, Poor and Verdú showed that the best rate at block length $n$ and block error $\epsilon$ is close to

where $Q^{-1}$ inverts the Q-function of The Gaussian and the Q-Function, and $V$ is the channel dispersion [8]. For the binary symmetric channel,

$$V = p(1 - p) \log_2^2 \frac{1 - p}{p} ,$$

which is the variance of the surprise $-\log_2 p(z)$ of one noise symbol. It is the same fluctuation that blurred the edges of the typical set. For $p = 0.1$, $V = 0.09 \times 3.1699^2 = 0.90436$ and $\sqrt V = 0.95098$, and with $Q^{-1}(10^{-3}) = 3.0902$ and $Q^{-1}(10^{-6}) = 4.7534$ the approximation gives Table 9.

At $n = 1000$ and $\epsilon = 10^{-3}$, the best code reaches only 0.825 of capacity, and a block of 100 symbols reaches less than half. The full expansion adds a term near $\log_2 n/(2n)$, 0.0050 at $n = 1000$, small beside the square-root term. Figure 9 plots the approach to capacity. The rest of this book is the search for codes with enough structure to be built and decoded, and good enough to sit near these curves.

12.Looking Ahead

A random code is good on average and can still be bad in detail. In the worked example A Small Random Code Decoded Exactly, 16 random codewords of 12 bits include two pairs that differ in only 2 positions, and the code barely beats sending each of its 4 message bits three times. The weakness is the distance between codewords, which a random choice leaves to chance.

The next chapter, Distance, Detection and Correction, makes distance the design target. It defines the Hamming distance between words and the weight of a word, and shows that a code whose codewords all differ in at least $d$ positions detects any $d - 1$ errors and corrects any $t = \lfloor (d - 1)/2 \rfloor$, the counting behind Hamming's first codes [9]. The theorem of this chapter proves that good codes exist but builds none, and minimum distance is the first handle by which a code can be built and checked. MacKay [10] and Cover and Thomas [5] give further proofs of the coding theorem, and Lin and Costello [11] begin the constructions there.

13.Worked Examples

14.Exercises

References

1. [1]Shannon, Claude E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal, 27(3), pp. 379–423. The paper concludes in the October issue, volume 27, number 4, pages 623 to 656. doi:10.1002/j.1538-7305.1948.tb01338.x
2. [2]Shannon, Claude E. (1949). “Communication in the Presence of Noise.” Proceedings of the IRE, 37(1), pp. 10–21. doi:10.1109/JRPROC.1949.232969
3. [3]Feinstein, Amiel (1954). “A New Basic Theorem of Information Theory.” Transactions of the IRE Professional Group on Information Theory, 4(4), pp. 2–22. doi:10.1109/TIT.1954.1057459
4. [4]Gallager, Robert G. (1965). “A Simple Derivation of the Coding Theorem and Some Applications.” IEEE Transactions on Information Theory, 11(1), pp. 3–18. doi:10.1109/TIT.1965.1053730
5. [5]Cover, Thomas M. and Thomas, Joy A. (2006). “Elements of Information Theory.” 2nd edition. Wiley-Interscience. doi:10.1002/047174882X
6. [6]Chernoff, Herman (1952). “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations.” The Annals of Mathematical Statistics, 23(4), pp. 493–507. doi:10.1214/aoms/1177729330
7. [7]Fano, Robert M. (1961). “Transmission of Information: A Statistical Theory of Communications.” M.I.T. Press. https://archive.org/details/transmissionofin0000fano
8. [8]Polyanskiy, Yury and Poor, H. Vincent and Verdú, Sergio (2010). “Channel Coding Rate in the Finite Blocklength Regime.” IEEE Transactions on Information Theory, 56(5), pp. 2307–2359. doi:10.1109/TIT.2010.2043769
9. [9]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
10. [10]MacKay, David J. C. (2003). “Information Theory, Inference, and Learning Algorithms.” Cambridge University Press. The author's site offers the whole book free to read on screen. https://www.inference.org.uk/itila/book.html
11. [11]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.