Channel Capacity and the Noisy Channel

Before 1948 the consensus was that transmitting over a noisy line meant accepting errors, and that reducing errors meant slowing down without limit. Shannon proved the opposite: there is a number \(C\), a property of the channel alone, such that for any rate below \(C\) you can drive the error probability arbitrarily close to zero, and for any rate above it you cannot. There is a cliff, not a slope.

Capacity

For a discrete memoryless channel with input \(X\), output \(Y\), and transition law \(p(y \mid x)\),

The maximisation is over input distributions, because the channel is given and the code designer's only freedom is how to use it. \(I(X;Y)\) measures how much the output tells you about the input; capacity is the best that can be arranged.

Two canonical cases anchor the intuition. The binary symmetric channel with crossover probability \(p\) has \(C = 1 - H_2(p)\) bits per use, where \(H_2\) is the binary entropy: at \(p = 0.1\), capacity is about 0.531 bits, so roughly half the raw bits are usable. The additive white Gaussian noise channel with signal power \(S\) and noise power \(N\) has \(C = \frac{1}{2}\log_2(1 + S/N)\) bits per use, the formula behind every link-budget calculation ever done.

The channel coding theorem then says: codes achieving any \(R < C\) with vanishing error exist, and no code with \(R > C\) has vanishing error. The proof of achievability is a random-coding argument that uses joint typicality, so the typical set is the shared machinery of both halves of Shannon's theory.

Note the structural symmetry with rate-distortion: capacity maximises mutual information over input distributions, \(R(D)\) minimises it over channels. Both are computed by the same alternating algorithm run in opposite directions.

The noisy-channel decomposition

The engineering theorem has an inferential twin. Suppose you observe \(y\) and want the \(x\) that produced it. Bayes gives

The decomposition is why statistical machine translation was built the way it was: a translation model \(p(\text{french} \mid \text{english})\) trained on parallel text, multiplied by a monolingual language model \(p(\text{english})\) trained on abundant target-side text (Brown et al., 1993, The Mathematics of Statistical Machine Translation, Computational Linguistics 19(2)). The same factorisation drove speech recognition and spelling correction for two decades. Its appeal is data economy: the two factors are estimated from different corpora, and the abundant one carries the fluency.

End-to-end neural sequence models modelled \(p(x \mid y)\) directly and won, which looked like the end of the noisy-channel era. It was not.

Where it resurfaced

The decomposition returned as a prompting and reranking strategy. Noisy-channel prompting scores a label \(c\) for input \(x\) by \(p(x \mid c)\), the probability the model assigns to the input given the label, rather than the direct \(p(c \mid x)\). On few-shot classification this is markedly more stable across prompt formats and example orderings, and better when the label distribution is skewed, because generating the long input conditioned on a short label is a harder task that the model cannot solve by pattern-matching the answer position (Min et al., 2022, Noisy Channel Language Model Prompting, arXiv:2108.04106, ACL 2022).

The same reversal is standard practice in reranking: score candidate outputs by a combination of \(p(y \mid x)\) and \(p(x \mid y)\), which penalises generic outputs that are probable regardless of input. Length-normalisation debates in beam search are, in effect, arguments about which factorisation is being approximated.

When it breaks

Capacity assumes a known channel and unbounded block length. Both fail routinely. Finite blocklength analysis shows a penalty proportional to \(\sqrt{n}\) that matters severely at short lengths, which is why 5G control channels look nothing like textbook capacity-achieving codes.

The noisy-channel decomposition in NLP has its own failure: it requires a calibrated \(p(x \mid c)\), and modern instruction-tuned models are trained to be good at \(p(c \mid x)\) specifically. Reversing the conditional asks the model to do something its post-training actively de-emphasised, so the technique works better on base models than on chat models, and its advantage has narrowed as instruction tuning improved. It remains the right tool when prompt-format sensitivity is the dominant error source. See prompt format sensitivity and mutual information and representations.