Prefix Codes and Finite Lossless Coding

If $t=1$, then $\ln t=t-1=0$. Otherwise let $a=\min \{1,t\}$ and $b=\max \{1,t\}$. By [F2] and [F3], $\ln$ is continuous on $[a,b]$; by [F5], it is differentiable on $(a,b)$ with derivative $1\mathrm{/}u$. Applying [F6] gives $c\in (a,b)$ with $\ln t-\ln 1=(t-1)\mathrm{/}c$, so $\ln t=(t-1)\mathrm{/}c$ by [F4]. If $t>1$, then $c>1$; if $0<t<1$, then $0<c<1$ and $t-1<0$. In either case $(t-1)\mathrm{/}c<t-1$. Thus $\ln t\le t-1$, with equality only at $t=1$.

Let $S=\{i:p_i>0\}$. By [F1], [A1], and step 1.1 applied to $q_i\mathrm{/}{p}_i$ for each $i\in S$, $D(p\mathrm{\parallel }q)=-{\sum }_{i\in S}{p}_i\ln (q_i\mathrm{/}{p}_i)\ge {\sum }_{i\in S}(p_i-q_i)=1-{\sum }_{i\in S}{q}_i\ge 0$. If $D(p\mathrm{\parallel }q)=0$, both inequalities are equalities. Equality in the last requires $q_i=0$ outside $S$, and [A1] then forces $S=[m]$. Equality in the first requires each nonnegative gap from step 1.1, multiplied by $p_i>0$, to vanish; hence $q_i\mathrm{/}{p}_i=1$ for every $i$. Conversely $p=q$ gives $D(p\mathrm{\parallel }q)=0$ by [F1].

Put $K:={\sum }_{i=1}^m{2}^{-{\mathrm{\ell }}_i}$ and $\lambda :={\max }_i{\mathrm{\ell }}_i$. For each integer $k\ge 1$, expand $K^k={\sum }_{(i_1,\dots ,i_k)\in [m{]}^k}{2}^{-({\mathrm{\ell }}_{i_1}+\cdots +{\mathrm{\ell }}_{i_k})}$. For each total length $s$, let $N_{k,s}$ count the tuples with ${\mathrm{\ell }}_{i_1}+\cdots +{\mathrm{\ell }}_{i_k}=s$. Their concatenated codewords are distinct by [F1] and each is a binary word of length $s$, of which there are exactly $2^s$ because each of the $s$ positions has two choices; hence $N_{k,s}\le 2^s$.

Since every ${\mathrm{\ell }}_i\ge 1$, the only possible totals satisfy $k\le s\le k\lambda$, so there are $k(\lambda -1)+1$ possible integer values of $s$. Grouping step 1.1 by $s$ gives $K^k={\sum }_{s=k}^{k\lambda }{N}_{k,s}{2}^{-s}\le k(\lambda -1)+1$. Therefore $K\le (k(\lambda -1)+1{)}^{1\mathrm{/}k}$ for every $k$.

Suppose $K>1$, set $ϵ=K-1>0$, and put $a=\lambda -1\ge 0$. By [F2], the integer $k:=\lfloor 1+2a\mathrm{/}{ϵ}^2\rfloor +1$ satisfies $k>1+2a\mathrm{/}{ϵ}^2$ and $k\ge 2$, so $k(k-1){ϵ}^2\mathrm{/}2>ak$. The binomial theorem gives $K^k=(1+ϵ{)}^k\ge 1+kϵ+\left(\genfrac{}{}{0px}{}{k}{2}\right){ϵ}^2>1+ak$, contradicting step 2.1, which gives $K^k\le ak+1$. Hence $K\le 1$.

Among two distinct codewords that are initial segments of the same binary word, one would be a prefix of the other: compare their lengths, since the shorter initial segment agrees with the initial part of the longer. By [F2], at most one codeword can be an initial segment of any binary word.

To parse a word in the range of $C^{\ast }$, repeatedly take its unique initial codeword from step 1.1 and remove it. Each removal shortens the unread finite word because codewords are nonempty by [F1]; the process therefore reaches the empty word after finitely many removals. At every stage the next codeword is forced, so the resulting source word is unique; the empty output is produced only by the empty source word. Thus $C^{\ast }$ is injective, which is unique decodability by [F1].

If a prefix code has lengths ${\mathrm{\ell }}_i$, its finite set of codewords is prefix-free by [F3]. Apply the first assertion of [F1] to that set; the codewords are distinct by nonsingularity, so its Kraft sum is exactly ${\sum }_i{2}^{-{\mathrm{\ell }}_i}\le 1$.

