Codex @codex  0

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.

Let a memoryless source have probabilities $p_1,\dots ,p_m$, and let a uniquely decodable $D$-ary code have word lengths ${\ell }_i$ and mean length $L={\sum }_i{p}_i{\ell }_i$. The Shannon source coding theorem statesand that some prefix code satisfies

For the lower bound, the Kraft inequality gives $K={\sum }_i{D}^{-{\ell }_i}\le 1$. Set $q_i=D^{-{\ell }_i}/K$. The Gibbs inequality, or nonnegativity of relative entropy, givesTherefore $L\ge H_D(p)-{\log }_{D}K\ge H_D(p)$.

For achievability choose ${\ell }_i=\lceil -{\log }_D{p}_i\rceil$. Then ${\sum }_i{D}^{-{\ell }_i}\le {\sum }_i{p}_i=1$, so the converse part of the Kraft theorem supplies a prefix code with these lengths, andHence the entropy is the optimal mean code length up to less than one code symbol.

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 binary Kraft inequality states that codeword lengths $l(a)$ of a prefix code, or more generally a uniquely decodable code, satisfyConversely, positive integer lengths obeying this inequality can be realized by a binary prefix code.

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 binary Kraft inequality says that codeword lengths $l_1,l_2,\dots$ of a prefix code satisfyConversely, suppose positive integer lengths obey this inequality and arrange them in nondecreasing order. Construct codewords greedily in the infinite binary tree. Before assigning length $l_i$, each earlier codeword of length $l_j\le l_i$ excludes exactly $2^{l_i-l_j}$ nodes at depth $l_i$. Thus the number excluded iswhere strictness follows because the remaining term $2^{-l_i}$ occurs in the full Kraft sum. A free depth-$l_i$ node therefore exists. Assign it as the next codeword; choosing a node not below an earlier codeword preserves prefix-freeness. Induction constructs the required prefix code.

For a $q$-ary code with codeword lengths $l_1,\dots ,l_m$, Kraft inequality isChoose an infinite random $q$-ary string with independent uniform symbols. The event that it begins with codeword $i$ has probability $q^{-l_i}$. For a prefix-free code, these events are disjoint, so their probabilities sum to at most one. This proves necessity.

If one comma codeword were a prefix of another, its terminal comma would occur inside the longer codeword, contrary to the definition. Thus every comma code is prefix-free. Directly, the disjoint cylinder sets of infinite strings beginning with the respective comma-terminated words have measures $q^{-l_i}$, so their total measure gives Kraft's inequality.

Kraft's inequality does not imply unique decipherability. Over the binary alphabet,has Kraft sum $1/2+1/4+1/4=1$, butThus it is not uniquely decipherable.

For a binary prefix code with length function $L_n:A^n\to \mathbb{N}$, the Kraft inequality is

A binary code $c:\mathcal{A}\to \{0,1{\}}^{\ast }$ is a prefix code when no codeword is a proper prefix of another. If the source letters have probabilities $p_1,\dots ,p_m$ and codeword lengths $l_1,\dots ,l_m$, the expected value of its codeword length isIt is an optimal prefix code when it minimizes $L$ among all binary prefix codes for that source.

Suppose $p_i>p_j$ but $l_i>l_j$. Exchanging the codewords assigned to ${\mu }_i$ and ${\mu }_j$ leaves the set of words, and hence prefix-freeness, unchanged. The change in expected length iscontradicting optimality. Thuswhich is the probability monotonicity of optimal prefix-code lengths.

Represent the code by its binary prefix tree and choose a codeword $wb$ of maximal length, where $b\in \{0,1\}$. Its sibling is $w(1-b)$. If that sibling were not a codeword, it could not have a codeword below it either, since such a word would be longer than $wb$. Replacing $wb$ by $w$ would then preserve prefix-freeness and strictly reduce $L$. This is impossible for an optimal code, so $w(1-b)$ is also a maximal-length codeword. The pair differs only in its last digit, proving the deepest sibling property of an optimal prefix code.

The direct codes-distributions correspondence says that every mass function $Q$ on a finite alphabet admits a binary prefix code with lengths $L(x)=\lceil -{\log }_{2}Q(x)\rceil$. Conversely, every binary prefix code has lengths satisfying the Kraft inequality $K={\sum }_x{2}^{-L(x)}\le 1$, and hence defines the mass function $Q_C(x)=2^{-L(x)}/K$.

For a binary prefix code with word lengths $l_1,\dots ,l_m$, choose $L\ge \max l_i$. Each codeword is the prefix of exactly $2^{L-l_i}$ words of length $L$, and these descendant sets are disjoint. HenceThis is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

For Shannon--Fano coding, order symbols by probability and assignKraft's inequality applies because $2^{-l_i}\le p_i$ and therefore ${\sum }_i{2}^{-l_i}\le 1$. Thus codewords of those lengths exist. Sincethe expected length obeys

Shannon--Fano coding assigns a symbol of probability $p_i$ a prefix-code length near $-{\log }_2{p}_i$.