Data Compression and Source Coding

Step 1: Represent the code as a tree. Each codeword is a leaf of a $D$-ary tree, and the path from the root spells its symbols. The prefix condition means no codeword is an ancestor of another.

Step 2: Look at the deepest level. Let $l_{\max}$ be the longest codeword length. A codeword at depth $l_i$ has exactly $D^{l_{\max} - l_i}$ descendants at depth $l_{\max}$.

Step 3: The descendant sets are disjoint. If two codewords shared a descendant, one would be an ancestor of the other, violating the prefix condition. There are only $D^{l_{\max}}$ nodes at depth $l_{\max}$, so

$$\sum_i D^{l_{\max} - l_i} \le D^{l_{\max}}$$

Dividing by $D^{l_{\max}}$ gives $\sum_i D^{-l_i} \le 1$.

Step 4 (converse): Greedy construction. Given lengths satisfying the inequality, sort them so $l_1 \le l_2 \le \cdots$. Label the first available node (lexicographically) at depth $l_1$ as codeword 1 and delete its descendants. Then label the first remaining node at depth $l_2$, and so on. The Kraft inequality guarantees a node is always available, and deleting descendants keeps the code prefix-free.

∎

The tree proof needs a deepest level, which an infinite code doesn’t have. Use intervals instead.

Step 1: Codeword to number. Read codeword $y_1 y_2 \cdots y_{l_i}$ as the $D$-ary fraction $0.y_1 y_2 \cdots y_{l_i} = \sum_{j=1}^{l_i} y_j D^{-j}$.

Step 2: Number to interval. The codeword “owns” the interval $\big[0.y_1\cdots y_{l_i},\; 0.y_1 \cdots y_{l_i} + D^{-l_i}\big)$: every real number whose $D$-ary expansion begins with that codeword. Its length is $D^{-l_i}$.

Step 3: Prefix-free means disjoint. Two intervals overlap exactly when one codeword is a prefix of the other. Disjoint subintervals of $[0,1]$ have total length at most 1, so $\sum D^{-l_i} \le 1$.

Step 4 (converse). Sort the lengths increasingly and assign intervals in order from the low end of $[0,1]$. For binary lengths $1, 2, \ldots$ this gives $[0, \frac{1}{2}), [\frac{1}{2}, \frac{3}{4}), \ldots$, i.e. codewords 0, 10, ….

∎

Step 1: Write the gap.

$$L - H_D(X) = \sum p_i l_i - \sum p_i \log_D \frac{1}{p_i} = -\sum p_i \log_D D^{-l_i} + \sum p_i \log_D p_i$$

Step 2: Turn the lengths into a distribution. Let $c = \sum_j D^{-l_j}$ (the Kraft sum) and $r_i = D^{-l_i}/c$, a genuine pmf. Then $D^{-l_i} = c\, r_i$, and

$$L - H = \sum p_i \log_D \frac{p_i}{r_i} - \log_D c = D(p \,\Vert\, r) + \log_D \frac{1}{c}$$

Step 3: Both terms are nonnegative. $D(p \Vert r) \ge 0$ by the information inequality, and $\log_D(1/c) \ge 0$ because $c \le 1$ by Kraft. So $L \ge H$.

Step 4: Equality. Both terms must vanish: $c = 1$ (the whole Kraft budget is spent) and $p = r$, i.e. $p_i = D^{-l_i}$.

∎

Step 1: Shannon lengths are within one of the ideal. Rounding up loses less than one symbol:

$$\log_D \frac{1}{p_i} \le l_i < \log_D \frac{1}{p_i} + 1$$

Step 2: Average. Multiply by $p_i$ and sum: $H_D(X) \le L_{\text{Shannon}} < H_D(X) + 1$.

Step 3: Sandwich. The optimal code is no worse than the Shannon code ($L^* \le L_{\text{Shannon}}$) and no better than the entropy ($L^* \ge H_D$ by the theorem above).

∎

The bound $H \le L^* < H + 1$ holds for any random variable, including the block $(X_1, \ldots, X_n)$:

$$H(X_1, \ldots, X_n) \le \mathbb{E}\, l(X_1, \ldots, X_n) < H(X_1, \ldots, X_n) + 1$$

For i.i.d. keystrokes $H(X_1, \ldots, X_n) = nH(X)$. Divide by $n$.

∎

Upper bound:

$$\mathbb{E}_p l(X) = \sum_x p(x) \left\lceil \log \frac{1}{q(x)} \right\rceil < \sum_x p(x) \left( \log \frac{1}{q(x)} + 1 \right)$$

Insert $1 = \frac{p(x)}{p(x)}$ inside the logarithm and split:

$$= \sum_x p(x) \log \frac{p(x)}{q(x)} + \sum_x p(x) \log \frac{1}{p(x)} + 1 = D(p \,\Vert\, q) + H(p) + 1$$

