Channel capacity and random coding

A discrete memoryless channel has finite input and output alphabets and a transition probability W(y given x). Conditional on the input block, its output law factors into a product of one-use transitions. A block code maps one of M equiprobable messages to n input symbols and reconstructs a message from the output. Its rate is log₂ M divided by n. Average error averages over messages, while maximal error takes the worst message's conditional probability.

For this finite stationary memoryless model without input cost constraints, capacity is the maximum mutual information over input distributions. The channel law stays fixed during this maximization; changing the input law changes the output law and their joint distribution. Compactness of the finite simplex and continuity guarantee a maximum. A rate below capacity is achievable with a sequence of block codes whose errors vanish as lengths grow. This does not attach an error value to an arbitrary finite codebook.

Choose an input law and independently draw every codeword from its iid block distribution. A joint-typicality decoder looks for a unique codeword jointly typical with the received output. The actual transmitted pair is typical with high probability. An independently drawn competing word has roughly two to the minus n mutual-information chance of fitting the same output, with slack terms supplied by typicality. A union bound over the competing messages gives the essential rate condition.

If the rate lies strictly below that input law's mutual information, both the atypicality term and the competitor term can vanish. This bounds expected average error over the random ensemble. Therefore some deterministic codebook has no worse average error than the ensemble bound. The theorem does not require a new random codebook for each transmission, and it does not assert that every codebook drawn from the ensemble is good. An efficient encoder and decoder are further design questions.

If a deterministic code has small average error, at least half its messages have conditional error at most twice that average. Keeping those messages produces a code with controlled maximal error and loses at most one bit from log₂ M. The rate loss is at most one over n, so average-error and maximal-error capacities agree for this DMC. This expurgation argument concerns a carefully selected subcode, not an automatic improvement of every message in the original code.

Finite-block performance additionally depends on block length, desired error and code structure. Being below capacity establishes that sufficiently long good codes exist, without certifying a particular short code. Counting raw channel flips also differs from decoding error: an error-correcting decoder can recover a message despite several flipped symbols. Conversely, sending an uncoded long packet and requiring every symbol to arrive unchanged can have a declining success probability even while positive-rate reliable coding is possible.