Shannon's source coding theorem

Shannon's source coding theorem states that the minimum average code length for lossless compression approaches a source's entropy per symbol as block length grows. It also gives a lower bound: no lossless code can average fewer bits per symbol than the entropy.

Shannon entropy: A measure of the average information produced by a probabilistic source, expressed in bits when logarithms use base two. It sets the asymptotic minimum number of bits required per source symbol.
Discrete memoryless source: A stochastic source that emits symbols from a finite or countable alphabet independently according to a fixed probability distribution. The classic theorem is stated for independent, identically distributed symbols from such a source.
Source coding theorem: A result connecting the statistical information of a source to the limits of representing its outputs with codes. Shannon's result is the foundational discrete lossless version of this broader family.
Bernoulli source: A memoryless binary source that emits one of two symbols with a fixed probability of success. Its entropy varies with symbol bias, making the coding limit easy to calculate.
Kraft–McMillan inequality: A condition on codeword lengths that characterizes whether a set of strings can form a uniquely decodable code. It constrains possible code lengths and supports the theorem's lower bound.
Lossless compression: A representation method that reduces data size while preserving enough information for exact reconstruction. The theorem establishes the best asymptotic rate for compression with exact recovery.
Shannon's noiseless coding theorem: Shannon's result that a discrete source can be encoded with average length arbitrarily close to its entropy under suitable block coding. This name emphasizes the achievable coding rate in the absence of transmission noise.
Uniform distribution: A probability distribution that assigns equal probability to every outcome in its support. For a uniform source, entropy equals the fixed-length cost per symbol.
Prefix code: A code in which no codeword is the beginning of another, allowing unambiguous decoding as symbols arrive. Prefix codes achieve average lengths close to entropy without requiring lookahead during decoding.
Codeword: A finite string of symbols assigned to represent a source symbol or source block. Average code length is computed from the lengths of codewords and their probabilities.

Linked from 4 pages