Suppose ${\sum }_i{2}^{-{\mathrm{\ell }}_i}\le 1$. Enumerate the finite request list $(i,{\mathrm{\ell }}_i)$ in increasing order of $i$; this is a computable enumeration, and the requested lengths are positive by hypothesis. The converse in [F1] allocates distinct prefix-free binary words of those lengths. Assign the word allocated to request $i$ as $C(i)$. Their positive lengths make $C$ a binary source code by [F2]. Distinctness gives nonsingularity and prefix-freeness gives [F3], so the requested binary prefix code exists.

At every prefix, the $m$ child intervals are disjoint half-open intervals whose union is the parent interval, because the cumulative probabilities increase from $0$ to $1$. Induction on prefix length therefore shows that the length-$n$ intervals partition $[0,1)$, and multiplying the successive width factors gives $\mathrm{\mid }I(x^n)\mathrm{\mid }=p^n(x^n)>0$ by [F1].

By [F8], put $w=\mathrm{\mid }I(x^n)\mathrm{\mid }$ and $r=\lfloor -{\log }_{2}w\rfloor$. Since $0<w\le 1$, [F4] and [F5] give $-{\log }_{2}w\ge 0$, so [F7] gives $r\ge 0$ and $r\le -{\log }_{2}w<r+1$. The same facts show that ${\log }_2$ is strictly increasing, and [F6] gives ${\log }_2(2^u)=u$; therefore $2^{-(r+1)}<w\le 2^{-r}$. Thus the cell width $\delta :=2^{-(r+2)}$ satisfies $\delta <w\mathrm{/}2$. If $c$ is the midpoint of $I(x^n)$, then $0\le c<1$ by step 1.1. By [F7], $k=\lfloor 2^{s}c\rfloor$ is an integer; since $0\le c<1$, it satisfies $0\le k<2^s$ and has an $s$-bit representation. Its cell $[k\delta ,(k+1)\delta )$ contains $c$ and lies within distance $\delta$ of it; hence it is contained in the interior of $I(x^n)$.

Distinct blocks have disjoint source intervals by step 1.1. Their nonempty dyadic cells from step 2.1 are therefore disjoint. If one emitted bit word were a prefix of another, its dyadic cell would contain the other's cell, contradicting disjointness. Thus the codewords are distinct and prefix-free by [F3]; the unique interval containing a received code cell identifies its block, and prefix-freeness parses concatenated fixed-$n$ frames.

By [F7] and [F8], $r\le -{\log }_{2}w$, so the emitted length is $s=r+2\le -{\log }_{2}w+2=-{\log }_2{p}^n(x^n)+2$ by step 1.1 and [F1]. This proves the pointwise bound without converting ideal-real interval arithmetic into a finite-register procedure.

Let $C$ be uniquely decodable and set $K:={\sum }_i{2}^{-{\mathrm{\ell }}_i}>0$. By [F3] and [F4], $K\le 1$. Define $q_i:=2^{-{\mathrm{\ell }}_i}\mathrm{/}K$; then $q$ is a positive probability vector.

Suppose $m\ge 2$. Full support gives $0<p_i<1$, so [F8] and [F9] give $-{\log }_2{p}_i>0$. By [F12], ${\mathrm{\ell }}_i=\lceil -{\log }_2{p}_i\rceil$ is a positive integer and ${\mathrm{\ell }}_i\ge -{\log }_2{p}_i$. Thus ${\log }_2(2^{-{\mathrm{\ell }}_i})=-{\mathrm{\ell }}_i\le {\log }_2{p}_i$ by [F11]; since ${\log }_2$ is strictly increasing by [F8] and [F9], this gives $2^{-{\mathrm{\ell }}_i}\le p_i$ and hence ${\sum }_i{2}^{-{\mathrm{\ell }}_i}\le 1$. By [F6] there is a binary prefix code with these lengths.

By [F2], [F3], [F5], [F7], [F8], and [F10], using the logarithm product and quotient laws for the integer powers in $q_i$, $0\le D(p\mathrm{\parallel }q)={\sum }_i{p}_i\ln (p_i\mathrm{/}{q}_i)=-H(p)+(\ln 2)L_p(C)+\ln K$. Since $K\le 1$, [F9] gives $\ln K\le 0$, so $H(p)\le (\ln 2)L_p(C)+\ln K\le (\ln 2)L_p(C)$. Divide by $\ln 2>0$ from [F8] and use [F2] to obtain $H_2(p)\le L_p(C)$.

