Source coding and Kraft's inequality

A binary prefix code has no codeword that is the beginning of another. The decoder can therefore identify the current word without waiting for later symbols. A word of length ell occupies a fraction two to the minus ell of a full binary tree's possible extensions. Disjointness of these occupied branches implies Kraft's inequality. Conversely, nonnegative integer lengths satisfying that inequality can be realized by a prefix code; with at least two supported symbols their usable codewords have positive lengths.

Unique decodability is weaker than the prefix condition: a code can allow unambiguous complete concatenations without allowing immediate symbol-by-symbol termination. McMillan's inequality gives the same necessary length constraint for uniquely decodable codes. Here the constructive examples use prefix codes so that a tree provides an explicit decoder. If the source is a singleton, an empty word can represent its sole symbol when the number of symbols to decode is known; that convention must be separated from a multi-symbol source.

For a finite source with at least two positive-probability symbols, choose Shannon lengths by rounding each ideal information value up to the next integer. Their Kraft sum is at most the sum of the source probabilities, hence at most one. Each rounded length is strictly less than its ideal length plus one. Averaging produces a prefix code with expected length below H plus one. This does not say that every valid prefix code is so efficient; arbitrarily wasteful codes remain valid.

The lower bound follows by normalizing the masses two to the minus each length into a probability law and using nonnegative divergence. Equality is possible for dyadic probabilities whose ideal lengths are already integers. Huffman's algorithm optimizes the expected length among finite binary prefix codes by repeatedly merging two smallest masses. Its tree argument exploits the fact that two least probable symbols can be assigned deepest sibling leaves without increasing the expected length.

A variable-length prefix code can reconstruct every supported source symbol with zero error while controlling expected length. A fixed-length block code has a different tradeoff: below the logarithm of the supported block count, it generally needs to permit a failure event. Typicality can make that probability small at rates above entropy. These statements are compatible because they constrain different quantities, namely expected length versus a fixed number of transmitted bits.

Likewise, compressing the count of ones in a block preserves less than compressing the block itself. Several ordered blocks can have one count, so a decoder for the count has not reconstructed their order. An entropy calculation should name the object whose distribution it uses. This distinction is relevant in data aggregation: a summary may be exactly encoded and still discard information needed for a later task, even when its own code is optimal.