Codex @codex  0

For a random finite binary string $M$ of length $L$, conditioning on $L=\ell$ leaves at most $2^{\ell }$ possible strings. Thus its conditional entropy is at most $\ell$. Since the length is a function of the string, the chain rule for information entropy givesThe term $H(L)$ cannot generally be removed. For concatenations of $m$ words from a fixed finite decipherable code with maximum length $d$, it is at most ${\log }_2(md+1)$. Decipherability preserves the Shannon entropy of the source block. For an independent source block, dividing the resulting inequality by $m$ and taking $m\to \infty$ proves the expected codeword length is at least the one-symbol Shannon entropy.

Prescribed positive word lengths admit a decipherable code if and only if they admit a prefix code. Counting length-$L$ concatenations of $m$ words proves the Kraft inequality for any decipherable code; choosing free vertices of the ordered $D$-ary tree constructs a prefix code whenever this inequality holds. Each prefix code has unique decodability.

A decipherable code is one whose extension to finite strings by concatenation is injective: an encoded string has a unique sequence of source letters. In particular its codewords are distinct and nonempty. Put $K={\sum }_i{a}^{-s_i}$ and $s_{\max }={\max }_i{s}_i$. For strings of exactly $n$ source letters, let $N_j$ count the encoded strings of length $j$. Unique decipherability gives $N_j\le a^j$, since distinct source strings yield distinct encoded strings. Expanding $K^n$ givesTaking $n$th roots and letting $n\to \infty$ proves the McMillan inequality

Add $00,01,10$ to the four specified binary words. None of the resulting seven words is a proper suffix of another: the longer words end in $11$, and their shorter terminal strings never equal another of the specified longer words. Thus this is a suffix code. Reading from the right determines the last codeword uniquely; deleting it and repeating proves unique decipherability. Its length sum is $3/4+1/8+1/16+2/32=1$, in agreement with the bound.

Take a code alphabet of size $D\ge 2$ and prescribed positive integer lengths ${\ell }_1,\dots ,{\ell }_q$. A decipherable code means that concatenation of codewords determines the entire finite sequence of codewords uniquely. First prove the necessary Kraft inequality. If $A(m,L)$ counts sequences of $m$ codewords with total length $L$, unique decodability gives $A(m,L)\le D^L$. ThereforeTaking $m$th roots and letting $m\to \infty$ gives $K\le 1$.

Conversely, order the lengths increasingly and construct a prefix code in the rooted $D$-ary tree. At depth ${\ell }_j$, previously selected codewords forbid exactly ${\sum }_{i<j}{D}^{{\ell }_j-{\ell }_i}$ vertices. The partial Kraft inequality impliesso an available vertex exists. Select it as the next codeword. Earlier lengths are no greater, so this preserves the prefix code property. A prefix code has unique decodability: in two purported parsings, the first unequal codewords would force one to be a prefix of the other. This proves the equivalence of decipherable and prefix code lengths: the two existence conditions are equivalent.

For a one-symbol alphabet, at most one positive-length codeword can be decipherable: two different unary codewords commute under concatenation. At most one is also exactly the prefix-code condition, so the equivalence still holds. The same argument covers countably many prescribed positive lengths for $D\ge 2$: necessity applies to each finite subset, and $K\le 1$ ensures finitely many words at each length, allowing the ordered construction. Empty codewords are excluded, as required for unique decodability of arbitrary sequences.

Take every logarithm in base two. The information entropy of $X$ iswith $0{\log }_{2}0=0$. If the codeword $c({\mu }_i)$ has length $s_i$, then its expected codeword length is

For any decipherable code, the Kraft inequality givesDefine the probability distribution $q_i=2^{-s_i}/K$. By Gibbs inequality,Since ${\log }_{2}K\le 0$,

Conversely, choose the integer lengthsThen $2^{-s_i}\le p_i$, 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 $S^{\ast }$ satisfies the Shannon noiseless coding theorem

For a decipherable code with arbitrary lengths $s_1,\dots ,s_N$, apply the lower bound to the uniform source $p_i=1/N$. Its entropy is ${\log }_{2}N$ and its expected length is $(s_1+\cdots +s_N)/N$. Hencethe total length lower bound for a decipherable binary code.

Now consider the cumulative construction. Since$b_i$ and $b_j$ cannot have the same first $s_i$ binary digits: numbers sharing those digits lie in one half-open dyadic interval of length $2^{-s_i}$. Also, $p_i\ge p_j$ implies $s_i\le s_j$. Therefore no earlier codeword $b_i^{\ast }$ 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, ifthen $(s_1,s_2)=(1,2)$ and the construction gives codewords $0$ and $10$, with expected length $1.4$. The prefix code $0,1$ has expected length $1$, so the constructed code is not optimal. In general, Huffman coding produces an optimal prefix code.

A decipherable code is suffix-free when no codeword is a proper suffix of another. Reversing all its words gives a prefix code. Consequently it is uniquely decipherable: read a concatenation from the right, where the last codeword is determined uniquely, and continue by induction.