シャノンの第二定理: 情報理論入門 10

信頼のできない通信路を用いて通信を行う際、十分低い誤り率を保ちながら通信できる最大の効率を示すのがシャノンの第二定理、またの名を通信路符号化定理、です。具体的には、一記号あたり $C$（通信路容量）ビットまでであれば、任意に低い誤り率を達成でき、逆に、一記号あたり $C$ ビットよりは多く伝えるのが不可能であるという両方向からの結果を述べたのがシャノンの第二定理です。

問題設定

送信者と受信者はやりとりしたいメッセージのパターン $\mathcal{M} = \{1, 2, \cdots, n\}$ があるとします。

入力記号を $\mathcal{X}$、出力記号を $\mathcal{Y}$、通信路行列を $\mathbf{P} \in \mathbb{R}^{\mathcal{X} \times \mathcal{Y}}$ とする通信路を用いて通信することを考えます。すなわち、この通信路に記号 $x \in \mathcal{X}$ を入力すると、確率 $\mathbf{P}_{xy} = P(Y = y \mid X = x)$ で記号 $y \in \mathcal{Y}$ が出力されます。

符号化関数を $f\colon \mathcal{M} \to \mathcal{X}^k$、復号関数を $g\colon \mathcal{Y}^k \to \mathcal{M}$ とします。送信者がメッセージ $m \in \mathcal{M}$ を送信する際には、$f(m) = x_1, x_2, \cdots, x_k$ と入力記号に符号化し、$x_1, x_2, \cdots, x_k$ を通信路に入力します。受信者は受信記号 $y = y_1, y_2, \cdots, y_k \in \mathcal{Y}^k$ に対して $g(y)$ と復号します。$m = g(y)$ となれば通信成功です。

（メッセージが一様ランダムに選ばれたときに）通信が失敗する確率 $P_{\text{error}} = \frac{1}{n} \sum_{m \in \mathcal{M}} p(m \neq g(y) \mid M = m)$ を小さく保ちつつ、$1$ 通信に必要な記号数 $k$ をできるだけ小さく保つことをめざします。

記法

入力記号の確率変数を $X$ および $X_1, X_2, \cdots, X_n$ で表し、出力記号の確率変数を $Y$ および $Y_1, Y_2, \cdots Y_n$ で表します。通信路容量を $C = \max_{p(X)} I(X; Y)$, 伝送レートを $R = \frac{\log_2 n}{k}$ とします。

シャノンの第二定理

以下にシャノンの第二定理を述べます。

定理: シャノンの第二定理（通信路符号化定理）

1. 任意の $R < C$ と $\varepsilon > 0$ について、伝送レートが $R$ 以上であり誤り率$P_{\text{error}}$ が $\varepsilon$ 以下となるような符号・復号方法 $f, g$ が存在する。

2. 一方、任意の $R > C$ について、ある $\varepsilon > 0$ が存在し、伝送レートが $R$ である任意の符号・復号方法は誤り率 $P_{\text{error}}$ が $\varepsilon$ 以上となる。

つまり、伝送レートが $C$ 未満であれば、工夫をすれば誤り率をいくらでも下げることができ、伝送レートが $C$ より大きければ、どんなに工夫をしても誤り率は一定より下げることができないことを示しています。

証明

1. $R = \frac{\log_2 n}{k} < C$ とする。通信路の入力記号と出力記号の相互情報量 $I(X; Y)$ が最大となる入力記号の分布を $p(X)$ とする。このとき、$I(X; Y) = C$ である。この $p(X)$ および $p(X, Y)$ は、通信路の情報から決定できるので、送信者と受信者はお互い知っている。

各 $m = 1, \cdots, n$ および $i = 1, \cdots, k$ について、$x_{mi}$ を $p(x)$ から独立にサンプリングする。この符号は送信者・受信者で共有する。共有し終わると、通信フェーズに入りお互い情報のやり取りは通信路のみで行うとする。
送信者は送信するメッセージ $m$ を一様ランダムにサンプルし、$f(m) = x_{m1} \cdots x_{mk}$ と符号化して通信路に入力
受信者は $y = y_1 \cdots y_k$ を受信する
受信者は $(f(\hat{m}), y)$ が $p(X, Y)$ の同時代表系列となる $\hat{m}$ が存在するかを調べる。ただ一つ存在したときは、その $\hat{m}$ を復号メッセージとする。そのような $\hat{m}$ が存在しないか、二つ以上存在する場合には、復号を諦める（または当てずっぽうでランダムに復号する。）

このとき、$k$ を十分大きくすると任意に誤り率が小さくなることを示す。

符号化方法およびメッセージのサンプリングが対称なので、一般性を失うことなく $m = 1$ と仮定して誤り率を計算する。

$E_{i}$ を「$f(i)$ と $y$ が同時代表系列となる」という事象とする。$E_1 \cap \bar{E}_2 \cap \cdots \cap \bar{E}_n$ が成り立てば、$y$ と同時代表系列となるのは $f(1)$ のみであるので $\hat{m} = m$ となり通信が成功する。

任意に $\varepsilon >0$ をとる。$\varepsilon’ = (C – R) / 6 > 0$ とおく。

同時漸近的等分配定理より、十分大きい $k$ に対して $$\text{Pr}[E_1] > 1 – \frac{\varepsilon}{2} \tag{1}$$ となる。

