What the Shannon Limit Tells You at Finite Block Length — Epoche C1
On a binary symmetric channel that flips each transmitted bit with probability $0.11$, the Shannon capacity is almost exactly $0.5$ bits per channel use. A designer who wants a block error probability no worse than $10^{-3}$ using codewords of length $1000$ cannot achieve $0.5$; the best rate any code whatever can reach under those constraints is about $0.41$. That seventeen per cent shortfall is not slack left by imperfect engineering. It is a property of the channel and the block length, it is computable in closed form to good accuracy, and computing it is the subject of this essay. The earlier version of this argument claimed that the Shannon limit "rigorously defines the maximum achievable information rate for any given finite code length". That claim is false as stated, and correcting it is the point on which everything else here turns: capacity is the limit of the finite-length maxima, not one of them. What Capacity Is, and in What Units Two definitions are needed before the finite-length question can even be posed, and both must carry their units, because the earlier version mixed two conventions without saying so. A discrete memoryless channel is specified by an input alphabet $\mathcal{X}$, an output alphabet $\mathcal{Y}$, and transition probabilities $p(y \mid x)$, with the memoryless property that each use of the channel is statistically independent of the others given its input. The mutual information $I(X;Y)$ between the input and output measures how much observing $Y$ reduces uncertainty about $X$, in bits, and the capacity is its maximum over input distributions: $$C = \max_{p(x)} I(X;Y) = \max_{p(x)} \sum_{x \in \mathcal{X}, \, y \in \mathcal{Y}} p(x,y)\log_2 \frac{p(y \mid x)}{p(y)}.$$ The units are bits per channel use . Shannon (1948) proved that for any rate below $C$ there exist codes whose error probability can be made as small as one likes by taking the block length large enough, and that no rate above $C$ admits reliable communication; Cover and Thomas (2006) give the modern textbook statement of both halves. For the additive white Gaussian noise channel — one whose output is the input plus an independent Gaussian disturbance — the corresponding per-use capacity for a real-valued input of average power $P$ against noise of variance $\sigma^2$ is $\tfrac{1}{2}\log_2(1 + P/\sigma^2)$ bits per channel use. The familiar $C = B\log_2(1 + S/N)$ quoted in the earlier version is a different quantity: it is measured in bits per second , and it is obtained from the per-use expression by noting that a channel of bandwidth $B$ supports $2B$ real samples per second, so that $2B \times \tfrac12\log_2(1+S/N) = B\log_2(1+S/N)$. The two formulae are consistent, but they are not interchangeable, and finite-block-length statements are made in the per-use currency. The Geometric Picture, Done Properly The earlier version proposed thinking of codewords as points in an $N$-dimensional space surrounded by noise clouds, which is the right instinct, but it drew the wrong moral from it — that as $N$ grows one can maintain codeword density while increasing the minimum distance between codewords. Minimum distance is not the operative quantity, and the correct picture explains the finite-length penalty rather than obscuring it. Consider $n$ uses of the Gaussian channel. The noise added over those $n$ uses is a vector in $\mathbb{R}^n$ whose squared length is a sum of $n$ independent squared Gaussians, with mean $n\sigma^2$ and standard deviation proportional to $\sqrt{n}\,\sigma^2$. Its length therefore concentrates near $\sigma\sqrt{n}$ with a relative spread of order $1/\sqrt{n}$: as $n$ grows, the noise cloud is not a diffuse ball but a thin shell. This is sphere hardening. Received vectors, similarly, lie near a sphere of radius $\sqrt{n(P+\sigma^2)}$. Since the volume of an $n$-dimensional ball scales as its radius to the power $n$, the number of disjoint noise balls that fit inside the received-signal sphere is about $$M \approx \frac{\left(\sqrt{n(P+\sigma^2)}\right)^n}{\left(\sqrt{n\sigma^2}\right)^n} = \left(1 + \frac{P}{\sigma^2}\right)^{n/2},$$ so that $\frac{1}{n}\log_2 M = \tfrac{1}{2}\log_2(1 + P/\sigma^2)$, recovering the capacity formula. The exponent is $n/2$ because the ratio of radii is raised to the dimension $n$ and each radius is itself a square root. Now note where the finite-length loss enters. The packing argument is exact only if the noise shell has zero thickness. Its relative thickness is of order $1/\sqrt{n}$, so a margin proportional to $1/\sqrt{n}$ must be conceded to keep the error probability at the target. That is the geometric origin of the correction term derived analytically below, and it is why the correction goes as $1/\sqrt{n}$ rather than, say, $1/n$. Minimum distance plays no role in this account, and rightly so: the capacity-approaching code families discussed later have unremarkable minimum distances and work anyway, because reliability at rates near capacity depends on the typical behaviour of the noise rather than on the worst-case separation of codewords. The Quantity That Actually Exists at Finite Length The finite-length question must be posed with three parameters rather than one, and once it is posed properly the earlier version's error is visible. Write $M^*(n,\epsilon)$ for the largest number of distinct messages that can be sent using $n$ channel uses with block error probability at most $\epsilon$ under an optimal code and an optimal decoder, and define the corresponding maximal rate $R^*(n,\epsilon) = \frac{1}{n}\log_2 M^*(n,\epsilon)$ in bits per channel use. This is a well-defined quantity for every $n$ and $\epsilon$ — it is a maximum over a finite set of possible codes — and it is what a designer needs. Shannon's theorem is the statement that $R^*(n,\epsilon) \to C$ as $n \to \infty$ for every fixed $\epsilon$ in $(0,1)$. It says nothing about how fast. For any channel with non-zero dispersion, defined below, and any $\epsilon$ less