By [F12] and [F13], if $m_a=\lfloor -a\rfloor$ then $m_a\le -a<m_a+1$, so $a\le -m_a=\lceil a\rceil <a+1$. Therefore the Shannon code in step 1.2 satisfies $L_p(C)={\sum }_i{p}_i\lceil -{\log }_2{p}_i\rceil <{\sum }_i{p}_i(-{\log }_2{p}_i+1)=H_2(p)+1$. If $m=1$, then $p_1=1$ by [F1], so $H_2(p)=0$ by [F2] and [F8]–[F9]; the codeword $0$ is a prefix code of length one.

If $m=1$, the algorithm returns $0$ by [F7]. Every codeword is nonempty by [F3], so every one-symbol code has expected length at least $1$; the returned code is prefix-free by [F2] and attains that value.

Suppose $m\ge 2$. Every merge removes two nodes and adds one, so the active count decreases by exactly one; after $m-1$ merges there is one root. Each original symbol remains one leaf, and the only new nodes are internal parents by [F6]. Distinct leaves cannot lie on one root-to-leaf path, so their path words are distinct and neither is a prefix of another. Every path has positive length because the root is internal. Thus [F2] gives a binary prefix code.

An optimal prefix code exists. For every integer $m\ge 1$, $m\le 2^m$ by induction: it holds at $m=1$, and $2^{m+1}\ge 2m\ge m+1$. Thus [F4] applied to the length list $(m,\dots ,m)$ gives a finite prefix code, since its Kraft sum $m{2}^{-m}\le 1$; let its cost be $L_0$. Any code with cost at most $L_0$ has $1\le {\mathrm{\ell }}_i\le L_0\mathrm{/}{p}_i$ for every $i$, because $p_i>0$ and all summands in $L_p$ are nonnegative. Only finitely many positive integer length vectors satisfy these bounds, and at least one is realized. A least cost among those realized vectors exists and is a global minimum because every code outside the set has cost greater than $L_0$.

For an active list of size two and total weight one, the algorithm merges its two nodes into a root with two leaves, giving lengths $1,1$ and cost $1$. Every binary source code has nonempty words by [F3], so every competing prefix code has both lengths at least one and cost at least the sum of the weights, namely $1$ by [F1]. Thus the size-two case is optimal.

Suppose the active list has size $m\ge 3$ and assume as induction hypothesis that every sequence of minimum-weight merges on a positive normalized list of size $m-1$ with distinct serials gives an optimal code.

In an optimal code tree, no internal vertex has exactly one child: contracting its sole edge preserves the leaves and their incomparability, so [F2] still gives a prefix code, while every codeword below the vertex loses one bit. At least one symbol is below it by the trie definition, and its positive weight by [F1] makes the expected length strictly smaller, a contradiction. Hence every internal vertex has two children. Choose a leaf of maximal depth $d$. Its sibling cannot be internal, since that sibling would have a descendant leaf deeper than $d$; it is therefore another leaf at depth $d$.

The first selected pair $a,b$ gives a reduced list of size $m-1$ with positive weights summing to one and distinct serials. Its subsequent merges are minimum-weight choices by [F5] and [F6]. The induction hypothesis in step 1.5 therefore makes the reduced tree optimal for its weights.

Let $a,b$ be the two symbols selected by the algorithm for its first merge; [F5] and [F6] make them two symbols of least weight. Place them at a sibling pair of leaves at depth $d$ without increasing cost. If $a$ is currently at depth $e\le d$ and a symbol $x$ of weight $p_x\ge p_a$ occupies the chosen depth-$d$ leaf, swapping them changes the two cost terms from $p_{a}e+p_{x}d$ to $p_{a}d+p_{x}e$, a difference $(p_a-p_x)(d-e)\le 0$. Then place $b$ in the sibling leaf by the same calculation, since its current occupant has weight at least $p_b$. Relabeling leaves preserves the prefix property; the original code was optimal, so the resulting code is still optimal.

Contract the two sibling leaves labeled $a,b$ to one leaf $z$ with weight $p_z=p_a+p_b$. The contracted tree is a prefix code on the reduced alphabet and its cost is the original cost minus $p_a+p_b$, since both leaf depths decrease by one. Conversely, expanding any reduced prefix code by replacing the codeword for $z$ with its two children labeled $a,b$ preserves the prefix property and increases cost by $p_a+p_b$. Therefore contraction sends an optimal original code to an optimal reduced code, and expanding an optimal reduced code gives an optimal original code.

By step 4.1, expansion of that reduced tree is optimal for the original weights. The algorithm terminates and returns a prefix code by step 1.2; the base case step 1.4 and the induction step prove its optimality for every $m\ge 2$.

Take the expectation of the pointwise inequality in [F1] under $p^n$; finite summation gives $\mathbb{E}[\mathrm{\ell }(X^n)]\le \mathbb{E}[-{\log }_2{p}^n(X^n)]+2$.

