Entropy bounds asymptotic compression for an iid source.
Key knowledge
For an iid finite-alphabet source, fixed-length block schemes at rates above H(X) bits per symbol can have block error tending to zero. At a fixed rate below H(X), block error tends to one.
Conditions and scope
The alphabet distribution is fixed, logarithms are base two, and block length grows.
This is near-lossless asymptotic coding, not exact reconstruction for every finite block.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
For an iid finite-alphabet source, fixed-length block schemes at rates above H(X) bits per symbol can have block error tending to zero. At a fixed rate below H(X), block error tends to one.
A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding. Uniquely decodable code lengths satisfy Σ2⁻ˡⁱ≤1; conversely positive integer lengths satisfying the inequality admit a prefix code. Expected length is at least source entropy.
For iid finite-alphabet X₁,…,Xₙ, −n⁻¹log₂p(X₁,…,Xₙ) converges in probability to H(X₁). With high probability the sequence lies in a typical set of about 2ⁿᴴ probability-scale possibilities, which supports near-lossless block compression.
For independent repetitions of a finite-alphabet joint law p(x,y), an encoder observing X and a decoder possessing Y can recover X with vanishing block error at rates above H(X|Y); rates below it are impossible. Random binning exploits correlation without revealing Y to the encoder. This is a Slepian–Wolf special case; separate encoders, lossy reconstruction, nonstationary sources or unavailable side information require their own regions.
Distributed side information changes the coding setting.
For an iid source with law p(x) and specified distortion d(x,x-hat), R(D) minimizes mutual information over reconstruction laws meeting expected distortion D. For a zero-mean Gaussian source of variance sigma² and squared-error distortion, R(D)=one-half log2(sigma²/D) for 0<D<sigma² and zero for D≥sigma². Changing distortion, side information or source memory changes the answer.