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.

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.

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.

True. The Huffman tree is a full binary tree, so its leaves form a complete prefix code. The Kraft inequality is therefore an equality:

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.

The Shannon lengths are $l_S(a)=\lceil {\log }_2(1/P(a))\rceil$. Their Competitive optimality of the Shannon code says that for every binary uniquely decodable code of lengths $l_C$ and every positive integer $k$,On this event, $P(X)<2^{-l_C(X)-k+1}$. Summing and applying the Kraft inequality proves

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.

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

For the direct half of the code-distribution correspondence, let $L$ be the length function of a binary prefix code and putThen $R$ is a probability mass function andThus every prefix code determines a distribution whose ideal description lengths do not exceed the codeword lengths.

Conversely, given a probability mass function $R$, setfor $R(x)>0$. Then $2^{-L(x)}\le R(x)$, so the Kraft inequality is satisfied. Its converse supplies a binary prefix code with these lengths, andIf real lengths are allowed, the ideal choice $L(x)=-{\log }_{2}R(x)$ satisfies Kraft with equality.

Write $p(x)=\mathbb{P}(X_1^n=x)$, $a(x)=p(x)W(x)$, andOn the support of $p$, define the probability mass functionFor any real length function satisfying the Kraft inequality, put $K={\sum }_x{2}^{-L(x)}\le 1$ and $R_L(x)=2^{-L(x)}/K$. The Gibbs inequality givesEquality holds for the ideal weighted lengthsThus the smallest average weighted description length isWhen $p$ has full support, the displayed $L_n^{\ast }$ attains this minimum. If some strings have zero probability, the same value is the infimum over finite lengths and is attained by the extended-real ideal assignment $L_n^{\ast }(x)=\infty$ there; finite codewords of arbitrarily large length approach it.

The code-distribution correspondence starts from the Kraft inequality. For codeword lengths $L(x)$ putConversely, a probability mass function determines ideal lengths $-{\log }_{2}R(x)$, up to integer rounding. For the source law $P_n$,using nonnegativity of Kullback-Leibler divergence and $K\le 1$.

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