なぜデジタルなのか

情報ってなんだろう

Ｑ．なぜデジタルなのか？
Ａ．コピーミスの確率を限りなく０に近づけることができるから

20世紀最大の技術革命は「デジタル化」ではないだろうか。
今日の我々の生活はデジタルに囲まれている、と言っても過言ではない。
なぜ世の中はここまでデジタル化されたのだろうか。
なぜアナログではいけなかったのだろうか。

もしその気になれば、アナログ電子回路で計算機を作ることも決して不可能ではない。
電圧をそのまま加算、コンデンサーで積分、コイルで微分を行えばよい。
今日普及している電子楽器、デジタルシンセサイザー以前には、アナログシンセサイザーという楽器があった。
どちらも電気で音を作り出すまでは同じだが、デジタルとアナログという方式が異なっているのである。
アナログシンセサイザーのように、ツマミをひねって答を探すアナログ計算機もなかなかオツなものかと思うのだが、
実際世の中で幅を利かせているのはあくまでもデジタル。
今後、アナログが主流になることは無さそうに見える。

数理的な側面から、デジタルの優位性を決定づけたのは「シャノンの通信路符号化定理」であろう。

                                                                                                                                              • -

{* 通信路符号化定理 -- わかりやすい版 *}

通信路容量（単位はビット／シンボル）よりも
遅い速度（単位はビット／秒）で
情報を送信することによって、
いくらでも誤りのない通信が可能になる。

誤り率を無限に小さくするには、
通信速度を一定の比率まで落せば済む。

　・参考：通信路の符号化
　>> http://www.yobology.info/text/channel_coding/channel_coding.htm
　・情報通信のメモ
　>> http://www.yobology.info/index.htm
　　-- 情報理論について懇切丁寧に書かれた、すごいサイト。

                                                                                                                                              • -

{* 通信路符号化定理 -- 正確な表現 *}
　A Mathematical Theory of Communication (By C. E. SHANNON)
　>> http://www.yobology.info/education/documents/shannon1948.pdf

Theorem 11:
Let a discrete channel have the capacity C and a discrete source the entropy per second H.
ある離散的な通信チャネルが許容量Ｃを持ち、ある離散的な情報源が１秒あたりエントロピーＨをもっていたとしよう。
If H <= C there exists a coding system
もし H <= C なら、符号化方法が存在する、
such that the output of the source can be transmitted over the channel
そのチャネルを通じて情報源の出力を伝達できる、
with an arbitrarily small frequency of errors (or an arbitrarily small equivocation).
任意に小さな頻度のエラーでもって（あるいは任意に小さなあいまい度合いで）。
If H > C it is possible to encode the source
もし H > C なら、符号化することが可能だ、
so that the equivocation is less than H - C + ε
そこでのあいまい度合いが H - C + ε よりも小さくなるように、
where ε is arbitrarily small.
ここでεは任意の小さな数だ。
There is no method of encoding which gives an equivocation less than H - C.
あいまい度合いが H - C より小さくなるような符号化方法は存在しない。

                                                                                                                                              • -

シャノンの通信路符号化定理とは、情報伝達時の誤り率について述べたものである。
データをコピーすることを考えたとき、ビデオテープのようなアナログデータでは劣化が避けられない。
一方、DVDのようなデジタルデータは、元と全く同じ完全なコピーが可能だ。
ならば、こういった「誤りの無い完全なコピー」は、デジタルであればいつでも無条件にできるのだろうか。
デジタル電気信号とて物理的な実在である。
途中で雑音（雑電波）を拾うかもしれないし、外で突然雷が鳴り出すかもしれない。
デジタルだからといって、それだけで１００％全く誤りのないコピーができる訳ではないのだ。

デジタル通信で生じる誤りを減らすには、どうすればよいか。
まっさきに思いつく方法とは、同じ信号を繰り返して送る方法だろう。
同じデジタル信号を３回ずつ繰り返して送れば、たとえ１つが間違ったとしても、残りの２つが正しい値を伝達する。
しかし、ごく希に２つ同時に間違う可能性も全く無いと言えない。
そこまで慎重を期すなら、４回、５回、と通信回数を増やしてゆけば、それにつれて誤り率は限りなく０に近づくはずだ。
あるいは、デジタル信号を完全に繰り返さずとも、要所要所に合計値のような確認のための信号を織り交ぜればよい。
確認のための信号の割合を増やせば増やすほど、誤り率は下がるはずだ。

ただ、これだけではデジタルの優位性は明らかではない。
「繰り返せば正確にできる」という事実は、アナログであっても同じだからだ。
アナログ計算機で何回も同じ計算を繰り返して平均をとれば、平均値は「真の値」に限りなく近づくであろう。
デジタルとアナログの違いは、「特定のビットが誤る確率か、真の値からのずれの大きさか」であって、
どちらか一方が絶対的に誤りが少ないというわけではないのだ。

シャノンが深く掘り下げたのは、この点だった。
「果たしてデジタル信号は、繰り返した分だけ、誤り率が下がるのか？」
深い考察の結果、シャノンは「繰り返し回数と誤り率は、反比例しているわけではない」ことを突き止めた。
繰り返し回数を無限に大きくする必要はない。
ある一定の値まで大きくすれば、誤り率を限りなく０に近づけることができる。
この「ある一定の値」というのが、通信路容量と呼ばれている値のことだ。
有限のある一定値までで、誤り率をとことん下げることができるのだから、デジタルはアナログに対して決定的に優位となる。
「有限の一定値」という概念は、アナログでは決して出てこないからだ。

