第19回　通信路符号化定理

阿坂先生
前回は信号の誤り率が0.1の場合の通信路容量Cは0.531であることを説明した。これは1000個の１と０を伝送したら531ビット分の情報をほぼ誤りなしで伝送できるという意味じゃった。

桂香助教
伝送信号の長さnと伝送ビットの数kとの比Rを符号化率と呼ぶわ。R=k/nよ。上記ではR=531/1000=0.531。ここでは通信路容量Cと同じに設定したのよ。つまり、R＝Cよ。

阿坂先生
シャノンはRが通信路容量Cよりも小さければ誤り率をどこまでも小さくして情報を伝達できることを発見したのじゃ。これを通信路符号化定理と呼ぶぞぃ。

麦わら君
つまり、R＜Cなら誤り率がゼロで伝送できるってことですか。

阿坂先生
厳密にはゼロではなく限りなくゼロじゃがな。まぁとりあえずはゼロと考えても良いぞぃ。

桂香助教
今回は今まで勉強してきたものをそのまま使えるようにR=C=531として、伝送信号の長さnを1000として情報ビット数k=531の伝送を考えてみるわ。

阿坂先生
この531ビット分の情報をどうやって1000個の1と０の信号に載せてやればよいかを考えてみるのじゃ。

麦わら君
どうやって1000ビット中の531ビット分の情報を詰め込むのか気になっていました。前々回に勉強した3連送符号では1000/3≒333ビット分しか送れないのに誤り率が0にはなりません。

桂香助教
もっとうまいやり方があるってこと。考え方のヒントとしては3連送符号では3つの０と１を使って１ビットを送っていたけど、そうではなくて531ビットを1000個の信号全体に拡散させて送信すると性能が上がるのよ。

麦わら君
言っていることはなんとなくわかりますが、具体的にどうすればよいか見えません。

阿坂先生
この伝送法は、誤り率が0.1の通信路は通信容量が0.531なので、1000ビットを送るのを諦めて531ビットを送るんじゃったな。ここで、1000個の１と０の信号系列のパターンは

の2の1000乗のパターンがあるな。

そして、531ビット送るには、この2の1000乗のパターンの中から2の531乗個選ぶんじゃ。531個じゃないぞぃ、2の531乗個じゃ。531個だったらたったの9ビット(log531)の情報伝送じゃからな。ここでは、2の531乗個の点はランダムで選ぶとしておこう。

桂香助教
いちおう言っておくけど、上記のパターンは物凄い数よ。2の1000乗は約10の301乗よ。2の531乗は10の160乗位。どっちも途方もない大きな数だけど、2の531乗は2の1000乗に比べたら微々たる数であることに注意。

阿坂先生
そして、「531ビットの情報」とそれぞれに対応する「1000個の１と0との信号」（これを符号語という。）との関係を表にして送信側と受信側で共有しておく。ある531ビットの情報（2の531乗個）が2の1000乗の信号列のどこに対応しているか受信側で分かれば通信できると言うわけじゃ。

麦わら君
なるほど、これで531ビットが1000ビットに拡張されたんですね。この1000ビットが符号語という訳ですね。

桂香助教
送信側は符号語を送るんだけど、受信側では通信路で発生した誤りのために受信するのは符号語そのものを受信できないわ。誤り率が0.1なので10%の誤りが発生するわ。つまり1000個中の100個誤るってこと。

阿坂先生
1000個の1と0の信号列ついて、100個だけ違う符号語のパターン数ってどの位あるのかのぉ？

麦わら君
1000個のうち100個違う。計算はコンビネーションですね。100C1000ですね。

桂香助教
この計算は約10の139乗≒２の461乗になり、2の461乗個の符号語の誤りパターンがあるということ。

阿坂先生
符号語が2の531乗のパターンあって、誤りがあるパターンが符号語１つに対して2の461乗個あることになる。だから、誤りのある受信符号語は全部で

じゃ。このように、ほぼきれいに1000ビット分使い切るんじゃ。