Lower bound: the same computation with $\lceil y \rceil \ge y$ in place of $\lceil y \rceil < y + 1$.

∎

Step 1: Pass to the $k$-th extension. If $C$ is uniquely decodable, its $k$-th extension $C^k$ (all concatenations of $k$ codewords) is nonsingular: distinct $k$-symbol messages produce distinct pulse strings. The length of a concatenation is the sum of the lengths, $l(x^k) = \sum_{i=1}^k l(x_i)$.

Step 2: The $k$-th power of the Kraft sum is a sum over messages.

$$\left(\sum_{x \in \mathcal{X}} D^{-l(x)}\right)^k = \sum_{x_1, \ldots, x_k} D^{-l(x_1)} \cdots D^{-l(x_k)} = \sum_{x^k \in \mathcal{X}^k} D^{-l(x^k)}$$

Step 3: Group the messages by encoded length. Let $a(m)$ be the number of $k$-symbol messages whose encoding has length $m$. Lengths range from 1 to $k\, l_{\max}$:

$$\sum_{x^k} D^{-l(x^k)} = \sum_{m=1}^{k l_{\max}} a(m) D^{-m}$$

Step 4: Unique decodability caps $a(m)$. There are only $D^m$ pulse strings of length $m$, and nonsingularity says no two messages share one. So $a(m) \le D^m$, and

$$\left(\sum_x D^{-l(x)}\right)^k \le \sum_{m=1}^{k l_{\max}} D^m D^{-m} = k\, l_{\max}$$

Step 5: Take $k$-th roots and let $k \rightarrow \infty$. $\sum_x D^{-l(x)} \le (k l_{\max})^{1/k}$ for every $k$. The right side grows only linearly inside a $k$-th root, so it tends to 1. Hence $\sum D^{-l(x)} \le 1$.

Step 6 (converse). Lengths satisfying Kraft give a prefix code, and every prefix code is uniquely decodable.

∎

Start from any optimal code $C_m$.

Property 1 (swap). Suppose $p_j > p_k$. Swap the codewords of $j$ and $k$ to get $C_m'$:

