シャノンの無雑音情報源符号化定理

下限については、$l_i$ を任意の接頭符号の長さとすると $\sum_{i=1}^n 2^{-l_i} \le 1$ が成り立つ。$Z=\sum_j 2^{-l_j} \le 1$ として $q_i = 2^{-l_i}/Z$ と定義すると、$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$ となるからである。クラフト・マクミラン構成により、このような長さは常に実際の接頭符号として実現できる（2分木の中でレベルごとに2進文字列を割り当てて符号を構築する）。

天井関数の定義より $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$ を達成する。