Reliable source encoding at a rate

A source is reliably encodable at rate $r$ if there are block encoders with at most $2^{nr}$ outputs and corresponding decoders whose probability of reconstructing the first $n$ source symbols incorrectly tends to zero as $n\to \infty$.

For a finite-alphabet IID source of entropy $H$, fixed-length block codes of rate $R<H$ have reconstruction success probability tending to zero. At most $2^{nR}$ strings can be correctly reconstructed. Their typical probability is at most $2^{nR}{2}^{-n(H-\delta )}$, and the atypical probability tends to zero; choose $0<\delta <H-R$.

// Target: algebra.bigb