Channel coding

Channel coding represents messages with codewords chosen to withstand transmission errors. An error-correcting code deliberately supplies redundancy, so a receiver can distinguish nearby corrupted outputs and recover the message. Lossless source coding instead removes predictable redundancy; practical communication can use both operations. The Shannon second coding theorem relates achievable rates on a discrete memoryless channel to its channel capacity.

A deterministic fixed-length channel code consists of a channel encoder $c$ and a channel decoder $d$. It represents $m$ possible messages by length-$n$ input codewords for a communication channel, and estimates the message from the resulting output word. Its code rate is $({\log }_{2}m)/n$ bits per channel use. The maximal decoding error probability requires reliable recovery of every message, while an average error criterion depends on the chosen message probability distribution.

Random coding constructs a channel code by sampling its codewords from a specified probability distribution and bounding the expected decoding error over that ensemble. If the expected average error is at most $ϵ$, at least one deterministic codebook has average error at most $ϵ$; otherwise every book would exceed the expectation bound. This is the probabilistic method applied to communication codes.

For independently uniform binary codewords, a fixed competing word falls in any received word's radius-$r$ Hamming ball with probability $2^{-n}{\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The union bound over competing messages, together with a bound on excessive channel noise, yields the basic random-coding error estimate. Expurgation of a codebook can then convert average-error control to maximal decoding error probability with negligible loss of asymptotic rate.

Expurgation discards messages with unusually high conditional decoding error. If a codebook with $2M$ equally likely messages has average error at most $ϵ$, at least $M$ messages have individual error at most $2ϵ$, by Markov's inequality. Retaining those messages and restricting the decoder's candidates gives a codebook with maximal error at most $2ϵ$, provided removal of candidates cannot spoil a previously successful decoding. This is the case for bounded-distance decoding with errors on ambiguity, and for a decoder that retains its former decisions whenever the decoded message remains.

For a sequence of block lengths $n$, halving a book changes its logarithmic rate by $1/n$, which tends to zero. Thus a vanishing average-error bound from a random coding construction can be converted into a vanishing maximal decoding error probability at the same limiting rate. The probabilistic construction first supplies a deterministic book with sufficiently small average error; expurgation is a subsequent deterministic step.