通信路符号化定理が解りずらい理由の１つは、「誤り率が０になる」わけではない、という点にある。
　「いくらでも誤りのない」
　「誤り率を無限に小さくする」
　「あいまい度合いが H - C + ε よりも小さくなるように、ここでεは任意の小さな数だ。」
これらの言い回しは同じことを言っているのだが、どれも奥歯に物がはさまったようですっきりしない。
しかし、確率の世界で「絶対１００％」ということはあり得ない話なのである。
ゼロではなく、非常に高い目標値、例えば誤り率 1/(10^10) 以下といった数字を掲げたとき、
その目標値を達成できるような方法が存在することを定理は述べている。
誤り率０の方法を述べているわけではない。（そんな方法は存在しない）
なので、正確に表現しようとすると、どうしても「限りなく０に近づく」といったすっきりしない表現が入ってしまうのだ。

それでは、肝心の定理の中身はいったいどのようなものだろうか。
正確な内容は情報理論の教科書に譲るとして、ここでは一番おいしいエッセンスだけをつまみ食いすることにする。
通信路符号化定理の説明には、幾つかの斬新なアイデアが登場する。

* アイデアその１：　２つのデジタル信号間の「距離」を考える
いま、１と０だけから成る２つのデジタル信号があったとして、この２つが「どれくらい違っているのか」を数値化したい。
そのため、２つの信号の中で異なっている文字の数を「違いの度合い＝２つの信号間の距離」と考えるのである。
このように定義した距離のことを「ハミング距離」と言う。wikipedia:ハミング距離
例えば 1011101 と 1001001 の間のハミング距離は 2 である。

* アイデアその２：　ビットの長さだけの次元を持つ「メッセージ空間」を考える
ビットの長さが３のデジタル信号は、３次元空間内に置かれた立方体の頂点として表現できる。
３ビット長の２進数デジタル信号は全部で８通り、立方体の頂点の数も８個である。
ということは、４ビット長のデジタル信号は、４次元空間に置かれた立方体の頂点として表現できることになる。
wikipedia:ハミング距離 に４次元立方体の挿絵があるが、こんな感じになる。
さらに演繹を続けて、Ｎビット長のデジタル信号をＮ次元空間に置かれた立方体の頂点と考えるのである。
このＮ次元立方体には、長さＮのデジタル信号の全てが含まれていることになる。

* アイデアその３：　距離の近い方に復号する
もしデジタル信号上に誤りが発生して、１つのビットの値が入れ替わってしまったとする。
入れ替わったデジタル信号は、もとのデジタル信号からハミング距離＝１の範囲内にある。
そこで誤りを除去するために、こんな方法が考えられるだろう。
全てのデジタル信号を、お互いに重ならない「ハミング距離の半径＝１の球」でカバーする。
そして、１つの球の範囲内にある信号は、全て同じメッセージなのだと解釈する。
１ビット違っていてもそれは許容して、球の中心である本来のメッセージに復号するのである。
例えば、長さ３ビットの信号で「ＡかＢかの２択」を送信したければ、
{0,0,0} を「Ａ」に、{1,1,1}を「Ｂ」にあてがっておけばよい。

こうしておけば、たとえ１ビットの誤りが生じても、
「０の数が多い方がＡ」、「１の数が多い方がＢ」という判断によって、元のメッセージを復元することができる。

* 通信路符号化定理の本質
ここまで来れば、通信路符号化定理の本質がわかってくるだろう。
デジタル信号によって誤りなく伝達できるかどうかは、
　「Ｎ次元のメッセージ空間に、ハミング距離一定の球がいくつまで入るか」
という問題だったのだ。

それでは、Ｎ次元メッセージ空間で、半径ｋの球の「体積※」はいくつになるだろうか。
（※より正確には「体積−中心点」、つまり離散的な「表面積」）
これは要するに組み合わせの問題で、Ｎ個の中からｋ個を取り出す組み合わせの数、すなわち
　　N C k = N! / (k!・(N - k!))
となる。

球の体積がわかれば、それとメッセージ空間全体の「ふくらみ具合」から、デジタル信号がメッセージ空間に収まりきるための限界値が求まる。
伝達したいメッセージを最低限、誤り無く表現するために必要なビット数がＮ0ビットだったとしよう。
このメッセージを誤りなく伝達するために、余分にビットを付け加えて全体でＮビットになったとする。
Ｎビットのデジタル信号が取り得る全メッセージの数＝メッセージ空間の広さは、2^N 。
誤りを訂正するために付け加えた、余計な（冗長な）メッセージの数＝メッセージ空間が広がった分は、2^(N - N0) 。
この広がった分が、先の半径ｋの球の体積よりも大きければ、全ての球がメッセージ空間に収まることになる。
つまり、限界値を表す式は
　　 2^(N - N0) >= N! / (k!・(N - k!))
となる。
この式に含まれているｋ（許容できるハミング距離の半径）を、平均的な誤り率に置き換えることによって、通信許容量が求められる。

シャノンの通信路符号化定理は、具体的なコーディング方法について述べたものではない。
具体的な方法を示さずとも、「全てのメッセージ空間」と、「その中にデジタル信号がいくつまで入るか」という全体的な視点から、誤りなく伝達できる情報量がわかってしまうのだ。
この洞察には、感動すら覚える。
以上がデジタルの優位性であり、20世紀最大の技術革新と言ってもよいだろう。

もっと深く知りたい人には、これがおすすめ。

ファインマン計算機科学

ファインマン計算機科学

今日から見れば決して最新とは言えないが、情報とは何か、についての深い洞察がある。
上に書いたことは、この本の受け売り。