2 誤りのある通信路

2.1 2元対称通信路

図1のような状況を考える．送信者はメッセージ²を送り， 受信者はそれを受け取る．通信路の途中に雑音源があり，メッセージが変わることがある． こういうことは，結構頻繁に生じる．遠距離の通信，例えば宇宙探査船が惑星の画像を送 る場合，かなりの確率で誤りが生じる．微弱な電波で長距離を伝送するからである．これほど のことはないが，地上内の通信でも誤りの発生確率をゼロにすることはできない．熱雑音 を避けることはできないからである．宇宙線が問題になることもある．

図 1: 誤りのある通信の例．糸電話で通 信しているが，途中ノイズで波が鍋になっている．

これから，誤りのある通信路の理論的な考察を行う．ある程度の式を使うことになるが， 意味さえ分かれば難しいことは何もない．

送信者は，メッセージ$x_i$を送る．もし，アルファベット26文字のいずれかを送るなら ば， $x_0=\mathrm{a},\,x_1=\mathrm{b},\,x_2=\mathrm{c},\,\cdots,\,x_{25}=\mathrm{z}$ と考える．また，0か1のバイナリーデータを送るならば， $x_0=\mathrm{0},\,x_1=\mathrm{1}$である．ここで，送信者が文字$x_i$を送る確率を$p(x_i)$ とする．すると，

$$\sum_i p(x_i)=1$$ (1)

である．送信者は，いずれかの文字を送るので，各々の確率を加えると1になるだけであ る．

メッセージを受け取る受信者の方も同じで，受け取る文字を$y_i$とする．ここでは，受 け取る文字の確率を$p(y_i)$とする．もちろん，いずれかの文字を受け取るので，その和 は1になる．

ここで，文字数が多くなると議論が複雑になるので，もっとも単純な二元対称通信路 (binary symeetric chanel)を考える．これは，図2 のような通信路で以下のように特徴づけられる．

• 通信に使う文字は${0,1}$の2種類である．送信者は，これらの文字のみが送信で きる．受信者は，こらの文字のみを受け取る．これが，二元対称通信路の「二元」という ことを表している．
• 途中で誤りが発生する確率$q$は，$0\to 1$も$1\to 0$も同じである．この場合， 誤りが発生しない;$0\to 0$あるいは$1\to 1$で正しく通信できる確率は$1-q$と なる．これが，二元対称通信路の「対称」ということを表している．

いつでもこのような状況が生じるわけではなく，このような理想的な状況を考える--と いうことを理解しておく必要がある．例えば，'0'あるいは'1'という文字を送ったが，そ れが途中で失われて，受信者には何も届かないこともある．また，'0'を送るときは 90[%]正しく通信ができるが，'1'を送るときには30[%]しか正しく通信できないことも ある．これは対称ではない．

図 2: 二元対称性通信路．送信者，受信 者とも${0,1}$の符号を使う．通信途中で誤りが生じ，符号が入れ替わることがある． 通信途中で誤りが生じる確率は$q$，正しく通信ができる確率$1-q$である．

この2元対称通信路の場合，もっとも「質の悪い」エラーとはどのようなものだろうか? 100[%]の確率($q=1$)で，エラーが起きる場合か? この場合，送られるメッセージと受け取るメッ セージは， $011010\to 100101$のようになる．受信者は，受け取ったメッセージから送っ たメッセージが分かる．'0'と'1'を反転させれば良い．エラーが0[%]の時と同じだけ情 報を受け取ることができる．もっとも「質の悪い」エラーは50[%]の確率($q=0.5$)でエラーが発生 する場合である．この場合，受け取るメッセージはランダムに'0'と'1'が並んだ数列に なり，送信者の送った情報を全く受け取ることができない³．

2.2 結合エントロピーと条件付きエントロピー

2.2.1 確率の定義

これから，誤りがある通信路の理論的な考察を行う．そのために，図 3に示すシステムを考える．このシステムは，送信者 $X$がある 文字$x_i$を送ると，受信者は$y_j$を受け取る．途中，信号にノイズが入り，メッセージ が変化する可能性がある．それぞれの確率(probability)を以下のように定義する．

 		 $p(x_i)$ 送信者が文字$x_i$を送信する確率．

$p(y_i)$ 受信者が文字$y_i$を受け取る確率．


$p(x_i,\,y_i)$ 送信者が$x_i$を送り，受信者が$x_i$を受け取る確率．

