Kraft–McMillan inequality

The Kraft–McMillan inequality states that codeword lengths in any uniquely decodable code over an alphabet of size r satisfy ∑ᵢ r⁻ⁿⁱ ≤ 1. The same bound characterizes lengths realizable by prefix-free codes.

Prefix code: A code in which no codeword is a prefix of another. Prefix-free trees make the length bound intuitive: each codeword occupies a disjoint subtree.
Codeword: A finite string of symbols assigned to represent a source symbol or message. The inequality uses each codeword’s length as its input.
Source coding theorem: A result relating the minimum achievable average code length to the entropy of a source. Kraft–McMillan bounds constrain the lengths over which source-coding limits are optimized.
Leon G. Kraft: An American mathematician and engineer whose 1949 thesis established the code-length inequality for instantaneous codes. Kraft proved the prefix-code form that bears his name.
Code tree: A rooted tree whose edges represent alphabet symbols and whose paths represent codewords. A codeword of length n occupies a tree region with a share proportional to r⁻ⁿ.
Code length: The number of symbols in a codeword. Each length nᵢ determines the term r⁻ⁿⁱ in the sum.
Huffman coding: A greedy algorithm for constructing an optimal prefix code from symbol probabilities. Its resulting code lengths form a prefix code and obey the inequality.
Boris McMillan: An American information theorist who extended Kraft’s inequality to uniquely decipherable codes. McMillan showed the bound applies beyond instantaneous, or prefix, codes.
Unique decipherability: A property of a code in which every concatenated encoded message has exactly one decoding. The inequality extends the prefix-code length constraint to codes that are not prefix-free.
Alphabet: A finite set of symbols from which strings are formed. Its size r sets the base of every term in the inequality.

Linked from 1 page

Shannon's source coding theoremRelated: It constrains possible code lengths and supports the theorem's lower bound.