香农无噪声信源编码定理

对于下界，设 $l_i$ 为任意前缀码的长度，则 $\sum_{i=1}^n 2^{-l_i} \le 1$ 成立。令 $q_i = 2^{-l_i}/Z$，其中 $Z=\sum_j 2^{-l_j} \le 1$，于是 $q$ 是一个概率分布。由吉布斯不等式，$0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$。由于 $Z \le 1$，故 $\log_2 Z \le 0$，因此 $0 \le -H(X) + L + \log_2 Z \le -H(X) + L$，整理即得 $L \ge H(X)$。

对于上界（可达性），对每个 $i$ 选取 $l_i = \lceil -\log_2 p_i \rceil$（将理想长度向上取整为最近的整数）。这些长度满足克拉夫特不等式，因为 $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$，所以 $\sum_i 2^{-l_i} \le \sum_i p_i = 1$；根据 Kraft–McMillan 构造，这样的长度总能实现为一个真正的前缀码（在二叉树中逐层分配二进制串来构造编码）。

由向上取整的定义，$l_i < -\log_2 p_i + 1$。乘以 $p_i \ge 0$ 并对 $i$ 求和得到 $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$。

结合两部分，这一构造达到了 $H(X) \le L < H(X) + 1$。