当てる性質：$D$ の非負性が圧縮の限界を決める

定理 1.5.6（平均符号長の分解 ★★★）

任意の符号 $C$ と情報源の分布 $p$ について

$$(\ln2)\,\bar\ell(C)=H(p)+D(p\,\|\,q_C)-\ln K(C)\tag{1.5.5}$$

が成り立つ。$H(p)=-\sum_xp(x)\ln p(x)$ は情報源のエントロピー（nat）、$q_C$ と $K(C)$ は定義 1.5.3 のものである。

定理 1.5.7（圧縮の下界 ★★★）

一意に復号できる任意の符号 $C$ について

$$\bar\ell(C)\ \ge\ \frac{H(p)}{\ln2}\quad\text{ビット}\tag{1.5.6}$$

が成り立つ。等号はすべての $x$ で $p(x)=2^{-\ell(x)}$ のときに限る。

定理 1.5.8（Shannon 符号 ★★★）

分布 $q$ に対して $\ell(x)=\lceil-\log_2q(x)\rceil$ と長さを選ぶと、Kraft の不等式を満たすので語頭符号が作れる（$q$ に合わせた Shannon 符号）。この符号を、実際には分布 $p$ に従う情報源に使うと

$$\frac{H(p)+D(p\,\|\,q)}{\ln2}\ \le\ \bar\ell\ <\ \frac{H(p)+D(p\,\|\,q)}{\ln2}+1\tag{1.5.7}$$

となる。とくに $q=p$ に合わせれば $H(p)/\ln2\le\bar\ell<H(p)/\ln2+1$ である。

この節の要点

• 平均符号長の分解 $(\ln2)\bar\ell=H(p)+D(p\,\|\,q_C)-\ln K$（式 (1.5.5)）。
• $D\ge0$ と $K\le1$ から、圧縮の下界 $\bar\ell\ge H(p)/\ln2$ ビット。
• 分布を $q$ と取り違えた代価は1記号あたり $D(p\,\|\,q)/\ln2$ ビット。

例題 1.5.3　取り違えの代価をビットで数える ★★★

オリジナル4つの記号 $a,b,c,d$ が確率 $p=(\tfrac12,\tfrac14,\tfrac18,\tfrac18)$ で出る情報源を考える。

1. $H(p)/\ln2$ を求め、符号 (1.5.2)（長さ $1,2,3,3$）の平均符号長と比べよ。
2. 4つの記号に長さ $2$ の符号語を1つずつ割り当てる固定長符号の平均符号長を求め、下界との差が $D(p\,\|\,u)/\ln2$（$u$ は一様分布）に等しいことを確かめよ。
3. 長さを逆順の $(3,3,2,1)$ にした符号の平均符号長を求め、下界との差を相対エントロピーで表せ。