Motivation
A source may produce some symbols much more often than others. Using shorter descriptions for frequent symbols can reduce average length, but the receiver must still know where each description ends. Prefix codes enforce an unambiguous boundary. Entropy measures the best possible average length up to less than one bit for a single symbol in the finite setting developed here.
Definitions
Definition 3.1.1
(Binary entropy)
Let a source take one of symbols with probabilities and . Symbols of probability zero may be omitted from this finite list. Its binary entropy is
Definition 3.1.2
(Prefix-free code)
A binary code assigns each symbol a distinct finite binary word. Its length is and its expected length is . A code is prefix-free if no codeword is a prefix of a different codeword. We allow the empty word only when it is the sole codeword. A prefix-free code with nonempty words can be decoded from left to right by stopping as soon as a codeword is recognized; the prefix condition prevents that word from being the beginning of a longer one. For the sole empty codeword, the receiver must know separately how many symbols were sent.
Theorem/proposition
Theorem 3.1.3
(Kraft inequality)
The lengths of a finite binary prefix code satisfy . Conversely, any finite list of nonnegative integer lengths satisfying this inequality is realized by a binary prefix code.
Theorem 3.1.4
(Entropy and expected length)
For any finite binary prefix code with expected length , . There is a prefix code with .
Proof sketch or proof idea
Proof
(Dyadic intervals for Kraft’s inequality)
A binary word of length represents a dyadic interval of length in : its bits identify one of the equal intervals. If a finite code is prefix-free, its intervals are disjoint. Their lengths sum to at most one, proving the necessary inequality.
Conversely, sort the proposed lengths in nondecreasing order. Place intervals of lengths consecutively starting at zero. Before placing the interval of length , the total of preceding lengths is an integer multiple of , because all preceding lengths correspond to coarser dyadic intervals. Thus the new interval is itself dyadic at the required depth. Kraft's inequality keeps all intervals inside . Their binary labels form a prefix-free code: one dyadic interval contains another exactly when its label is a prefix of the other's label. The empty word gives the whole interval, so it is possible only as the sole codeword.
Proof
(Divergence and rounded lengths)
For the entropy bound, first use for . It follows by differentiating , whose minimum occurs at . If are positive probability vectors of equal length, then
Indeed apply to , multiply by , and sum: .
For prefix lengths let and set . Then is a positive probability vector and
For the upper bound choose . Then , so Kraft's inequality permits a prefix code with those lengths. Since , multiplying by and summing gives . The lower bound applies to this code too. This proves a single-symbol statement; it does not claim that every code achieves entropy or that a particular source model has been verified.
Proof X-ray
What the prefix condition contributes
The lower bound uses the prefix condition only through Kraft's inequality ; after that, the argument concerns two probability vectors. The non-obvious move is to normalize the dyadic weights, , so that the divergence inequality applies. The normalization costs exactly , which is nonnegative because , and positivity of every keeps each logarithm finite.
The upper bound runs the other way. The rounded lengths satisfy , so their Kraft sum is at most , and the converse half of Kraft's theorem produces the code; the strict inequality comes from . Without the prefix condition, may exceed one and becomes negative, which is exactly how the counterexample under common mistakes escapes the bound.
Why uniform probabilities maximize entropy
Theorem 3.1.5
(Uniform distribution maximizes entropy)
For positive probabilities, . The upper bound is attained exactly by the uniform distribution.
Proof
(Comparison with the uniform law)
For positive probabilities, compare with the uniform distribution . The divergence inequality gives
Hence . The lower bound holds because , making each term nonnegative. Equality in the upper bound occurs only for the uniform distribution: equality in occurs only at , so every must be one. If , the sole probability is one and the entropy is zero.
Coding blocks and the role of independence
Theorem 3.1.6
(Block coding approaches entropy)
If source symbols are independent and identically distributed with law , the length- blocks have entropy , and some prefix code for the blocks has expected length with .
Proof
(Block entropy and the per-symbol rate)
Suppose source symbols are independent and identically distributed with probabilities . Treat each length- sequence as one symbol of an enlarged alphabet. Its probability is the product of its coordinate probabilities. The block entropy is
To see the last equality, expand the logarithm into a sum of terms. In each term, summing probabilities over all other coordinates gives one, leaving . Independence is essential to the product formula. If repeated symbols are perfectly correlated, the block entropy can be much smaller than .
Apply the previous construction to the finite block alphabet. Its expected codeword length satisfies
Thus the expected number of bits per original symbol approaches entropy as block length grows. This is an existence statement for a code of each finite block length, not a bound on computational cost, memory, delay, or performance under an incorrect source distribution. The block alphabet has possible sequences when all probabilities are positive, so a direct table can grow rapidly.
A prefix code as a tree
Concept lensCombinatorial
Kraft’s inequality by counting leaves
A finite binary prefix code can be drawn as a rooted binary tree. Starting at the root, a 0-bit follows a left edge and a 1-bit follows a right edge. Codewords label selected nodes, and prefix-freeness says no selected node is an ancestor of another. We may regard them as leaves after discarding unused descendants. At depth , a codeword of length has descendants. Their descendant sets are disjoint and lie among the nodes at depth . Dividing the count by recovers Kraft's inequality.
The tree picture also clarifies the case : some depth- leaves are unused. It does not require every internal node to have two used children. Completing a tree by inserting unused words may change the message alphabet and is not necessary to encode the original symbols.
Equality and conventions
Theorem 3.1.7
(Equality in the entropy bound)
A prefix code for single symbols has exactly when for every symbol.
Proof
(Both slack terms must vanish)
The proof of the lower bound separates two possible sources of slack:
Both terms on the right are nonnegative. Equality therefore requires and . By the equality case of , the latter means for every . Combined, these conditions say for every symbol. Conversely, if each probability equals its codeword's dyadic weight, direct substitution gives . Thus a prefix code for individual source symbols attains the lower bound exactly when its probabilities match the dyadic weights of a complete prefix-length list.
For one symbol, the length-zero word is allowed under our convention, yielding and . Some communication settings require at least one bit or a separate termination marker. Those are additional coding constraints, so the allowed code family and optimal average can change. The mathematical zero-length case does not mean a real protocol needs no framing or information about how many symbols were sent.
A prefix code with nonempty words is uniquely decodable from left to right: reading each codeword determines its end before the next begins. For the sole empty codeword, a separately known word count determines the sequence, since no bits are available to mark its repetitions. The entropy and Kraft results stated here do not require a proof of the more general theorem for all uniquely decodable codes. A code that is not prefix-free might still be uniquely decodable by a more complicated procedure, so failure of the prefix property alone is not a proof of ambiguity for every possible concatenation.
The model measures codeword bits only. It does not count the cost of communicating a changing dictionary, synchronizing blocks, or detecting transmission errors.
Worked examples
Worked example 3.1.8
(Unequal probabilities)
For probabilities , the prefix words have lengths and expected length . The entropy is also . Here the length of each word equals , so the lower bound is attained.
Worked example 3.1.9
(A nonintegral information value)
For three equally likely symbols, . The code has expected length . A length of bits cannot be assigned to each individual word because word lengths are integers, although averages can be nonintegral. This is consistent with both bounds: .
Worked example 3.1.10
(A forbidden length list)
Three binary codewords all of length one would have Kraft sum . No prefix code can have these lengths; in fact only two binary words of length one exist. The converse part of the theorem says that when the Kraft sum is at most one, a prefix code with the specified integer lengths can be constructed.
Worked example 3.1.11
(A biased binary source)
For two symbols with probabilities and , the entropy is
It is less than the one bit of a fair binary source. A prefix code for the two individual symbols still needs at least one bit for each: neither word may be empty when there are two words. Thus the one-symbol code has average length 1, not . The entropy lower bound need not be attained by integer word lengths.
Worked example 3.1.12
(Independent and perfectly correlated bit pairs)
For two independent fair bits, the four two-symbol blocks are equally likely. Assign as codewords. The expected block length is 2 bits and the expected length per original symbol is 1, equal to the single-symbol entropy. If the two symbols are instead perfectly correlated, only the blocks and occur, each with probability ; their block entropy is 1 bit, not 2. Marginal probabilities alone did not determine the joint entropy.
Common mistakes
Common mistake
(Distinct words need not be prefix-free)
A small average length does not guarantee instantaneous decoding. The words and are distinct but not prefix-free: reading an initial zero does not reveal whether it is a complete first word or the start of the second. Prefix-free is a sufficient instantaneous-decoding condition; the entropy theorem here is stated for prefix codes, not asserted for every arbitrary list of distinct words.
Dropping the prefix condition does not merely complicate decoding; it can break the entropy bound itself.
Counterexample mode
Distinct words alone do not respect the entropy bound
Claim: every code that assigns distinct binary words satisfies . For use the distinct words . Then
The code is not prefix-free, since is a prefix of , and its Kraft sum is . It is not decodable either: the string could be one third symbol or two first symbols. The repaired statement is the theorem proved above: prefix codes satisfy .
Common mistake
(The bound concerns the average length)
Entropy depends on probabilities, not just the number of possible symbols. The upper bound is a bound on the constructed code's average length, not on the length of every individual word. The probabilities must form a distribution; is omitted here to avoid writing , with the usual limiting convention available when desired.
Summary
Kraft's inequality converts prefix-freeness into a bound on binary-tree capacity and also characterizes which finite length lists can be realized. The entropy lower bound follows from a nonnegative divergence, and rounding information values upward constructs a code whose average is less than one bit above entropy.
Exercises
Quick check
(Can a binary prefix code have lengths ?)
Compute the Kraft sum.
Solution · Answer
No. The Kraft sum is .
Quick check
(For two equiprobable symbols, find the entropy and an optimal prefix code.)
Use the uniform-maximum theorem with .
Solution · Answer
bit. The words and both have length 1 and average 1, achieving the entropy lower bound.
Quick check
(A prefix code has lengths . Compute the Kraft sum and construct one such code.)
Place the two short words first, then split one unused word of length two.
Solution · Answer
The sum is . One code is . None of these words is a prefix of another. The unused capacity does not obstruct decoding.
Quick check
(A source produces the same fair bit twice, so its possible two-bit blocks are and , each with probability . Find the block entropy and compare it with twice the marginal entropy.)
Count the outcomes that actually occur.
Solution
The block has two equiprobable outcomes, so its entropy is 1 bit. Each individual bit has entropy 1, but the two bits are dependent and twice the marginal entropy is 2. The product-distribution proof for independent symbols does not apply.
Quick check
(Can a binary prefix code with lengths , paired in that order with source probabilities , attain entropy exactly?)
Compute and compare it with .
Solution
Its expected length is , whereas the source entropy is . Thus it does not attain the lower bound. Its Kraft sum is , also showing unused tree capacity. A code with lengths attains entropy for these probabilities.
Quick check
(A source has one symbol of probability one. What do the stated conventions give for entropy and optimal expected length?)
Use the convention for the empty word.
Solution · Answer
Its entropy is . Assigning the empty word gives expected length zero and meets the lower bound. A practical system's message-count or framing requirements may impose additional costs outside this model.