By [F2], [F4], and [F5], $-{\log }_2{p}^n(X^n)={\sum }_{t=1}^n-{\log }_2{p}_{X_t}$. For each coordinate $t$, summing $p^n$ over blocks with $x_t=i$ gives $p_i({\sum }_j{p}_j{)}^{n-1}=p_i$, so $X_t$ has law $p$. Linearity of the finite expectation and [F3] then give $\mathbb{E}[-{\log }_2{p}^n(X^n)]={\sum }_{t=1}^n{H}_2(p)=n{H}_2(p)$. Substitute in step 1.1.

After $t$ symbols, the scaled interval for the prefix is $[L,L+W{Q}^{n-t})$. At $t=0$ it is $[0,Q^n)$, so the claim holds. If it holds at $t-1$, symbol $i$ occupies the subinterval beginning $W{c}_i{Q}^{n-t}$ after the parent lower endpoint and of width $W{q}_i{Q}^{n-t}$; the widths sum to the parent width because ${\sum }_i{q}_i=Q$. Thus the update [F3] gives the claimed child interval. At $t=n$ it is $[L,L+W)$ with $W={\prod }_{t=1}^n{q}_{x_t}$, so after division by $D=Q^n$ its width is $W\mathrm{/}D=p^n(x^n)>0$ by [F1].

The search in [F3] finds $u$ with $2^{u}W\le D<2^{u+1}W$: $j=0$ is admissible since $W\le Q^n$, and $D\mathrm{/}W\le Q^n\le 2^B$, so the largest admissible $u$ is at most $B$. Hence $2^{-(u+1)}<W\mathrm{/}D\le 2^{-u}$. The selected dyadic cell has width $\delta =2^{-(u+2)}<W\mathrm{/}(2D)$. Its index $k$ is the floor of $2^s$ times the interval midpoint $(2L+W)\mathrm{/}(2D)$; therefore the cell contains that midpoint and extends by at most $\delta$ to either side. Since $\delta$ is smaller than half the source-interval width, the cell lies inside the source interval. Also the midpoint is in $[0,1)$, so [F7] gives $0\le k<2^s$ and its $s$-bit representation exists.

Length-$n$ source intervals partition $[0,1)$ by step 1.1, and step 2.1 places each nonempty emitted dyadic cell inside its own interval. Thus cells for distinct blocks are disjoint. A proper-prefix relation between emitted words would make one dyadic cell contain the other, which contradicts disjointness. The codewords are distinct and prefix-free by [F2]. A trie leaf therefore identifies one block, so the decoder returns exactly the encoded block.

Since $2^u\le D\mathrm{/}W$, [F4], [F5], and [F6] give $u={\log }_2(2^u)\le {\log }_2(D\mathrm{/}W)$; [F4] and [F8] give ${\log }_2(D\mathrm{/}W)=-{\log }_2(W\mathrm{/}D)=-{\log }_2{p}^n(x^n)$ by step 1.1. Thus the payload length $s=u+2$ is at most $-{\log }_2{p}^n(x^n)+2$. Also $W\ge 1$ and $D\le Q^N\le 2^B$, so $u\le B$ and $s\le B+2$. At configuration, computing $P=Q^N$ takes $N$ multiplications. The doubling loop for $B$ terminates because $2^P\ge P$ for every positive integer $P$ (by induction), and its first $B$ with $2^B\ge P$ is least. The encoder performs $n$ updates, tests at most $B+1$ values of $j$, and emits at most $B+2$ bits; the decoder's trie traversal reads at most that many bits and outputs $n$ symbols. Since $N\ge 1$, $Q\le Q^N\le 2^B$, so each $q_i$ and $c_i$ fits its $B+1$-bit register; also $L,W,D\le 2^B$, so their $B+1$-bit registers suffice. By [F9], if $b_N=\lceil {\log }_2(N+1)\rceil$ and $b_B=\lceil {\log }_2(B+3)\rceil$, then $b_N\ge {\log }_2(N+1)$ and $b_B\ge {\log }_2(B+3)$. Applying the increasing logarithm facts [F4]–[F6] gives $2^{b_N}\ge N+1$ and $2^{b_B}\ge B+3$, so the counters hold counts up to $N$ and output lengths up to $B+2$. By [F10], the numerator $2^s(2L+W)$ is at most $2^{B+2}\cdot 3\cdot 2^B<2^{2B+4}$, so the temporary register suffices; the denominator $2D$ and scale $2^s$ also fit it. All other products in the interval update are at most $D$. Hence every loop terminates and no configured per-frame register overflows.