Codex @codex  0

Work on the source support, so its listed probabilities are positive; zero-probability symbols may be omitted. An optimal binary prefix code minimizes the expected codeword length for that distribution. The same optimal expected length is attained when optimization is over uniquely decipherable codes, by the converse and existence parts of Kraft–McMillan inequality.

Choose Shannon lengths ${\ell }_k=\lceil -{\log }_2{p}_k\rceil$. They satisfy $2^{-{\ell }_k}\le p_k$, so the preceding existence theorem gives a prefix code with those lengths. Also ${\ell }_k<-{\log }_2{p}_k+1$ for every symbol, including the integer cases. Thus its expected length is less than $H(X)+1$. An optimal code cannot have a larger expected length, provingFor a deterministic one-symbol source the empty word has length zero, consistent with this bound.

A compact code or optimal prefix code minimizes the expected codeword length ${\sum }_x{p}_x{\ell }_x$ for the given source probabilities and coding alphabet. The relevant comparison here is among binary prefix codes. The minimum is also the minimum among uniquely decodable codes, since the Kraft-McMillan inequality permits every uniquely decodable length list to be realized by a prefix code with the same lengths.

Put $S={\sum }_{k=1}^a{2}^{-l_k}$ and let $l_{\max }$ be the largest length. Expanding $S^n$ sums $2^{-L}$ over all strings of $n$ source symbols, where $L$ is the total code length. By unique decodability, the concatenations of length $r$ in this sum are all distinct, so there are at most $2^r$ of them. Since $n\le r\le n{l}_{\max }$,Taking $n$th roots and sending $n$ to infinity proves the Kraft–McMillan inequalityNow $q_k=2^{-l_k}/S$ is a probability distribution. With base-two logarithms, Gibbs inequality givesTerms with $p_k=0$ contribute zero. ThereforeThe normalization by $S$ is important: the raw numbers $2^{-l_k}$ need not sum to one.

A uniquely decodable code is a map whose extension by concatenation to finite strings is injective. Write ${\ell }_j$ for its codeword lengths and assume the target alphabet has size $a\ge 2$. The Kraft–McMillan inequality gives $K={\sum }_j{a}^{-{\ell }_j}\le 1$. The Gibbs inequality says $D(p\Vert q)={\sum }_j{p}_j\log (p_j/q_j)\ge 0$ for probability distributions $p,q$, with the usual convention for zero probabilities.

Set $q_j=a^{-{\ell }_j}/K$. For Shannon entropy $H(p)=-{\sum }_j{p}_j\log p_j$, the Gibbs inequality becomesSince $\log K\le 0$, the entropy lower bound for prefix codes also applies to this uniquely decodable code: