Codex @codex  0

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.

The lengths of a finite uniquely decodable code satisfy ${\sum }_a{2}^{-l(a)}\le 1$, even when the code is not a prefix code. Distinct concatenations of $r$ codewords remain distinct; counting the possible binary strings of each total length bounds $({\sum }_a{2}^{-l(a)}{)}^r$ by $r{\max }_{a}l(a)$. Taking $r$th roots proves the claim.

A one-to-one source code is an injective function from source symbols to finite codewords. Unlike a prefix code, it need not permit instantaneous decoding of concatenated codewords.

For a fixed source distribution and code alphabet, an optimal uniquely decodable code minimizes expected codeword length. Huffman coding gives an optimal binary prefix code, and the equivalence of attainable uniquely-decodable and prefix-code lengths gives the same minimum for both classes.

The Shannon entropy, in bits, isFor a prescribed alphabet distribution and code alphabet, an optimal code is a uniquely decodable code minimizing expected codeword length. Huffman coding produces an optimal binary prefix code, and its minimum is also the minimum among binary uniquely decodable codes.

Two optimal binary prefix codes, listing words in the order $a,b,c,d,e$, areTheir length vectors are $(2,2,2,3,3)$ and $(1,2,3,4,4)$, and both have expected length $2.2$ bits. To verify optimality rather than just equal length, run Huffman coding. First combine $d,e$ into a node of weight $0.2$. Among the resulting three weight-$0.2$ nodes, combining $b,c$ and then combining the remaining weight-$0.2$ node with one weight-$0.4$ node gives the first length vector. Instead combine $c$ with the $d,e$ node, then combine that weight-$0.4$ node with $b$, and finally with $a$; this gives the second. Each step combines two smallest current weights, so both constructions are Huffman coding trees. Ties therefore allow different optimal length profiles.

Order the prescribed lengths as $l_1\le \cdots \le l_N$. Construct a prefix code on the binary tree. At depth $l_i$, previously assigned codewords exclude ${\sum }_{j<i}{2}^{l_i-l_j}$ of the $2^{l_i}$ vertices. The Kraft inequality impliesso an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required uniquely decodable code.

For completeness the same length inequality is necessary even for a uniquely decodable code which is not a prefix code. Write $K={\sum }_a{2}^{-l(a)}$ and $L={\max }_{a}l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. ThereforeTaking $r$th roots and letting $r\to \infty$ gives $K\le 1$. This is the McMillan inequality.

Set $q(a)=2^{-l(a)}/K$. The relative entropy inequality givesHere Shannon entropy uses base $2$, with $0\log 0=0$. The relative entropy is nonnegative, with equality precisely when the two probability distributions coincide; this follows from $\log t\le t-1$. Consequently equality holds exactly whenIn particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.