情報伝送速度
情報伝送速度とは、１秒当たりにノイズのある通信路を通じて正確に伝送される平均情報量です。情報伝送速度 $R$ は、通信記号を毎秒 $ 個送る場合、離散系通信路において、相互情報量 $I(X; Y)$ により以下で定義されます。
$$R = rI(X; Y)$$$$R\text{[bit/s]} = r\text{[symbol/s]}\times I(X; Y) \text{[bit/symbol]}$$
相互情報量
相互情報量（Mutual information）とは、受信信号 $Y$ を観測することによって得られる、送信信号 $X$ に関する平均情報量（不確実性の減少量）です。相互情報量 $I(X; Y)$ は以下で定義されます。
$$I(X; Y) = H(X) – H(X\vert{}Y)$$$$I(X; Y) = H(Y) – H(Y\vert{}X)$$
ここでエントロピーは以下で定義されます。
- 送信側の事前エントロピー $H(X)$
送信データが持つ平均的な情報量（不確実性）です。$$H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)$$ - 受信側の事前エントロピー $H(Y)$
受信データが持つ平均的な情報量です。$$H(Y) = -\sum_{j=1}^{m} p(y_j) \log_2 p(y_j)$$ - 条件付きエントロピー（あいまい度 / 追補度）
受信信号 $Y$ を得た後に、なお残る送信信号 $X$ についての不確実性（あいまい度）を $H(X\vert{}Y)$、逆に $X$ を知った上での $Y$ の不確実性（雑音度）を $H(Y\vert{}X)$ と表します。$$H(X\vert{}Y) = -\sum_{i=1}^{n} \sum_{j=1}^{m} p(x_i, y_j) \log_2 p(x_i \vert{} y_j)$$$$H(Y\vert{}X) = -\sum_{i=1}^{n} \sum_{j=1}^{m} p(x_i, y_j) \log_2 p(y_j \vert{} x_i)$$ノイズのない通信路であれば、受信した $Y$ から $X$ が完全に分かるので、$$H(X|Y)=0$$逆に、$X$ と $Y$ が全く関係なければ、$$H(X|Y)=H(X)$$
条件付きエントロピーの導出
条件付きエントロピー $H(X\vert{}Y)$ の定義式は、受信信号 $Y = y_j$ が具体的に得られたときの送信信号 $X$ の条件付きエントロピーの期待値（平均）をとることで導出できます。
受信信号が特定の条件 $Y = y_j$ に固定されたとき、送信信号 $X$ の条件付き確率分布は $p(x_i \vert{} y_j)$ となります。この条件下での $X$ の平均情報量（エントロピー） $H(X \vert{} Y = y_j)$ は、エントロピーの定義により以下のように書けます。
$$H(X \vert{} Y = y_j) = -\sum_{i=1}^{n} p(x_i \vert{} y_j) \log_2 p(x_i \vert{} y_j)$$
実際の通信では、$Y$ の値自体も確率 $p(y_j)$ に従って変動します。そのため、全体としての条件付きエントロピー $H(X\vert{}Y)$ を得るには、すべての $y_j$ について $p(y_j)$ による重み付け平均（期待値）をとります。
$$H(X\vert{}Y) = \sum_{j=1}^{m} p(y_j) \cdot H(X \vert{} Y = y_j)$$$$= \sum_{j=1}^{m} p(y_j) \Big( -\sum_{i=1}^{n} p(x_i \vert{} y_j) \log_2 p(x_i \vert{} y_j) \Big)$$$$= -\sum_{i=1}^{n} \sum_{j=1}^{m} p(x_i, y_j) \log_2 p(x_i \vert{} y_j)$$
最後は以下の乗法定理を使っています。
$$p(x_i, y_j) = p(y_j) p(x_i \vert{} y_j)$$
結合エントロピー
結合エントロピー $H(X, Y)$ とは、2つの確率変数 $X$ と $Y$ が同時に起こるシステム全体が持っている全体の不確実性（平均情報量）を表す指標です。
離散確率変数 $X \in \{x_1, \dots, x_n\}$ と $Y \in \{y_1, \dots, y_m\}$ に対し、同時に生じる確率（結合確率）を $p(x_i, y_j)$ とするとき、以下のように定義されます。
$$H(X, Y) = -\sum_{i=1}^{n} \sum_{j=1}^{m} p(x_i, y_j) \log_2 p(x_i, y_j)$$
結合エントロピーの主な特徴は以下になります。
- 独立な場合（最大値）
$X$ と $Y$ が互いに全く無関係（独立）である場合、全体の不確実性はそれぞれの不確実性の単なる足し算になります。$$H(X, Y) = H(X) + H(Y)$$ - 依存関係がある場合
$X$ と $Y$ の間に関連性（情報共有）がある場合、全体の情報量は個々の和よりも小さくなります（加法性・劣加法性）。$$H(X, Y) \le H(X) + H(Y)$$ - 条件付きエントロピーとの関係（連鎖律）
全体の不確実性は、片方の不確実性とそれを知った後にもう片方に残る不確実性の和で表せます。$$H(X, Y) = H(X) + H(Y\vert{}X) = H(Y) + H(X\vert{}Y)$$ - 相互情報量 $I(X; Y)$ との関係
結合エントロピーを用いると、相互情報量は個別の不確実性の和から、重複している全体の情報量を引いたものとして表されます。$$I(X; Y) = H(X) + H(Y) – H(X, Y)$$
通信路容量
通信路容量（channel capacity）とは、与えられた通信路特性 $p(y\vert{}x)$ のもとで、送信確率分布 $p(x)$ を最も効率的に選んだ（相互情報量を最大化した）ときの限界値（理論的に達成可能な最大の情報量）です。
$$C = \max_{p(x)} I(X; Y) = \max_{p(x)} \left( H(X) – H(X\vert{}Y) \right)$$
例：二元対称通信路（BSC）
誤り率が $p$（$0 \le p \le 1$）である二元対称通信路の場合、以下の関係があります。
- 条件付きエントロピー（あいまい度）：$$H(Y\vert{}X) = h(p) = -p \log_2 p – (1-p) \log_2 (1-p)$$
- 相互情報量（情報伝送速度）：
送信した情報量からノイズによる不確実性を引いたもの$$I(X; Y) = H(Y) – h(p)$$ - 通信路容量（情報伝送速度の上限値）：
$H(Y) \le 1$ であり、送信確率分布を等確率 $p(x_0) = p(x_1) = 0.5$ にしたときに $H(Y) = 1$（最大）となるため、$$C = 1 – h(p) = 1 + p \log_2 p + (1-p) \log_2 (1-p) \quad \text{[bit/symbol]}$$
