第18回　通信路容量

阿坂先生
通信路符号化定理を導き出すために雑音がある通信路では伝送した情報の量が受信側でどのくらい減ってしまうのか求めてみよう。

麦わら君
それって、通信路で発生する誤りの発生確率で計算できるんじゃないですか？誤る確率が0.1だったら、1000ビット送ったら100ビット間違うので伝送できる情報の量は900ビットじゃないですか？

桂香助教
ぶー。違うのよ。なぜ違うのかは後で説明するけれど、伝送できる情報の量は相互情報量から求める必要があるわ。相互情報量I(X;Y)は第8回で説明しているから復習してみてね。ここでは相互情報量の式をもう一度書いてみるわ。

　　　I(X;Y)=H(X)-H(X|Y)　　　　　　　(1)

H(X)は送信側のエントロピー、H(X|Y)はYを受信したときのXのエントロピーになるわ。絵を描くとこんな感じ。

H(X|Y)はYを受信してのXのあいまいさ。つまりXが何であるか予測しているとも言えるわ。Yを受信してXがただ１つに決まるのであればあいまいさはゼロ。つまり、H(X|Y)=0だわね。これを(1)式に代入すれば

　　　I(X;Y)=H(X)

となり、受信側ではH(X)の情報をすべて手に入れることができるという意味になる。H(X|Y)=0ということは誤りビットがないと同じ意味で、通信路で誤りが発生しない（誤り率0)という意味になるわ。

麦わら君
分かりました！じゃあ、H(X|Y)＝H(X)のとき、つまり、Yを受信しても何の情報も得られなくて、送信側のエントロピーH(X)から変わらないという場合はが最悪ですね。つまり、H(X|Y)＝H(X)のときは

　　I(X;Y)=0

になりますね。このときは誤り率が100%？

阿坂先生
惜しいのう。誤り率が100%ということは絶対に間違うということじゃから１が0、0が１とビットと必ず反転するという意味になるのじゃ。だから、結局、ビットを反転させれば誤りなしになる。最悪は誤り率50%のときで、I(X;Y)=0となるのじゃ。どうしてそのような計算になるかは今から求めていくぞぃ。（※）

桂香助教
誤り率0とか１とか0.5のような極端な例の場合を考えたけど、今度は誤り率が0.1の場合を考えてみるわ。1000ビット送ったら100ビット間違える場合よ。

阿坂先生
数字を与えて具体的に計算してみよう。まず、(1)式じゃが

　I(X;Y)=H(X)-H(X|Y)＝H(Y)-H(Y|X)

じゃったな。第8回でこれは解説しておる。　　

桂香助教
ここでは１と０がそれぞれ確率0.5で出力される情報源を考えるわ。そのときのエントロピーH(X)は

H(X)=-∑p(x)log{p(x)} =-0.5log0.5-0.5log0.5=1

H(X)=1、つまり1ビットの情報源よ。

麦わら君
たしか、確率0.5のときがH(X)が一番大きくなるんでしたよね。１が出るか0が出るかが一番あいまいだから。

桂香助教
そのとおりよ。次にH(Y)を求めてみるわ。誤り率0.1として１が０、0が1になってしまう様子を表すと以下の図になるわ。

この図からわかるようにyが１であるか、0であるかの確率は0.5だわね。だからH(Y)も1だわ。

阿坂先生
続いて条件付きエントロピーH(Y|X)を求めてみよう。まず、条件付き確率p(y|x)、つまり、xを送信したときyである確率は

0を送信したとき0を受信する確率　p(0|0)=0.9
0を送信したとき1を受信する確率　p(1|0)=0.1
1を送信したとき1を受信する確率　p(1|1)=0.9
1を送信したとき0を受信する確率　P(1|0)=0.1

になるわ。x=0と固定したときのエントロピーH(Y|x=0)は

H(Y|x=0)=-∑p(y|x=0)log{p(y|x=0)}=-0.1log0.1-0.9*log0.9=0.469

同様にx=1と固定したときのエントロピーH(Y|x=1)は

H(Y|x=1)=-∑p(Y|x=1)log{p(Y|x=1)}=-0.1log0.1-0.9*log0.9=0.469

そして、Xが0.5の確率で１と０がランダムに出力されるので

H(Y|X)=0.5*H(Y|x=0)+0.5*H(Y|x=1)=0.469

になるわ。

阿坂先生
だから、相互情報量I(X;Y)は(1)式より

I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=1-0.469=0.531　　　　　　　(1)

になる。これってどうゆう意味だと思う。

麦わら君
えーと。誤りがない通信路だと１ビットの情報の量を受け取ることができるけど、誤りがあるので0.531ビットの情報の量しか受け取れないってことですか？

桂香助教
そのとおりよ。0.531ビットのことを通信路容量と言うわ。相互情報量との違いは、H(X)を最大にしたときに特別に相互情報量を通信路容量と言うの。この通信路容量は、もし送信側で1000ビット送ると誤りが発生して531ビット分しか受け取れないって意味よ。

阿坂先生
ここで、おかしいと思わないか？誤り率が0.1なので間違えるビットは100ビット。900ビットは正しく伝送できているはずなのに伝送できるのは531ビットしかない。これが冒頭に言ったことじゃ。

麦わら君
あー確かに。計算するとそうなりますね。9割は正しく送れているのに伝送できている情報は半減している。なぜでしょうか？

阿坂先生
実はな、9割当たっていると言っても、実はどのビットが当たっているかがわからないというのがネックなのじゃ。どこかが間違っているか分からないから情報が減ってしまうのじゃ。

桂香助教
でもね、どの桁の情報ビットがあっていて、どの桁が間違っているかが判れば、間違った桁を修正してやれば誤り率は0%になるわ。これは明らかにおかしいわよね。

阿坂先生
もう１つ言っておくと、適当に０と１を1000ビット並べてやっても約半分の500ビット位はマグレで当たるだろうから伝送できる情報ビット数は500ビットというのもおかしいじゃろ。500ビット当たっていてもどの桁があっているのかがわからないと全く役に立たない。

麦わら君
適当に０と１を並べるということは平均して半分だけ正解ということだから誤り率が0.5。だから上の（※）のところで誤り率0.5のときに伝送できる情報の量が0になるんですね。だからあてずっぽうに予測しても意味はなく、結局受け取る情報の量はゼロということか。

阿坂先生
このようにどこが間違ってるかわからないと、1000ビット送ったとき、たった1割の伝送ミスでも、531ビット分の情報しか送れないことになる。これはある特定のビットが正確に送れて、それ以外のビットが不正確に送られたと分けて考えるよりも1000個のビット列全体がダメージを受けて、その結果531ビット分の情報しか受け取れないと考えたほうがしっくりくるかもしれんのぉ。