情報理論における符号化と復号化

定義¹

アルファベットの集合を$\Sigma$とする。以下のように定義される$f_{n}$を圧縮率^{compression rate}が$0 \lt \alpha \le 1$の符号化関数^{encoding scheme, 符号化}という。

$$f_{n} : \Sigma^{n} \to \left\{ 0, 1 \right\}^{\lfloor \alpha n \rfloor}$$

下のような$g_{n}$を圧縮率が$\alpha$の復号化関数^{decoding scheme, 復号化}という。

$$g_{n} : \left\{ 0, 1 \right\}^{\lfloor \alpha n \rfloor} \to \Sigma^{n}$$

説明

簡単に言うと、圧縮率はアルファベットを2進数にマッピングする時、$0$と$1$の数をアルファベットの数で割ったものである。例えば、$\text{LESSERAFIM} \mapsto 101_{(2)}$のようなマッピングなら、圧縮率は次のようになる。

$$0.3 = \dfrac{3}{10} = \dfrac{\left| \left\{ 1, 0, 1 \right\} \right|}{ \left| \left\{ L, E, S, S, E, R, A, F, I, M \right\} \right| }$$

データ量が多ければ、それを効率的に保存して送信するのが難しくなる。だから、情報理論ではメッセージ$m \in \Sigma^{n}$がどれだけ効率的に圧縮できるかに興味を持つ。効率的と言う言葉は圧縮だけでなく、復元にも含まれている。$m \mapsto 1$のようにマッピングすると非常に効率的に圧縮されるが、この$1$を元のメッセージ$m$に復元するのは不可能である。そのため、$m = g_{n}(f_{n}(m))$を満たす$f_{n}, g_{n}$が存在する最小の$\alpha$を見つけることが、メッセージを効率的に圧縮することに等しい。これは情報理論の父、クロード・シャノンによって数学的に整理された。

• ノイズのないコーディング定理
• ノイズのあるチャンネルのコーディング定理

この記事では、メッセージの効率的な圧縮についてもっとナイーブに説明する。$0$と$1$で構成された長さが$n$のメッセージを送りたい状況を考えよう。メッセージ内で$0$が現れる確率が$p$ならば、$1$が出る確率は$1-p$だ。

大数の法則

$\left\{ X_{i} \right\}_{i=1}^{n}$を互いに独立な確率変数とする。$X_{i}$の平均が$\mu$であれば、任意の$\epsilon \gt 0$に対して次のことが成立する。

$$\lim\limits_{n \to \infty} P\left( \left| \dfrac{1}{n}\sum\limits_{i=1}^{n}X_{i} - \mu \right| \ge \epsilon \right) = 0$$

大数の法則は、試行回数$n$が十分に大きければ、標本平均$\dfrac{1}{n}\sum\limits_{i=1}^{n}X_{i}$が母平均$\mu$に十分近くなることを意味する。これにより、$n$が十分に大きい時、メッセージ内の$0$の数は$np$であり、$1$の数は$n(1-p) = (n - np)$である。$0$と$1$で作ることができるメッセージの場合の数は、$n$の場所から$np$の場所に$0$が入る場合を順番に関係なく選ぶことであり、したがって次のようになる。

$$\dfrac{n!}{(np)! (n-np)!}$$

これらのメッセージに二進法で番号を付けるために必要なビットの数は次のようになる。

$$\begin{equation} \log_{2}\dfrac{n!}{(np)! (n-np)!} \end{equation}$$

スターリングの近似

$$\log_{2} n! \approx n \log_{2} n - n \log_{2}e$$

$(1)$をスターリングの公式で近似すると次のようになる。

$$\begin{align*} & \log_{2} n! - \log_{2}(np)! - \log_{2}(n-np)! \\ &\approx \left( n \log_{2} n - n \log_{2}e \right) - \left( np \log_{2} (np) - np \log_{2}e \right) \\ &\qquad - \left( (n-np) \log_{2} (n-np) - (n-np) \log_{2}e \right) \\ &= n \log_{2} n - {\color{red}\cancel{\color{black}n \log_{2}e}} - np \log_{2} (np) + {\color{green}\cancel{\color{black}np \log_{2}e}} \\ &\qquad - (n-np) \log_{2} (n-np) + ({\color{red}\cancel{\color{black}n}}-{\color{green}\cancel{\color{black}np}}) \log_{2}e \\ &= n \log_{2} n - np \log_{2} n - np \log_{2} p - n\log_{2} n(1-p) + np\log_{2} n(1-p) \\ &= n \log_{2} n - np \log_{2} n - np \log_{2} p \\ &\qquad - n\log_{2} n - n\log_{2}(1-p) + np\log_{2} n + np\log_{2} (1-p) \\ &= - np \log_{2} p - n\log_{2}(1-p) + np\log_{2} (1-p) \\ &= - np \log_{2} p - n(1-p)\log_{2}(1-p) \\ &= n\Big(- p \log_{2} p - (1-p)\log_{2}(1-p) \Big) \end{align*}$$

括弧内の式はエントロピーである。したがって、次を得る。

$$\log_{2}\dfrac{n!}{(np)! (n-np)!} \approx nH(p)$$

したがって、$n$が十分に大きい時、$nH(p)$ビットでコーディングするのが効率的であり、効率的な圧縮率は$H(p) = \dfrac{nH(p)}{n}$である。この結果は、確率変数$X$のエントロピーが、つまり$X$の独立試行によって作られたメッセージの圧縮効率であることを意味する。

一般的に話すと、あるアルファベット$x_{i}$が現れる確率が$p(x_{i})$であれば、メッセージ内でアルファベット$x_{i}$が現れる回数は平均的に$np(x_{i})$である。アルファベットを$k \ge 2$個使って作った長さが$n$のメッセージの数は次のようになる。

$$\dfrac{n!}{\prod\limits_{1\le i \le k}(np(x_{i}))!}$$

これらのメッセージに二進法で番号をつけると、

$$\begin{align*} &\log_{2} \dfrac{n!}{\prod\limits_{1\le i \le k}(np(x_{i}))!} \\ &= \log_{2}n! - \sum\limits_{1\le i \le k}\log_{2}(np(x_{i}))! \\ &\approx \left( n \log_{2} n - n \log_{2}e \right) - \sum\limits_{1\le i \le k}\Big( np(x_{i})\log_{2}(np(x_{i})) - np\log_{2}e \Big) \\ &= - n\sum\limits_{1\le i \le k} p(x_{i})\log_{2}p(x_{i}) \\ &= - nH \end{align*}$$