注意    $p()$は関数ではない．また，添え字の$i$や$j$は送信/受信順序を表す ものではない．$i$と$j$は文字の区別を行っている．

言うまでもないと思うが，全ての確率を加えると1になる．したがって，先ほど示したそれぞれ の確率は

$$\sum_ip(x_i)=1 \sum_j p(y_j)=1 \sum_i\sum_j p(x_i,y_j)=1$$ (2)

となる．また，

$$p(x_i)=\sum_j p(x_i,y_j) p(y_j)=\sum_i p(x_i,y_j)$$ (3)

という関係も直ちに分かる．

図 3: $X$から$Y$へメッセージを送る場合の確率．$p(x_i)$は送信者が$x_i$を送る 確率．$p(y_j)$は受信者が$y_j$を受け取る確率． $p(x_i,y_j)$は，メッセージ $x_i\to y_i$となる確率．

ここで， $p(x_i,y_j)=p(x_i)p(x_j)$と考える人がいるかもしれない．それは間違いである．次の ような二元対称通信路(図4)を考えれば，明らかである．

1. 誤りが全く生じない場合を考える．送信者が'0'を送れば，受信者は必ず'0'を受 け取る．反対に'1'を送れば，'1'を受け取る．
2. 送信者が'0'および'1'を送る確率は，それぞれ0.5である．すなわち， $p(x=0)=p(x=1)=0.5$となる．
3. 途中で誤りが全く生じないので，受信者が'0'および'1'を受け取る確率はそれぞれ 0.5である．すなわち， $p(y=0)=p(y=1)=0.5$となる．
4. 従って， $p(x=0,y=0)=p(x=1,y=1)=0.5$， $p(x=0,y=1)=p(x=1,y=0)=0$となる．

この場合，明らかに $p(x_i,y_j)=p(x_i)p(x_j)$は成立しない．この関係式が成り立つの は，入出力がお互いに全く無関係の場合のみである．このような通信路は全く役に立たな い!! 2元対称通信路の場合，誤りの確率が$q=0.5$のときである．

図: 通信路の途中で誤りが発生しない2元対称通信路の確率．この場合，明らかに $p(x_i,y_j)\ne p(x_i)p(x_j)$である．

元に戻って，今後のために一般的な2次元対通信路の確立の関係を示しておく．全て，直 感的に理解できる式である．

$$p(x=0)+p(x=1)=1 \qquad p(y=0)+p(y=1)=1$$ (4)

$$p(x=0,y=0)+p(x=0,y=1)+p(x=1,y=0)+p(x=1,y=1)=1$$ (5)

$$p(x=0)=p(x=0,y=0)+p(x=0,y=1) \qquad p(x=1)=p(x=1,y=0)+p(x=1,y=1)$$ (6)

$$p(y=0)=p(x=0,y=0)+p(x=1,y=0) \qquad p(y=1)=p(x=0,y=1)+p(x=1,y=1)$$ (7)

これらの式は，式(2)や式(3)に対応したものである．

2.2.2 システムのエントロピー

神様になった気持ちでシステム全体を見渡して，エントロピー(平均情報量)を考える．こ のシステムを観測することにより得られる情報は，送信者の文字$x_i$と受信者の文字 $y_j$である．送受信が$(x_i,y_j)$となる確率は $p(x_i,y_j)$なので，エントロピー $H(X,Y)$は

$$H(X,Y)=-\sum_i\sum_j p(x_i,y_j)\log_2p(x_i,y_j)$$ (8)

である．これを，結合エントロピーと呼ぶ．また，システムエントロピーと呼ばれること もある．

これは，ある一つの通信を行ったとき，送信/受信の両方の文字を知ることにより，得 ることができる平均情報量である．あるいは，このシステムの通信前の情報の平均的な情 報の曖昧(不確かさ)の度合いを表していると言っても良い．

1回通信を行い，送信/受信の文字を知ることにより，情報が確定する;曖昧さがなくなる． 確率の低い情報ほど大きな情報を得ることができる．確率と情報量の関係は，

$$=-\log_2p$$ (9)

であった．ここで，$p$はその情報が生じる確率である．底の2は大きな意味は無く，他で も良いがバイナリーデータを扱うことが多いので，その方が都合が良い．これから，結合 エントロピーは，得られる情報量の期待値であることが分かる．これは，以前学習したと おり．

2.3 条件付きエントロピー

次に受信者側を考える．この場合でも，受け取る文字に関するエントロピー(平均情報量 )は，

