The Noisy Channel Limit

Sphere Packing in High Dimensions and the Speed Limit of All Communication

Communication engineers prior to 1948 treated thermal noise on a copper wire or radio link as a permanent toll on accuracy. Every physical channel—whether an undersea cable, a microwave relay tower, or a magnetic tape—is agitated by the random thermal motion of electrons. Whenever a transmitter sends a pulse down the line, Gaussian thermal noise adds random voltage spikes that flip occasional zeros into ones. Throughout the 1930s and 1940s, engineering consensus held a grim view. If a system had a fixed signal power $S$ and a fixed thermal noise power $N$, there were only two ways to make the error rate arbitrarily small. An engineer had to either shout louder by increasing power, or repeat each symbol over and over, driving the net data transmission rate toward zero.

In the second half of his 1948 Bell System Technical Journal paper, Claude Shannon demolished that consensus with his noisy-channel coding theorem. Every noisy communication link, he showed, possesses a hard, intrinsic speed limit called the channel capacity $C$. Mathematically, $C$ equals the maximum mutual information between the channel input $X$ and output $Y$. For a continuous analog channel of bandwidth $B$ hertz disturbed by additive white Gaussian noise of power $N$ and constrained to average signal power $S$, Shannon derived the exact capacity in bits per second:

What shocked the engineering world was not that a maximum rate $C$ existed, but what happened below $C$. Suppose a transmitter sends information at any finite rate $R$ strictly less than the channel capacity $C$, even at ninety-nine percent of $C$. Shannon proved that an encoding scheme exists that drives the probability of decoding error at the receiver as close to zero as desired without slowing down the transmission rate.

How could a receiver eliminate errors completely across a noisy line without repeating every bit ten times? Shannon found the mechanism by translating waveform transmission into the geometry of high-dimensional Euclidean space. By the Nyquist-Shannon sampling theorem, a signal of bandwidth $B$ lasting $T$ seconds is completely determined by $n = 2BT$ discrete amplitude samples. Therefore, any transmitted block of duration $T$ is simply a single point in an $n$-dimensional geometric space. Its distance from the origin is proportional to $\sqrt{nS}$.

When thermal noise of average power $N$ strikes the signal during transit, the received point is knocked away from the transmitted point. In three dimensions, a random Gaussian nudge can vary wildly in radius. In a space of $n = 10{,}000$ dimensions, however, the law of large numbers hardens the noise cloud into a thin, sharp spherical shell of radius proportional to $\sqrt{nN}$. Decoding without error reduces to a pure geometry puzzle. How many non-overlapping noise spheres of radius $\sqrt{nN}$ can be packed inside a larger total-power sphere of radius $\sqrt{n(S + N)}$?

Dividing the $n$-dimensional volume of the large outer sphere by the volume of one small noise sphere yields $(1 + S/N)^{n/2} = 2^{BT \log_2(1 + S/N)}$. Taking the logarithm gives the exact capacity $C = B \log_2(1 + S/N)$. To prove that such non-overlapping codebooks actually exist, Shannon introduced the method of random coding. He generated a codebook completely at random and showed that the average error probability across all random codes vanishes exponentially as block length $n$ grows large. Because the average across all codes approaches zero, at least one concrete codebook in the ensemble must perform at least as well as the average.

While Shannon's 1948 proof showed that error-free codes existed without specifying how to construct them efficiently, his Bell Labs office mate Richard Hamming was simultaneously building the first constructive single-error-correcting block code. Shannon cited Hamming's $[7, 4]$ code right inside the 1948 paper. Forty-five years after Shannon proved via high-dimensional sphere packing that near-zero error rates were possible right up to channel capacity, the 1993 discovery of turbo codes and the revival of low-density parity-check codes brought real deep-space and cellular receivers within fractions of a decibel of the 1948 limit.