Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2008-08-07

なぜデジタルなのか

Q.なぜデジタルなのか?

A.コピーミスの確率を限りなく0に近づけることができるから


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.

ある離散的な通信チャネルが許容量Cを持ち、ある離散的な情報源が1秒あたりエントロピー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のようなデジタルデータは、元と全く同じ完全なコピーが可能だ。

ならば、こういった「誤りの無い完全なコピー」は、デジタルであればいつでも無条件にできるのだろうか。

デジタル電気信号とて物理的な実在である。

途中で雑音(雑電波)を拾うかもしれないし、外で突然雷が鳴り出すかもしれない。

デジタルだからといって、それだけで100%全く誤りのないコピーができる訳ではないのだ。


デジタル通信で生じる誤りを減らすには、どうすればよいか。

まっさきに思いつく方法とは、同じ信号を繰り返して送る方法だろう。

同じデジタル信号を3回ずつ繰り返して送れば、たとえ1つが間違ったとしても、残りの2つが正しい値を伝達する。

しかし、ごく希に2つ同時に間違う可能性も全く無いと言えない。

そこまで慎重を期すなら、4回、5回、と通信回数を増やしてゆけば、それにつれて誤り率は限りなく0に近づくはずだ。

あるいは、デジタル信号を完全に繰り返さずとも、要所要所に合計値のような確認のための信号を織り交ぜればよい。

確認のための信号の割合を増やせば増やすほど、誤り率は下がるはずだ。


ただ、これだけではデジタルの優位性は明らかではない。

「繰り返せば正確にできる」という事実は、アナログであっても同じだからだ。

アナログ計算機で何回も同じ計算を繰り返して平均をとれば、平均値は「真の値」に限りなく近づくであろう。

デジタルとアナログの違いは、「特定のビットが誤る確率か、真の値からのずれの大きさか」であって、

どちらか一方が絶対的に誤りが少ないというわけではないのだ。


シャノンが深く掘り下げたのは、この点だった。

「果たしてデジタル信号は、繰り返した分だけ、誤り率が下がるのか?」

深い考察の結果、シャノンは「繰り返し回数と誤り率は、反比例しているわけではない」ことを突き止めた。

繰り返し回数を無限に大きくする必要はない。

ある一定の値まで大きくすれば、誤り率を限りなく0に近づけることができる。

この「ある一定の値」というのが、通信路容量と呼ばれている値のことだ。

有限のある一定値までで、誤り率をとことん下げることができるのだから、デジタルはアナログに対して決定的に優位となる。

「有限の一定値」という概念は、アナログでは決して出てこないからだ。


通信路符号化定理が解りずらい理由の1つは、「誤り率が0になる」わけではない、という点にある。

 「いくらでも誤りのない」

 「誤り率を無限に小さくする」

 「あいまい度合いが H - C + ε よりも小さくなるように、ここでεは任意の小さな数だ。」

これらの言い回しは同じことを言っているのだが、どれも奥歯に物がはさまったようですっきりしない。

しかし、確率の世界で「絶対100%」ということはあり得ない話なのである。

ゼロではなく、非常に高い目標値、例えば誤り率 1/(10^10) 以下といった数字を掲げたとき、

その目標値を達成できるような方法が存在することを定理は述べている。

誤り率0の方法を述べているわけではない。(そんな方法は存在しない)

なので、正確に表現しようとすると、どうしても「限りなく0に近づく」といったすっきりしない表現が入ってしまうのだ。


それでは、肝心の定理の中身はいったいどのようなものだろうか。

正確な内容は情報理論の教科書に譲るとして、ここでは一番おいしいエッセンスだけをつまみ食いすることにする。

通信路符号化定理の説明には、幾つかの斬新なアイデアが登場する。


* アイデアその1: 2つのデジタル信号間の「距離」を考える

いま、1と0だけから成る2つのデジタル信号があったとして、この2つが「どれくらい違っているのか」を数値化したい。

そのため、2つの信号の中で異なっている文字の数を「違いの度合い=2つの信号間の距離」と考えるのである。

このように定義した距離のことを「ハミング距離」と言う。wikipedia:ハミング距離

例えば 1011101 と 1001001 の間のハミング距離は 2 である。


* アイデアその2: ビットの長さだけの次元を持つ「メッセージ空間」を考える

ビットの長さが3のデジタル信号は、3次元空間内に置かれた立方体の頂点として表現できる。

3ビット長の2進数デジタル信号は全部で8通り、立方体の頂点の数も8個である。