桂香助教
符号語と誤り符号語のイメージはこんな感じよ。2の531乗個の黒丸の符号語を選んでやれば、誤り符号語は灰色丸になる。この灰色丸に含まれる総パターンは2の1000乗個になって、もとの２の1000個のパターンを埋め尽くすことができる。送信する1000個の信号を無駄なく使い切ることができるってことよ。

阿坂先生
受信側では「誤りがある符号語のパターン」と「元の符号語」の関係を把握しておけば、受信した符号語から送信された符号語を決定できる。

麦わら君
気になることがあります。ランダムに黒丸選んだら同じ黒丸が2回選ばれたり、灰色丸が重なることがあるんじゃないですか？

阿坂先生
黒丸が重なる可能性はゼロではない。じゃが、前に桂香助教が言ったようにと符号語のパターン２の531乗は2の1000乗の全パターンと比較して物凄く少ない。だから一致する確率はもめちゃくちゃ小さいぞ。ここでも符号長を1000ではなく10000とかするばもっと確率は小さくなる。
灰色丸が重なるかについては、黒丸の選び方が大事なのは間違いない。じゃが、重ならない組み合わせが存在するのじゃ。ここでは深入りしないでそのような組み合わせがあると理解して欲しいぞぃ。

桂香助教
受信符号語と誤りパターンと照合の他にも、受信符号語と送信符号語を比較して、どの符号語に近いか（似ているか）で送信した符号語を判断する方法もあるね。この復号法を最尤推定という。

麦わら君
イメージ湧きました。誤り率が大きいと誤りがある符号語のパターン数が増えるので灰色丸が大きくなる。そうなると2の1000乗のスペースの中に納まらなくなり、灰色丸に重複がでてくる。こうなると誤りが発生してしまう。逆に誤り率が小さいと灰色丸も小さくなり、スカスカになって2の1000乗のスペースが無駄になる。この場合は伝送するビット数を増やしてもっと黒丸を増やすことでできるってことだね。

桂香助教
そうよ。誤り率0.1の場合でちょうどいいのが531ビットってわけ。

麦わら君
でも、気になることがあります。10%誤りといっても必ず1000個中100個が間違えるのではなく99個のときもあれば、101個のときもあるように、むしろぴったり100個間違えるほうが少ないじゃないですか？

阿坂先生
そう。良いことに気がついたのぉ。そのとおりじゃ。ここで使うのは大数の法則じゃ。符号語の長さをここでは1000としたが、これをどんどん大きくしてやれば符号語長と誤り数の比率はどこまででも10%に近づけることができる。

桂香助教
実際に符号語を作るときは誤り率10%というよりも誤り個数が1000個中100個以下なら大丈夫な符号というものを考えるのよ。100個以下の誤りパターンも考慮した符号を考えるの。あと実用化できるものは符号語長をあまり長くすることはできない。現実的な符号の作り方は次に勉強するわ。

麦わら君
判りました。現実的な符号はちょっと性能が落ちるということですか？

桂香助教
そのとおりよ。理想的な符号は符号語長が無限なのよ。実現できる符号語長は数１０００位で抑える必要があるのよ。

阿坂先生
なお、誤りがあっても間違いを修正できる符号のことを誤り訂正符号というぞぃ。

桂香助教
また、誤り訂正符号では、符号語長を抑えると同時に符号や復号に要する計算量の削減も必要だわ。実用化されている誤り訂正符号では符号長を抑えて計算量も削減する様々な工夫がなされているわ。

麦わら君
ではシャノンの通信路符号化定理は実現できない机上の空論なのですか？

阿坂先生
前に情報源符号化定理というのをやったのを覚えておるか？あちらの方はエントロピーHに漸近できる符号化方式が開発されておるが、通信路符号化定理によりRがCに漸近できる符号化方式はまだ道半ばといってもいいじゃろ。R≒Cを実現目指す符号化方式は日々研究がなされておる。

麦わら君
わかりました。僕もそんな符号を開発してみたいですね。

桂香助教
実用化されていてシャノンの示した限界に近い誤り訂正符号にはターボ符号やLDPC符号などがあるのよ。

阿坂先生
そのような訳で次回からは実用化させれている誤り訂正符号について勉強していこう。ターボ符号やLDPC符号の基本となる符号じゃからきっと役に立つはずじゃ。