また、十分大きい $k$ に対して、$$\begin{align*}\text{Pr}[E_2 \cup \cdots \cup E_n] &\stackrel{\text{(a)}}{\le} (n – 1) 2^{-k(I(X; Y) – 3 \varepsilon’)} \\ &\stackrel{\text{(b)}}{=} (n – 1) 2^{-k(C – 3 \varepsilon’)} \\ &\le n 2^{-k(C – 3 \varepsilon’)} \\ &\stackrel{\text{(c)}}{=} 2^{kR} 2^{-k(C – 3 \varepsilon’)} \\ &= 2^{-k(C – R – 3\varepsilon’)} \\ &\stackrel{\text{(d)}}{=} 2^{-3k\varepsilon’} \\ &\to 0 \quad (\text{as} k \to \infty)\end{align*}$$ ただし、(a) ではブールの不等式と同時漸近的等分配定理を、(b) では $I(X; Y) = C$ を、(c) では $R = \frac{\log_2 n}{k}$を、(d) では $\varepsilon’ = (C – R) / 6$ を用いた。よって、十分大きい $k$ に対して $$\text{Pr}[E_2 \cup \cdots \cup E_n] \le \frac{\varepsilon}{2} \tag{2}$$ となる。よって、式 (1) (2) を合わせて、通信成功確率は $$\text{Pr}[E_1 \cap \bar{E}_2 \cap \cdots \cap \bar{E}_n] > 1 – \varepsilon$$ すなわち、誤り確率を任意に小さくできる。

ここで、今まで符号化方法 $f$ はランダムサンプリングによって決定していた。ランダムな符号化方法の誤り確率が $\varepsilon$ 未満であるということは、少なくとも一つは、誤り確率が $\varepsilon$ 以下である符号化方法が存在するということである。

2. $R = \frac{\log_2 n}{k} > C$ とする。まず、記号を $k$ 個連結した時の相互情報量が単一記号の相互情報量の $k$ 倍を越えないことを示す。$X^k$ を記号 $k$ 個の系列を値にとる確率変数とし、この記号を通信路に入力したときの出力を表す確率変数を $Y^k$ とする。これらの $i$ 番目の値を $X_i, Y_i$ などと表記する。このとき、$$\begin{align*}I(X^k, Y^k) &= \mathbb{E}_{(x, y) \sim p(X^k, Y^k)}\left[ \log \frac{p(Y^k = y \mid X^k = x)}{p(Y^k = y)} \right] \\ &= \mathbb{E}_{(x, y) \sim p(X^k, Y^k)}\left[ \log \frac{\Pi_{i = 1}^k p(Y_i = y_i \mid X_i = x_i)}{p(Y^k = y)} \right] \\ &\stackrel{\text{(a)}}{=} \sum_{i = 1}^k \mathbb{E}[\log p(Y_i \mid X_i)] – \mathbb{E}[\log p(Y^k)] \\ &\stackrel{\text{(b)}}{=} – \sum_{i = 1}^k H(Y_i \mid X_i) + H(Y^k) \\ &\stackrel{\text{(c)}}{\le} – \sum_{i = 1}^k H(Y_i \mid X_i) + \sum_{i = 1}^k H(Y_i) \\&\stackrel{\text{(d)}}{=} \sum_{i = 1}^k I(Y_i; X_i) \\ &\stackrel{\text{(e)}}{=} kI(X; Y) \tag{3} \end{align*}$$ ただし、(a) は対数の性質と期待値の線形性より、(b) はエントロピーの定義より、(c) は同時エントロピーは各変数のエントロピーより小さいという性質より、(d) は相互情報量の定義より従う。(e) では、各記号において入出力は常に $P(Y \mid X)$ に従うということを利用した。

続いて、本題の定理を証明する。一般性を失うことなく、$i \neq j \Rightarrow f(i) \neq f(j)$ と仮定する（単射でない符号化方法で伝送レートを $C$ より大きくしながら誤り率を任意に下げられるなら、同じ符号語に変換されるメッセージを取り除くことで、同じ符号語に符号化しない符号化方法であって、伝送レートを $C$ より大きくしながら誤り率を任意に下げられるものが存在することが示せる。）

$\varepsilon = \frac{R – C}{R} > 0$ とし、 $k \ge \frac{2}{R – C}$ ととる。このとき、$$\begin{align*}P_{\text{error}} &\stackrel{\text{(a)}}{\ge} \frac{H(X^k \mid Y^k) – 1}{\log n} \\ &\stackrel{\text{(b)}}{=}\frac{H(X^k \mid Y^k) – 1}{kR} \\ &\stackrel{\text{(c)}}{=}\frac{H(X^k) – I(X^n; Y^k) – 1}{kR} \\&\stackrel{\text{(d)}}{\ge} \frac{H(X^k) – kC – 1}{kR} \\&\stackrel{\text{(e)}}{=} \frac{kR – kC – 1}{kR} \\&= \frac{R – C}{R} – \frac{1}{kR} \\&\stackrel{\text{(f)}}{\ge} \varepsilon\end{align*}$$ ただし、(a) ではファノの不等式を、(b) は $R = \frac{\log_2 n}{k}$ を、(c) では相互情報量の定義を、(d) では式 (3) を、(e) では各メッセージが一様に選ばれるという事実と、 $$\begin{align*}H(X^k) &= – \frac{1}{n} \sum_{i = 1}^n \log p(X^k = f(i)) \\ &= – \frac{1}{n} \sum_{i = 1}^n \log \frac{1}{n} \\ &= \log n\end{align*}$$ を、(f) では $\varepsilon = \frac{R – C}{R}$ と $k \ge \frac{2}{R – C}$ を用いた。

よって、十分大きい $k$ では誤り率は $\varepsilon$ より下げられないことが示せた。また、小さい $k$ において誤り率を $\varepsilon$ より下げられたとすると、そのような符号化方法を連結することで、任意に大きい $k$ において誤り率を $\varepsilon$ より下げられることになり矛盾する。よって、任意の $k$ について誤り率を $\varepsilon$ より下げられない。