５．通信路

公開状態にしてますが、編集中です。
間違いや表記ゆれがあります。

相互情報量

相互情報量$${I(X;Y)}$$は、X とYの「依存度」を表す指標である。
$${I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y)}$$

関係性を図示すると、以下のようになる。

$${I(X;Y)=H(Y)-H(Y|X)}$$から、
$${H(Y)=H(Y|X)}$$で$${I(X;Y)=0 (\min)}$$
$${H(Y|X)=0}$$で$${I(X;Y)=\max}$$

$${p=0,1}$$で$${I(X;Y)=\max}$$となり、
$${p=0.5}$$で$${I(X;Y)=0}$$となる。

通信容量

通信路が運ぶ情報量である相互情報量$${I(A;B)}$$の最大値をその通信路の通信容量と呼ぶ。

生起確率を$${P(a_j)}$$として、
$${C=\displaystyle\max_{P(a_1)+P(a_2)+ \cdot \cdot \cdot +P(a_j)=1}I(A;B)}$$

2元対称通信路

誤り率$${p}$$の2元対称通信路

通信路行列を考える。

$${T=\begin{pmatrix} 1-p & p \\ p & 1-p \end{pmatrix}}$$

入力確率変数$${X}$$の値が$${x}$$となる確率$${p_x(x)}$$を$${p_x(0)=a ,p_x(1)=1-a}$$としたとき、
通信路容量$${C}$$を求めたい。

通信路容量$${C}$$
→相互情報量$${I(X;Y)=H(Y)-H(Y|X)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)}$$
→条件付きエントロピー$${H(Y|X)=H(Y)-I(X;Y)=H(Y,X)-H(X)}$$
→入出力エントロピー$${H(X),H(Y)}$$

入出力エントロピー

エントロピー$${H(X)}$$は、
$${H(X)=-(p(0)\log p(0)+p(1)\log p(1))}$$
$${=-(a \log a+(1-a)\log (1-a))}$$

次に出力エントロピー$${H(Y)}$$を考える。
式は、$${H(Y)=-(p(y_0)\log p(y_0)+p(y_1)\log p(y_1))}$$となるが、$${p(y_0),p(y_1)}$$はいずれも示されていないので、導出をする必要がある。

図1の2元対称通信路は何を示しているのか？

一度、以下のような通信路線図を考える。
節点は、入出力で有向枝は条件付確率を示している。

入力シンボルは、独立に生起しているから、
出力するシンボル$${b_2}$$の確率$${p(b_2)}$$は、
$${P(b_2)=\displaystyle \sum_{k=1}^i P(a_k)P(b_2|a_k)}$$

要するに、出力$${Y}$$各生起確率を出したいときは、入力の生起確率とそれの枝の本数分（条件付き確率）の和である。

行列式より、$${\bold P(b_k)=\bold P (a_j)\bold T}$$

このことを踏まえて、2元対称通信路を考える。

0となるシンボル$${y_0}$$の生起確率$${P(y_0)}$$は、
$${p(y_0)=p(x_0)p(y_0|x_0)+p(x_1)p(y_0|x_1)}$$
$${=a(1-p)+p(1-a)=a+p-2ap}$$

したがって、$${{H(Y)}=-((a+p-2ap) \log(a+p-2ap)+(1-a-p+2ap) \log(1-a-p+2ap)}$$

条件付エントロピー

$${H(Y|X)=\displaystyle \sum_{j=1}^J P(x_j)(-\displaystyle \sum_{k=1}^Kp(y_k|x_j)\log P(y_k|x_j))}$$

$${H(Y|X)=-\displaystyle \sum_{j=1}^J\displaystyle \sum_{k=1}^Kp(y_k,x_j)\log P(y_k|x_j))}$$  ※結合エントロピーは順不同だが、情報量と合わせると間違わない。

したがって、

$${H(Y|X)=-(p(0,0) \log p(y_0|x_0)+p(0,1) \log p(y_0|x_1)+p(1,0) \log p(y_1|x_0)+p(1,1) \log(y_1|x_1))}$$

$${=-(1-p) \log(1-p)-p \log p}$$

通信路容量

$${C=\displaystyle\max_{P(x_0)+P(x_1)=1}I(X;Y)}$$
は、何を示しているのか？

まず、計算を進める。

$${C=\displaystyle\max_{P(x_0)+P(x_1)=1}(H(Y)-H(Y|X))}$$

前項で計算を省略したが、
$${H(Y|X)=-((1-p) \log(1-p)+p \log p)}$$とpのみの式になる。

通信路容量は、入力シンボルの組み合わせで最大値になる組み合わせ
であることを示している。