ということは、4ビット長のデジタル信号は、4次元空間に置かれた立方体の頂点として表現できることになる。

wikipedia:ハミング距離 に4次元立方体の挿絵があるが、こんな感じになる。

さらに演繹を続けて、Nビット長のデジタル信号をN次元空間に置かれた立方体の頂点と考えるのである。

このN次元立方体には、長さNのデジタル信号の全てが含まれていることになる。


* アイデアその3: 距離の近い方に復号する

もしデジタル信号上に誤りが発生して、1つのビットの値が入れ替わってしまったとする。

入れ替わったデジタル信号は、もとのデジタル信号からハミング距離=1の範囲内にある。

そこで誤りを除去するために、こんな方法が考えられるだろう。

全てのデジタル信号を、お互いに重ならない「ハミング距離の半径=1の球」でカバーする。

そして、1つの球の範囲内にある信号は、全て同じメッセージなのだと解釈する。

1ビット違っていてもそれは許容して、球の中心である本来のメッセージに復号するのである。

例えば、長さ3ビットの信号で「AかBかの2択」を送信したければ、

{0,0,0} を「A」に、{1,1,1}を「B」にあてがっておけばよい。

f:id:rikunora:20080807223516p:image

こうしておけば、たとえ1ビットの誤りが生じても、

「0の数が多い方がA」、「1の数が多い方がB」という判断によって、元のメッセージを復元することができる。


* 通信路符号化定理の本質

ここまで来れば、通信路符号化定理の本質がわかってくるだろう。

デジタル信号によって誤りなく伝達できるかどうかは、

 「N次元のメッセージ空間に、ハミング距離一定の球がいくつまで入るか」

という問題だったのだ。


それでは、N次元メッセージ空間で、半径kの球の「体積※」はいくつになるだろうか。

(※より正確には「体積−中心点」、つまり離散的な「表面積」)

これは要するに組み合わせの問題で、N個の中からk個を取り出す組み合わせの数、すなわち

  N C k = N! / (k!・(N - k!))

となる。


球の体積がわかれば、それとメッセージ空間全体の「ふくらみ具合」から、デジタル信号がメッセージ空間に収まりきるための限界値が求まる。

伝達したいメッセージを最低限、誤り無く表現するために必要なビット数がN0ビットだったとしよう。

このメッセージを誤りなく伝達するために、余分にビットを付け加えて全体でNビットになったとする。

Nビットのデジタル信号が取り得る全メッセージの数=メッセージ空間の広さは、2^N 。

誤りを訂正するために付け加えた、余計な(冗長な)メッセージの数=メッセージ空間が広がった分は、2^(N - N0) 。

この広がった分が、先の半径kの球の体積よりも大きければ、全ての球がメッセージ空間に収まることになる。

つまり、限界値を表す式は

   2^(N - N0) >= N! / (k!・(N - k!))

となる。

この式に含まれているk(許容できるハミング距離の半径)を、平均的な誤り率に置き換えることによって、通信許容量が求められる。


シャノンの通信路符号化定理は、具体的なコーディング方法について述べたものではない。

具体的な方法を示さずとも、「全てのメッセージ空間」と、「その中にデジタル信号がいくつまで入るか」という全体的な視点から、誤りなく伝達できる情報量がわかってしまうのだ。

この洞察には、感動すら覚える。

以上がデジタルの優位性であり、20世紀最大の技術革新と言ってもよいだろう。


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

ファインマン計算機科学

ファインマン計算機科学

今日から見れば決して最新とは言えないが、情報とは何か、についての深い洞察がある。

上に書いたことは、この本の受け売り。


dokasendokasen 2009/01/02 04:47 興味深いです!
ただ、途中、メッセージ空間の「体積」の計算あたりから解らなく成りました。3次元しばりでなくN次元の場合のメッセージ空間の容量を表現しようとすると、値の表現方法が無限に広がってきそうな予感、、、

rikunorarikunora 2009/01/04 00:15 dokasen 様
シャノンの情報理論って、私も最初はさっぱり意味がわからなかったのですが、
メッセージ空間のイメージがつかめると、実は感動ものの内容なんですよ。
おそらく数学上の理由だけでなく、この感動があったからこそ急速にデジタルになったのではないでしょうか。
私の生半可な説明だと受け売りだし誤解も招きやすいので、
ぜひファインマン計算機科学とか、他の情報理論と銘打ってある本を手にとってみてください。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20080807/p1