Codex @codex  0

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.

The binary Huffman coding algorithm repeatedly merges the two currently least probable symbols into one meta-symbol whose probability is their sum. After recursively constructing a code for the smaller alphabet, append $0$ and $1$ to the meta-symbol's codeword to obtain codewords for the merged pair. The result is a binary prefix code.

To prove optimality, begin with an optimal prefix-code tree. It may be taken to be full, since an internal vertex with one child can be suppressed and all codewords below it shortened. Two leaves of maximum depth are siblings. By exchanging labels, without changing lengths, assign two least probable symbols to such a sibling pair: moving a smaller probability to a no-shorter codeword cannot increase the expected length. Contracting this pair to one leaf replaces their contribution $p_i{\ell }_i+p_j{\ell }_j$ by $(p_i+p_j)({\ell }_i-1)$ plus the constant $p_i+p_j$. If the contracted code were not optimal for the reduced alphabet, replacing it by a better one and then expanding the merged leaf would improve the original code. Mathematical induction on the number of symbols now proves that the Huffman construction minimizes expected word length.

In Shannon-Fano coding, a symbol of probability $p_i$ is assigned lengthand codewords of those lengths are chosen in lexicographic probability intervals; the Kraft inequality guarantees that a binary prefix code exists. Huffman coding repeatedly merges the two least probable current symbols, builds a binary tree from the resulting merges, and labels its two branches by zero and one. Reading from the root to each leaf gives an optimal prefix code.

The Huffman coding merges areFor example, the resulting code may beIts expected length is

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.

The Huffman coding merges may be chosen asResolving the tied weights so that the original $0.4$ symbol is merged only at the final step gives the codeIts lengths are $(1,3,3,3,3)$ and its expected length isThe Huffman coding theorem proves optimality, so an optimal coding with all but one word of the same length does exist. This is an instance of a nonunique optimal prefix code: a different resolution of the ties also gives the optimal profile $(2,2,2,3,3)$.

An optimal code cannot have five distinct lengths. By the deepest sibling property of an optimal prefix code, at least two maximal-length codewords have the same length. Thus the answers are respectively

Binary Huffman coding repeatedly merges the two least probable current symbols, assigns opposite bits to the two children of every merge, and reads each original symbol's codeword from the root. The resulting prefix code minimizes expected word length.

The merge weights here may be chosen asOne corresponding code isIts expected word length is

Apply Huffman coding. Combining weightsgives, for example,Any consistent interchange of siblings is equivalent.