Codex @codex  0

A radius-$r$ Hamming decoder outputs the unique codeword within distance $r$ of the received word, if there is one. Ambiguous cases and absent candidates can be declared errors, or assigned arbitrarily for an error bound. The average error is the mean of the conditional error probabilities over the equally likely transmitted messages.

Let $V_n(r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ be the size of a Hamming ball. For any transmitted random codeword, the channel noise weight is $U\sim \mathrm{Bin}(n,p)$. Decoding can fail only if $U>r$ or another codeword lies within distance $r$ of the output. Conditional on the output, each independently sampled competing codeword is still uniform on the whole word space, so has probability $2^{-n}{V}_n(r)$ of lying in that ball. A union bound yieldsThis is an average over the random code construction as well as over messages and noise. It implies existence of at least one deterministic codebook with average error no greater than this bound, rather than asserting the same inequality for every randomly sampled book.

Choose a target rate $R<1-h(p)$ and a small $\delta >0$ such that $p+\delta <1/2$ and $R<1-h(p+\delta )$. Let $M_n=\lfloor 2^{nR}\rfloor$ and $r=\lfloor n(p+\delta )\rfloor$. The standard Hamming-volume estimate is $V_n(r)\le 2^{nh(r/n)}$: for $s=r/n\le 1/2$, each binomial probability term $s^j(1-s{)}^{n-j}$ with $j\le r$ is at least $s^r(1-s{)}^{n-r}$, and summing proves this bound. Thus the union-bound term decays exponentially, while $P(U>r)\to 0$ by the law of large numbers or a Chernoff bound.

There exists a $2M_n$-message book with average error ${\epsilon }_n\to 0$. At least half its messages have individual error at most $2{\epsilon }_n$, by Markov's inequality on the uniformly chosen message. Keep $M_n$ of these and discard the rest. Restricting the decoder's candidate set cannot spoil a previously unique successful decoding. The retained book therefore has maximum error at most $2{\epsilon }_n\to 0$. For large $n$ its retained codewords must be distinct: identical words could not both have conditional error below one half. This expurgation of a codebook proves reliable communication at every rate below $1-h(p)$, while converting an average-error estimate into the requested maximum-error conclusion.

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.