= Expurgation of a codebook
Expurgation discards messages with unusually high conditional decoding error. If a codebook with $2M$ equally likely messages has average error at most $\epsilon$, at least $M$ messages have individual error at most $2\epsilon$, by <Markov's inequality>. Retaining those messages and restricting the decoder's candidates gives a codebook with maximal error at most $2\epsilon$, 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.
Back to article page