$$L(C_m') - L(C_m) = p_j l_k + p_k l_j - p_j l_j - p_k l_k = (p_j - p_k)(l_k - l_j)$$

$C_m$ is optimal, so this is $\ge 0$. Since $p_j - p_k > 0$, we need $l_k \ge l_j$.

Property 2 (trim). If the longest codeword were strictly longer than all others, delete its last bit. The result is still prefix-free (no other codeword is that long) and has strictly smaller expected length, contradicting optimality.

Property 3 (rearrange). Every maximal-length codeword has a sibling (the same codeword with its last bit flipped). Otherwise we could trim it as above. Swap codewords among the maximal-length ones, which doesn’t change $\sum p_i l_i$ since they all have the same length, so that the two least likely symbols sit on a sibling pair.

∎

Let $L^*(p)$ and $L^*(p')$ be the optimal expected lengths for $p$ and its reduction $p'$.

Step 1: Expand. Take an optimal code for $p'$. Split the codeword of the merged symbol $p_{m-1} + p_m$ by appending 0 (for $m-1$) and 1 (for $m$). Only those two symbols get one bit longer, so the resulting code for $p$ has

$$L_{\text{exp}}(p) = L^*(p') + p_{m-1} + p_m$$

Step 2: Condense. Take a canonical optimal code for $p$. By the lemma, symbols $m-1$ and $m$ are siblings. Merge them into their parent node, which shortens both by one bit. The resulting code for $p'$ has

$$L_{\text{cond}}(p') = L^*(p) - p_{m-1} - p_m$$

Step 3: Add the two equations.

$$\big(L_{\text{exp}}(p) - L^*(p)\big) + \big(L_{\text{cond}}(p') - L^*(p')\big) = 0$$

Each bracket is $\ge 0$, because no code beats the optimum. Two nonnegative numbers summing to 0 are both 0. So $L_{\text{exp}}(p) = L^*(p)$: expanding an optimal code for the reduction gives an optimal code for the original.

Step 4: Induct. For two symbols the optimal code (0, 1) is obvious. Huffman’s algorithm is exactly repeated reduction followed by repeated expansion, so by induction it is optimal for every $m$. McMillan extends the comparison from prefix codes to all uniquely decodable codes.

∎

Step 1: Truncation stays in the step. Truncating to $l(x)$ bits moves the number down by less than $2^{-l(x)}$. With the chosen length,

$$2^{-l(x)} \le \frac{p(x)}{2} = \bar{F}(x) - F(x-1)$$

The midpoint sits $p(x)/2$ above the bottom of the step, so the truncated value still lies inside $x$‘s step.

Step 2: Codeword as interval. Read the codeword $z_1 \cdots z_l$ as the interval $[0.z_1 \cdots z_l,\; 0.z_1\cdots z_l + 2^{-l})$. The code is prefix-free exactly when these intervals are disjoint (as in the extended Kraft proof).

Step 3: Each interval fits inside its own step. The interval starts in the lower half of the step (at or below the midpoint), and its length $2^{-l(x)}$ is at most half the step’s height. So it ends below the top of the step. Steps of different symbols are disjoint, hence so are the intervals.

∎

Step 1: Remove the ceiling. $l(X) < \log \frac{1}{p(X)} + 1$, so

$$\Pr\big(l(X) \ge l'(X) + c\big) \le \Pr\left(\log \frac{1}{p(X)} \ge l'(X) + c - 1\right) = \Pr\big(p(X) \le 2^{-l'(X) - c + 1}\big)$$

Step 2: Bound the probability of those symbols. Sum $p(x)$ over the symbols where the condition holds, and use the condition itself as the bound on each term:

$$\sum_{x:\, p(x) \le 2^{-l'(x)-c+1}} p(x) \le \sum_x 2^{-l'(x)} 2^{-(c-1)} \le 2^{-(c-1)}$$

since $\sum_x 2^{-l'(x)} \le 1$ by McMillan.

∎

Step 1: A bound on the sign. On the integers, $\operatorname{sgn}(t) \le 2^t - 1$. Check: at $t = 0$, $0 \le 0$; at $t = 1$, $1 \le 1$; for $t \ge 2$ the right side exceeds 1; for $t \le -1$, $-1 \le 2^t - 1$. (This fails for non-integer $t$, which is why dyadic integer lengths are needed.)

Step 2: Write the score difference as an expectation.

$$\Pr(l' < l) - \Pr(l' > l) = \sum_x p(x)\operatorname{sgn}\big(l(x) - l'(x)\big) \le \sum_x p(x)\big(2^{l(x) - l'(x)} - 1\big)$$

Step 3: Use $p(x) = 2^{-l(x)}$.

$$= \sum_x 2^{-l(x)}\big(2^{l(x) - l'(x)} - 1\big) = \sum_x 2^{-l'(x)} - \sum_x 2^{-l(x)} = \sum_x 2^{-l'(x)} - 1 \le 0$$

by McMillan for $l'$ (and because the dyadic Shannon code spends its Kraft budget exactly).

Step 4: Equality. Step 1 is tight only at $t \in \{0, 1\}$, and Step 3 only if $l'$ spends its Kraft budget exactly. Together these force $l' = l$.

∎

Step 1: Label every leaf distinctly to get $Y$. By the lemma, $\mathbb{E}T = H(Y)$.

Step 2: $X$ is a deterministic function of $Y$ (several leaves can carry the same label). A function can’t increase entropy: $H(Y) = H(Y, X) = H(X) + H(Y \mid X) \ge H(X)$, using the chain rule.

Step 3: Hence $\mathbb{E}T = H(Y) \ge H(X)$.

∎

For dyadic $p$, the Huffman code equals the Shannon code. The leaf for $x$ sits at depth $\log \frac{1}{p(x)}$, so it is reached with probability exactly $p(x)$. The expected depth is the expected codeword length, which is $H(X)$ for a dyadic distribution.

∎

Step 1: Expected depth from atoms. Let $Y$ range over the atoms. Then $\mathbb{E}T = H(Y) = \sum_i T_i$, where $T_i = \sum_{j:\, p_i^{(j)} > 0} j\, 2^{-j}$ collects the atoms of symbol $i$ (an atom at depth $j$ contributes $j 2^{-j}$).

Step 2: Locate $p_i$. Pick $n$ with $2^{-(n-1)} > p_i \ge 2^{-n}$, i.e. $n - 1 < -\log p_i \le n$. Then the first atom of $p_i$ is at depth $n$, and all its atoms are at depth $\ge n$.

Step 3: Show $T_i < -p_i \log p_i + 2p_i$. Using $p_i \log p_i < -(n-1)p_i$ and $p_i = \sum_j 2^{-j}$ over its atoms,

$$T_i + p_i \log p_i - 2p_i < T_i - (n+1)p_i = \sum_{j:\, p_i^{(j)} > 0} (j - n - 1) 2^{-j}$$

The depth-$n$ atom contributes $-2^{-n}$, depth $n+1$ contributes 0, and the rest contribute at most $\sum_{k \ge 1} k\, 2^{-(k+n+1)} = 2^{-(n+1)} \cdot 2 = 2^{-n}$. So the total is $\le 0$.

Step 4: Sum over symbols. $\mathbb{E}T = \sum_i T_i < -\sum_i p_i \log p_i + 2\sum_i p_i = H(X) + 2$.