For the nontrivial case , every and
The probability ordering makes . At a dyadic number, choose the terminating binary expansion followed by zeros. Let be the first bits of , and let
be its binary cylinder interval.
Suppose and were a prefix of . Since , the numbers and would have the same first bits, so both would lie in . In particular . But
a contradiction. A later word cannot be a shorter prefix of an earlier word because the lengths are nondecreasing; equal-length coincidences were also excluded. Thus the cumulative Shannon code is a prefix code.
The ceiling inequalities give
Multiply by and sum to obtain
For a one-symbol deterministic source the displayed construction assigns the empty word and gives . This zero-bit convention is valid when the number of source emissions is supplied separately. It is not an unframed uniquely decodable code: concatenating different numbers of empty words gives the same bit string. If positive-length unframed words are required, the shortest deterministic code has length , so the strict upper bound requires the nontrivial-source assumption.
Take every logarithm in base two. The information entropy of is
with . If the codeword has length , then its expected codeword length is
For any decipherable code, the Kraft inequality gives
Define the probability distribution . By Gibbs inequality,
Since ,
Conversely, choose the integer lengths
Then , so their Kraft sum is at most one and the converse part of Kraft's inequality supplies a binary prefix code. Moreover,
Thus the minimum expected length satisfies the Shannon noiseless coding theorem
For a decipherable code with arbitrary lengths , apply the lower bound to the uniform source . Its entropy is and its expected length is . Hence
the total length lower bound for a decipherable binary code.
Now consider the cumulative construction. Since
and cannot have the same first binary digits: numbers sharing those digits lie in one half-open dyadic interval of length . Also, implies . Therefore no earlier codeword is a prefix of a later one, and no later, weakly longer codeword can be a prefix of an earlier one. The cumulative Shannon code is thus a prefix code, hence decipherable.
An optimal code minimizes expected codeword length over all decipherable codes for the specified source probabilities. The cumulative construction need not be optimal. For example, if
then and the construction gives codewords and , with expected length . The prefix code has expected length , so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.