第9回 通信路容量

初めに必ず連絡事項を確認してください。

通信路を通る情報の量

概要

解説動画

情報源事象系 (入力の値「0」「1」を事象とする事象系) \(X\) と、入力の値「0」「1」を事象とする事象系 \(Y\) を考える。通信路で変化が起こると、 \(X\) と \(Y\) は異なったものになり、それぞれのエントロピーは図のように表わされる。


このうちの重なり部分、つまり相互情報量が「実質的に通信路を通った情報の量」にあたる。これが多ければ通信路をたくさんの情報が通れる、つまり通信路の性能が良いことになる。
左の三日月 \(H(X|Y)\) は「出力について知っていても入力についてわからないこと」→「通信路を通れなかった情報の量」
右の三日月 \(H(Y|X)\) は「入力について知っていても出力についてわからないこと」→「変化してできたゴミ情報の量」
にあたる。

0が確率 \(\alpha\) で発生する情報源事象系 \(X\) の信号を変化の確率が \(p\) の2元対称通信路 \(T\) に通す場合について、この相互情報量を考えてみる。
\(X\) と \(T\) は以下のように書き下せる。
\( \begin{eqnarray} X&=& \begin{bmatrix} x_0 & x_1 \\ \alpha & 1-\alpha \end{bmatrix} \cdots(1)\\ T&=& \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix} \end{eqnarray} \)

前回の課題3, 4で計算したように、出力が0, 1になる確率は
\( \begin{eqnarray} P_y=&&P_xT\\ =&& \begin{bmatrix} \alpha, & 1-\alpha \end{bmatrix} \begin{bmatrix} 1-p & p \\ p & 1-p \end{bmatrix}\\ =&& \begin{bmatrix} \alpha(1-p)+(1-\alpha)p, & \alpha p+(1-\alpha)(1-p) \end{bmatrix}\\ =&& \begin{bmatrix} p+\alpha-2\alpha p, & 1-p-\alpha+2\alpha p \end{bmatrix} \end{eqnarray} \)

のように計算できるので、出力信号の事象系は
\( Y= \begin{bmatrix} y_0 & y_1 \\ p+\alpha-2\alpha p & 1-p-\alpha+2\alpha p \end{bmatrix} \cdots(2) \)

となる。さらに、 \(X\) と \(Y\) の結合事象系 \(XY\) を考えると、それを構成する事象は
事象 意味
\(x_0,y_0\) 入力が0、出力が0 (変化しない)
\(x_1,y_0\) 入力が1、出力が0 (変化する)
\(x_0,y_1\) 入力が0、出力が1 (変化する)
\(x_1,y_1\) 入力が1、出力が1 (変化しない)
で、入力が0, 1である確率はそれぞれ \(\alpha\) と \(1-\alpha\) で、通信路で変化する確率、しない確率はそれぞれ \(p\) と \(1-p\) なので、結合事象系は以下のようになる。
\( XY= \begin{bmatrix} x_0,y_0 & x_1,y_0 & x_0,y_1 & x_1,y_1 \\ \alpha(1-p) & (1-\alpha)p & \alpha p & (1-\alpha)(1-p) \end{bmatrix} \cdots(3) \)

(1) から
\( H(X)=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha)\cdots(4) \)

(2) から
\( H(Y)=-(p+\alpha-2\alpha p)\log(p+\alpha-2\alpha p)-(1-p-\alpha+2\alpha p)\log(1-p-\alpha+2\alpha p)\cdots(5) \)

(3) から
\( \begin{eqnarray} &&H(XY)\\ =&&-\alpha(1-p)\log\{\alpha(1-p)\}\\ &&-(1-\alpha)p\log\{(1-\alpha)p\}\\ &&-\alpha p\log(\alpha p)\\ &&-(1-\alpha)(1-p)\log\{(1-\alpha)(1-p)\}\\ =&&-\alpha\log\alpha -(1-\alpha)\log(1-\alpha) -p\log p -(1-p)\log(1-p)\cdots(6) \end{eqnarray} \)
となる (計算過程は省略)。

一方、第4回の (6) の関係式
\( H(XY)=H(X)+H(Y)-I(Y,X) \)

を変形すれば
\( I(Y,X)=H(X)+H(Y)-H(XY) \)

