情報源記号をひとつひとつ符号化するのではなく、複数の情報源記号をまとめて符号化するとより効率的に符号化ができます。ひとつひとつ符号化する場合は平均符号長の下界と達成できる値に開きがありましたが、複数の情報源記号をまとめて符号化する場合は下界に任意に近づく符号長を達成できます。この綺麗な定理をシャノンの第一定理、またの名を情報源符号化定理といい、情報理論の最も重要な理論の一つに数えられています。
情報源記号を \mathcal{X} とし、符号アルファベットを \Sigma = \{0, 1\} とします。
情報源からは記号 x \in \mathcal{X} が確率 p(x) で生じるとします。
前章では、各情報源記号 x \in \mathcal{X} に対して符号語 f(x) \in \Sigma^* を割り当てましたが、本章では、n 個の情報源記号に対して符号語を割り当てる方式 f\colon \mathcal{X}^n \to \Sigma^* を考えます。たとえば、n = 3 で情報源から生成された記号列が AABABBAAB \cdots のとき、f(AAB)f(ABB)f(AAB) \cdots というように符号化されます。各記号は i.i.d で生成されるとし、記号列の確率も p という記号を用います。たとえば p(ABB) = p(A)p(B)^2 を表します。
瞬時符号 f\colon \mathcal{X}^n \to \Sigma^* であって、平均符号長 \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|] が小さいものを構築するのが目的です。
n 個の情報源記号をまとめて符号化するとき、\mathcal{X}^n という |\mathcal{X}|^n 個の情報源記号がある情報源を符号化していると考えることもできます。このように、n 個の記号をまとめて一つの記号と考えた情報源をn 次拡大情報源とよびます。
情報源からの系列が i.i.d. であるとき、拡大情報源のエントロピーはもとの情報源の n 倍であることが示せます。
情報源からの系列が i.i.d. であるとき、n 次拡大情報源のエントロピーは H(\mathcal{X}^n, p) = nH(\mathcal{X}, p) となる。
\begin{align*}H(\mathcal{X}^n, p) &\overset{\text{(a)}}{=} – \sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_1 \cdots x_n) \\ &\overset{\text{(b)}}{=} – \sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_1) \cdots p(x_n) \\ &\overset{\text{(c)}}{=} -\sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \sum_{i = 1}^n \log p(x_i) \\ &= – \sum_{i = 1}^n\sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_i) \\ &\overset{\text{(d)}}{=} – \sum_{i = 1}^n \sum_{x_i \in \mathcal{X}} p(x_i) \log p(x_i) \\ &\overset{\text{(e)}}{=} \sum_{i = 1}^n H(\mathcal{X}, p) \\ &= nH(\mathcal{X}, p) \end{align*} ただし、(a) はエントロピーの定義より、(b) は i.i.d. であることより、(c) は \log 関数の性質より, (d) は確率分布の周辺化より、(e) はエントロピーの定義より従う。
いよいよ、シャノンの第一定理を証明します。この定理は、情報源記号をまとめて符号化することで、一記号あたりの平均符号長がエントロピーに任意に近づけることができることを示しています。n 記号まとめて符号化するとき、一つの符号 f(x_1 \cdots x_n) に n 記号分の情報が込められているので、送信する符号アルファベットは一記号あたり \frac{1}{n} |f(x_1 \cdots x_n)| であることに注意してください。
瞬時符号 f\colon \mathcal{X}^n \to \Sigma^* の一記号あたりの平均符号長は \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] \ge H(\mathcal{X}, p) を満たす。逆に、任意の \varepsilon > 0 に対して、正整数 n \in \mathbb{Z}_+ および瞬時符号 f\colon \mathcal{X}^n \to \Sigma^* が存在して、\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] \le H(\mathcal{X}, p) + \varepsilon とできる。
平均符号長の限界定理を拡大情報源 \mathcal{X}^n に適用すると、任意の瞬時符号 f\colon \mathcal{X}^n \to \Sigma^* に対して、\begin{align*}\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] &= \frac{1}{n} \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|]\\ &\ge \frac{1}{n} H(\mathcal{X}^n, p) \\ &= H(\mathcal{X}, p)\end{align*} となる。
一方、n = \text{ceil}\left(\frac{1}{\varepsilon}\right) とし、n 次拡大情報源に対してシャノン・ファノ符号 f を構築すると、\begin{align*}\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] &= \frac{1}{n} \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|] \\ &\le \frac{1}{n} \left(H(\mathcal{X}^n, p) + 1\right) \\ &= \frac{1}{n} \left(nH(\mathcal{X}, p) + 1\right) \\ &= H(\mathcal{X}, p) + \frac{1}{n} \\ &\le H(\mathcal{X}, p) + \varepsilon \end{align*}
- 複数の情報源記号をまとめて符号化することにより、一情報源記号あたりの平均符号長を小さくすることができる
- シャノンの第一定理より、一情報源記号あたりの平均符号長はエントロピーにまで任意に近づけることができる。
