= Random coding
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 $\epsilon$, at least one deterministic codebook has average error at most $\epsilon$; 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\binom nj$. 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.
Back to article page