$$H(Y)=-\sum_j p(y_j)\log_2 p(y_j)$$ (10)

となる．受信者が文字$y_j$を受け取ると，平均的に$H(Y)$の情報を得る．

つぎに，文字$y_j$を受け取ったときに，送信者が送った文字を推定することを考える． 文字$y_j$を受け取ったときに，送信文字$x_i$に関してどれだけの情報を得ることができ るか?--と言う問題である．

いま，受信者が文字'0'を受け取ったとする．このとき，

$$=\frac{p(x=0,y=0)}{p(x=1,y=0)+p(x=0,y=0)}$$ 送信文字が'0'である確率    式(7)を使うと

$$=\frac{p(x=0,y=0)}{p(y=0)}$$ (11)

となる．これを

$$p(x=0\vert y=0)=\frac{p(x=0,y=0)}{p(y=0)}$$ (12)

と表し，条件付き確率と呼ぶ．文字'0'を受け取ったとき，送信文字が'0'である確率であ る．同様に，文字'0'を受け取ったときに，送信文字が'1'である確率は， $p(x=1\vert y=0)=p(x=1,y=0)/p(y=0)$となる．したがって，文字'0'を受け取った場合，入力 文字のあいまいさ(エントロピーあるいは平均情報量)は

$$H(X\vert y=0)=-\sum_i p(x_i\vert y=0)\log_2 p(x_i\vert y=0)$$ (13)

となる． $p(x_i\vert y=0)$は受け取った文字が'0'のとき，送信した文字が$x_i$である確率で ある．

以上のことより，受け取った文字が$y_j$の場合の，送信文字に関するエントロピー$H(X\vert Y)$は

$$H(X\vert Y) =-\sum_j p(y_j)H(X\vert y=y_j)$$ (14)

となる．$p(y_j)$は受け取る文字が$y_j$となる確率である． $H(X\vert y=y_j)$はそのときの エントロピーである．したがって，$H(X\vert Y)$は文字$y_j$を受け取った後の送信文字に関 する平均的なあいまいさ(条件付きエントロピー)となっている．

この式をもう少し変形すると，次のようになる．

$$H(X\vert Y) =-\sum_j p(y_j)H(X\vert y=y_j)$$

$$=-\sum_jp(y_j)\sum_ip(x_i\vert y=y_j)\log_2p(x_i\vert y=y_j)$$

$$=-\sum_i\sum_jp(y_j)\frac{p(x=x_i,y=y_j)}{p(y=y_j)} \log_2\frac{p(x=x_i,y=y_j)}{p(y=y_j)}$$

$$\qquad\qquad p(x=x_i,y=y_j)=p(x_i,y_j),\quad p(y=y_j)=p(y_j)$$

$$=-\sum_i\sum_jp(x_i,y_j)\log_2\frac{p(x_i,y_j)}{p(y_j)}$$

$$=-\sum_i \sum_j p(x_i,y_j)\log_2 p(x_i,y_j) +\sum_i \sum_j p(x_i,y_j)\log_2 p(y_j)$$    右辺第一項は，式(8)より

$$=H(X,\,Y) +\sum_j\left[\sum_i p(x_i,y_j)\right]\log_2 p(y_j)$$    右辺第二項は，式(3)より

$$=H(X,\,Y)+\sum_j p(y_j)\log_2{p(y_j)}$$    右辺第二項は，式(10)より

$$=H(X,\,Y)-H(Y)$$ (15)

これは，出力文字を知った後での，入力文字のあいまいさを表している．

これと全く同じ議論が，逆の場合でも成り立つ⁴．文字$x_i$を送ったとき，受 信者が受け取る文字$y_j$に関するあいまいさでる．式で表すと

$$H(Y\vert X)=H(X,\,Y)-H(X)$$ (16)

となる．ここで，$H(Y\vert X)$は文字を送信した後に受信者が受け取る文字のあいまいさ(条 件付きエントロピー)である．$H(X)$は元々の送信する側の文字のあいまいさである． $H(X,\,Y)$の$X$と$Y$が入れ替わらない理由? これはシステムのエントロピーであり，送 信者側や受信者側とは関係ない，全体に関することである．神様が見ているようなもので， 逆の議論でも関係ない．

2.4 相互情報量

2.4.0.1 定義