という形になる。ここで (4)~(6) の結果の形を使うと
\( \begin{eqnarray} &&I(Y,X)\\ =&&H(X)+H(Y)-H(XY)\\ =&&-\cancel{\alpha\log\alpha}-\cancel{(1-\alpha)\log(1-\alpha)}\\ &&-(p+\alpha-2\alpha p)\log(p+\alpha-2\alpha p)\\ &&-(1-p-\alpha+2\alpha p)\log(1-p-\alpha+2\alpha p)\\ &&-\{-\cancel{\alpha\log\alpha} -\cancel{(1-\alpha)\log(1-\alpha)} -p\log p -(1-p)\log(1-p)\}\\ =&&p\log p+(1-p)\log(1-p)\\ &&-(p+\alpha-2\alpha p)\log(p+\alpha-2\alpha p)\\ &&-(1-p-\alpha+2\alpha p)\log(1-p-\alpha+2\alpha p)\cdots(7) \end{eqnarray} \)
となる。

課題1

入力信号の事象系が \( \begin{eqnarray} X_1&=& \begin{bmatrix} x_0 & x_1 \\ 0.3 & 0.7 \end{bmatrix} \end{eqnarray} \) で、通信路の通信路行列が \( \begin{eqnarray} T&=& \begin{bmatrix} 0.9 & 0.1 \\ 0.1 & 0.9 \end{bmatrix} \end{eqnarray} \) の場合の入力 \(X_1\) と出力 \(Y_1\) の相互情報量を求めよ。ただし、計算結果は四捨五入して小数第二位まで求めること。

課題1ヒント


課題2

入力信号の事象系が \( \begin{eqnarray} X_2&=& \begin{bmatrix} x_0 & x_1 \\ 0.5 & 0.5 \end{bmatrix} \end{eqnarray} \) で、課題1と同じ通信路を通した場合の入力 \(X_2\) と出力 \(Y_2\) の相互情報量を求めよ。ただし、計算結果は四捨五入して小数第二位まで求めること。

課題2ヒント


課題1と課題2の結果を比べると、課題2の方が大きい値になるはず。第2回で見たように、事象系のエントロピーは偏りが少ないほど大きくなる。この結果は、入れてやる \(H(X)\) が大きくなったために通る情報の量も多くなったと解釈できる。

通信路容量

概要

解説動画

課題1, 2で見たように、通信路を通る情報の量 \(I(Y,X)\) は「通信路の性質(上の例では \(p\))」「入れてやる情報の性質(上の例では \(\alpha\))」の両方に左右される。これでは通信路の性能を表わす指標としては使いにくい。
そこで、入力する情報の性質をいろいろ変えて、\(I(Y,X)\) が最大になるときの値を指標として使う。これを通信路容量と呼び、文字 \(C\) で表わす。

(7)式の4つの項のうち、最初の2つの項は \(p\) だけに依存する。第3項と第4項の和は、それらがちょうど同じ値になったとき、つまり
\( p+\alpha-2\alpha p=1-p-\alpha+2\alpha p \)

になったときに最大になる (その理由は(7)式を \(\alpha\) で偏微分すればわかるのだが、ここでは省略する。興味のある人はこちらを参照)。これを変形すれば、結局この条件は
\( \begin{eqnarray} 2\alpha-4\alpha p&=&1-2p\\ 2\alpha(1-2p)&=&1-2p\\ 2\alpha&=&1\\ \alpha&=&\frac{1}{2} \end{eqnarray} \)

となる。\(\alpha\) をこの値にすると、(7)式の第3項の対数の前のカッコの部分 (対数の後のカッコの中も同じ形) は
\( \begin{eqnarray} &&1-p-\frac{1}{2}+2\times\frac{1}{2}p=\frac{1}{2} \end{eqnarray} \)

になり、第4項の対数の前後のカッコの中もこれと同じ値になる。 よって、通信路容量は
\( \begin{eqnarray} C=&&p\log p+(1-p)\log(1-p)-\frac{1}{2}\log\frac{1}{2}-\frac{1}{2}\log\frac{1}{2}\\ =&&p\log p+(1-p)\log(1-p)+1\cdots(8) \end{eqnarray} \)

となる。

課題3

\(p=0.01\) の2元対称通信路の通信路容量 \(C\) の値を求めよ。ただし、計算結果は四捨五入して小数第二位まで求めること。

課題3ヒント

課題4

\(p=0.001\) の2元対称通信路の通信路容量 \(C\) の値を求めよ。ただし、計算結果は四捨五入して小数第二位まで求めること。

課題4ヒント

\(p\) は通信路で変化が起こる確率なので、この値が小さいほど実質的に通る情報の量は多くなる。
つまり、課題4の結果は課題3の結果より大きくなるはず。

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は11/16(土) 正午です。提出によって出席・点数がつきます。