したがって、誤り率$${p}$$は定数で、第２項は無視できる。
$${=H(Y)-\displaystyle \sum_{k=1}^Kp(y_k|x_j)\log P(y_k|x_j)}$$

では、$${H(Y)}$$が最大値を取るには？

エントロピーの範囲は、
$${0 \leq H(Y) \leq \log J }$$　($${J}$$は事象数）
であるから、最大値は1である。
したがって、$${C=1-H(Y|X)}$$

$${p(x_0),p(x_1)}$$の組み合わせは、どうすれば良いか？
$${p(x_0)=0.5 ,(p(x_1)=1-p(x_0)=0.5)}$$のとき、$${H(Y)=1}$$

無限に直列につないだ2元対称通信路

大学院試や資格等で出てきそうな問題に取り組む。
前の出力と後ろの入力が直列でつながっている。
（OUT:0→IN0）/（OUT:1→IN1）

2段の2元対称通信路

初めに2段の2元対称通信路をつなげたときを考える。

入力は不変だが、出力は変わる。
要するに、通信路行列が変わることがいえる。

$${\begin{pmatrix} z_0  z_1\end{pmatrix}=\begin{pmatrix} y_0  y_1\end{pmatrix} \bold T}$$
$${\begin{pmatrix} y_0  y_1\end{pmatrix}=\begin{pmatrix} x_0  x_1\end{pmatrix} \bold T}$$
$${\begin{pmatrix} z_0  z_1\end{pmatrix}=\begin{pmatrix} x_0  x_1\end{pmatrix} \bold T^2}$$

したがって、通信路行列の2乗を考えればよい。

1段と同様に、通信路容量を求めると、

$${C_2=\displaystyle\max_{P(x_0)+P(x_1)=1}(H_2(Y)-H_2(Y|X))}$$
$${H_2(Y)=1}$$であるから、$${H_2(Y|X)を計算すればよい。}$$

n段の2元対称通信路

加法的２元通信路

通信路内の誤り源$${S_E}$$が、各時刻に$${E\in\{0,1\}}$$が発生する。
通信路は、入力$${X\in\{0,1\}}$$に対して、出力$${Y\in\{0,1\}}$$。
$${\oplus}$$は、排他的論理和（XOR）を示している。
排他的論理和：「論理演算の一つで、二つの命題のいずれか一方のみが真のときに真、両方真・偽のときは偽となるもの」

$${X=Y=0}$$のとき$${E=0}$$
$${X=Y=1}$$のとき$${E=0}$$
一方で、
$${X=0 \neq Y }$$のとき$${E=1}$$
$${X=1 \neq Y}$$のとき$${E=1}$$
$${\bold {E=1}}$$のとき、$${X \neq X\oplus E =Y }$$で誤りが発生する。

相互情報量$${I(X ;Y)}$$は、
$${I(X;Y)=H(Y)-H(Y|X)}$$
$${=H(Y)-{H(X\oplus E|X)}^※}$$
$${=H(Y)-H(E)}$$

※$${{H(X\oplus E|X)}＝P(X=0)H(E|X=0)+P(X=1)H(1 \oplus E| X=1)}$$
$${X,E}$$は独立しているから、
$${H(E|X=0)=H(E), H(1\oplus E|X=1)=H(1\oplus E)}$$
さらに、$${P(1\oplus E=0)=P(E=1)}$$であるから$${H(1 \oplus E)=H(E)}$$

したがって、通信路容量$${C}$$の導出は入力$${X}$$の確率分布に関して、$${H(Y)}$$を最大にすればよい。

$${X,E}$$が独立だから、$${P_X(0)=P_X(1)=1/2}$$であれば$${E}$$に依らず、$${P_Y(0)=P_Y(1)=1/2}$$となる。$${H(Y)}$$は、最大値1を取るので、
$${C=1-H(E)}$$を得る。

誤り源が無記憶定常情報源

2元対称通信路として考える。$${P(E=1)=p,P(E=0)=1-p}$$

$${H(S_E)=-(p \log p+(1-p) \log (1-p))}$$より、
$${C=1-H(S_E)}$$

誤り源がマルコフ情報源

定常分布において、状態$${s_0,s_1}$$にいる確率を$${\pi_0,\pi_1}$$とする。

$${H(S_E)=\pi_0 H(E|s_0)+\pi_1 H(E|s_1)}$$

$${E=1}$$であるから、エントロピーは、
$${H(E|s_0)=H(0.4)=-0.4 \log(0.4)=0.5288}$$
$${H(E|s_1)=H(0.7)=-0.7 \log(0.7)=0.3602}$$

状態分布$${\pi}$$は、平衡方程式から求める。