文字$y_j$受け取ったとき，送信文字$x_i$について分かったことを考える．文字を受け取る前の受信者が送信文字$x_i$に関して持っているあいまいさ(エントロピー)は，$H(X)$ であった．ここで$y_j$受け取る(観測)とあいまいさは，$H(X\vert Y)$となった．文字$Y_j$を 受け取ることにより，あいまいさが $H(X)\to H(X\vert Y)$と変化した．この変化した量が受け 取った情報量$I(X;Y)$である．したがって，

$$I(X;Y)=H(X)-H(X\vert Y)$$ (17)

である．この$I(X;Y)$を相互情報量と呼ぶ．式(16)と式 (15)から，

$$I(X;Y)=H(X)-H(X\vert Y)=H(Y)-H(Y\vert X)=I(Y;X)$$ (18)

と書き直すことができる．この式の言っていることは少し不思議な感じがする．つぎの2 つが全く同一となる．

• $I(Y;X)$は，文字$x_i$を送った後，受信者が受け取るであろう文字$y_j$のあい まいさの減少を表す．
• $I(X;Y)$は，文字$y_j$を受け取ると，送信者が送ったであろう文字$x_i$のあい まいさの減少を表す．

2.4.0.2 グラフ化

それでは，具体的に$H(X\vert Y)$と$I(X;Y)$をプロットしてみよう．もっ とも単純な2次元対称線路を考える．図5に示すように，送 信者が'0'を送る確率 $p(x_i=0)=\alpha$とし，誤りの確率を$q$とする．

図 5: 一般的な2元対称通信路．送信者が'0'を送る確率を$\alpha$，通信路の途中 で誤りが生じる確率を$q$としている．

式(15)を使うと，

$$H(X\vert Y) = -p(0,0)\log_2\frac{p(0,0)}{p(y=0)}- p(0,1)\log_2\frac{p(0,1)}{p(y=1)}- p(1,0)\log_2\frac{p(1,0)}{p(y=0)}- p(1,1)\log_2\frac{p(1,1)}{p(y=1)}$$

$$=-\alpha(1-q)\log_2\frac{\alpha(1-q)}{\alpha+q-2\alpha q} -\alpha q\log_2\frac{\alpha q}{1-\alpha-q+2\alpha q}$$

$$\qquad-(1-\alpha)q\log\frac{(1-\alpha q)}{\alpha+q-2\alpha q} -(1-\alpha)(1-q)\log_2\frac{(1-\alpha)(1-q)}{1-\alpha-q+2\alpha q}$$ (19)

が得られる．さらに，式(10)を使うと

$$H(X) =-p(x=0)\log_2 p(x=0)-p(x=1)\log_2 p(x=1)$$

$$-\alpha\log_1\alpha-(1-\alpha)\log_2(1-\alpha)$$ (20)

が得られる．以上より，$H(X\vert Y)$と$H(X)$の計算でき，図6 のグラフ(教科書 [1]のp.68の図3.23と同じ)が得られる．

図 6: 2元 対称線路の$H(X\vert Y)$と$I(X;Y)$のグラフ．上向きの凸が$H(X\vert Y)$で，凹が$I(X;Y)$であ る．横軸は通信路のエラーの確率$q$である． $p(x=0)=0.5$の場合である．

図6のグラフから，次のことが分かる．

• 条件付きエントロピー$H(X\vert Y)$は，文字$y_j$を受け取ったときに送信文字$x_i$ のあいまいさを表している．受信者が送信文字を何かの方法で知ったとき;送信文 字が確定したときに得られる平均情報量(エントロピー)と言ってもよい．グラフ より以下のことが分かる．
  • 通信路でのエラーの確率$q$が0または1の時は，条件付きエントロピーは ゼロである．この場合，即座に送信文字は確定できる．したがって，あいまい さは全くない．
  • 通信路でのエラーの確率$q$が0.5のとき，条件付きエントロピーは最大に なる．この場合，文字を受け取っても，全く送信文字の推定ができないか らである．
• 相互情報量$I(X;Y)$は，文字$y_j$を受け取ったときに，送信文字$x_i$に関して 得る情報量である．グラフより以下のことが分かる．
  • 通信路でのエラーの確率$q$が0または1の時は，相互情報量エントは 最大になる．この場合，即座に送信文字は確定できる．したがって，送信 文字に関して多くの情報を得たことになる．
  • 通信路でのエラーの確率$q$が0.5のとき，相互情報量はゼロに なる．この場合，文字を受け取っても，全く送信文字に関する情報を得る ことができないからである．

ホームページ: Yamamoto's laboratory
著者: 山本昌志