情報理論の父といわれるClaude E. Shannonは、いったいどのようなことをきっかけにシャノン限界(Shannon Limit)を考え付いたのでしょうか。


(参考:シャノンへのインタヴューを試みたがはぐらかされた記者の話が出ています。Scientific American, January 1990, Page 16-17)

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2010/01/20 14:41:04
  • 終了:2010/01/27 14:45:02

回答(2件)

id:ita No.1

ita回答回数204ベストアンサー獲得回数482010/01/21 12:27:16

ポイント18pt

必要性と発想の元に分けて考えてみます。

10%のノイズが入る通信路で99%以上の信頼性で0/1信号を送りたいとします。

とりあえず同じ信号を三回送って多数決をすればいけそうです。でも、もっとうまい誤り訂正のコーディングをすれば、通信の速度を上げられるかもしれません。

で、もっとうまい方法を一生懸命考える時に、これ以上はどうがんばっても無理、という限界が分かってればかなりやり易いですね。限界の90%くらいならまあいいか、とか判断できますし。そういう必要性に迫られて考えたはずです。

で、なにか理論的限界があるのは直感的に明らかだと思うんですがどうでしょう。そうなれば後は数学的に詰めるだけです。具体的な式の形をどう考えたか、というのは分からないですが。

URLはダミー http://aaa.com

id:ShinRai

質問の仕方が悪かったのかもしれませんが、期待はずれの回答でした。

C/W=log 2 ( 1+S/N ) の式がどうやって生まれたのかというところに興味があります。

そもそもシャノンは、デジタルデータとアナログデータの区別ができていたのかなあという疑問もあります。

2010/01/21 15:15:06
id:ajapoo No.2

ajapoo回答回数1ベストアンサー獲得回数02010/01/21 19:18:09

ポイント52pt

具体的に説明すると長くなるので概要を説明させていただきます。

通信システムにおいて送信者の送る情報自体の分布をうまくいじると誤りを抑えて情報を受信者に送ることができます。

ただいくらいじっても限界はあります。この限界を示したものがチャンネル容量です。

さらに送る情報を符号化して、その符号化率がチャンネル容量よりも小さければ任意に誤り率を下げることができるというものを示したのが

チャンネル符号化理論です。

このチャンネル符号化理論をガウスチャンネルに適応するとShinRaiさんが示されたシャノン限界がもとまります。

大まかに

送信情報の分布をいじれば誤りを抑えられるのではないか?→符号化すればさらに抑えられるかも!→ガウスチャンネルに適用してみよう。

という流れだと思います。

私自身情報理論の勉強中でして間違ってる所などがあればご指摘ください。

また、当時はすでに世界初のコンピュータも登場していますしデジタルとアナログの区別はできていたと思います。

http://1.com

id:ShinRai

ガウスチャンネルというのは量子力学の世界の話ですか。

シャノンは、リレースイッチの回路の論文はあるけど、量子論のペーパーはひとつもない。

どうしてそこにシャノンがすっといけたのか、疑問です。

もう少し教えていただければありがたいです。

また、シャノンは、デジタルとアナログという概念を一度も使っていません。

概念なしに、区別をできるとは、思いがたい。

通信路符号化は、送信前・受信後に行なう計算処理であり、計算によって

エントロピーを低くして、回線ノイズに対する耐性を加える作業だと思っております。

しかし、アナログの符号に対しては、計算できないから、通信路符号化は

デジタル符号に限った話になるのでは? いかがですか。

あなたの言っておられることが、間違っているとは思っていません。

もう少し教えていただければありがたいです。

2010/01/22 10:13:58
  • id:ita
    あ、失礼しました。ピントはずしてましたね。
    N種類の電圧で通信するような場合にパルス何個分に相当するか、
    というようなことが頭にある感じなんでデジタルな気がします。
  • id:ShinRai
    itaさん、

    こちらこそ、失礼しました。
    ご協力に感謝申し上げます。

    それにしても量子ガウスチャネル、わからないです。

    http://jglobal.jst.go.jp/public/20090422/200902225639726731

    しかし、こういった論文を読むと、ガウス通信路のことがわかるのでしょうか。
    図書館にいってみようかと思います。

    シャノンは、ひとことも量子ということを言っていないのではないかと思う
    のですが、どうしてそれを思いつくことができたのでしょう。

  • id:ShinRai
    http://www.optronics.co.jp/books/store/?mode=search&pattern=detail&itemid=20150

    こういった本を読むとわかりますか。


  • id:ajapoo
    ガウスチャンネルという表現が悪かったかもしれません。
    私の言うガウスチャンネルというのは受信信号に白色ガウス雑音を足し合わせたものです。
    AWGN通信路というのが適切な表現のようです。
    白色ガウス雑音が現実の雑音良い近似になります。
    本質は量子論になるのかもしれません。
    http://en.wikipedia.org/wiki/AWGN

    デジタルアナログの区別ですが、今一度復習してみたところシャノンはデジタルのアイディアを持っていたようです。
    下記のページに彼の修士論文"A Symbolic Analysis of Relay and Switching Circuits"はデジタル回路の基礎理論を作ったと書かれています。
    http://www.bell-labs.com/news/2001/february/26/1.html

  • id:ajapoo
    あいまいさ(エントロピー)についてご存知のようなので補足させていただきます。

    >通信システムにおいて送信者の送る情報自体の分布をうまくいじると誤りを抑えて情報を受信者に送ることができます。
    >ただいくらいじっても限界はあります。この限界を示したものがチャンネル容量です。

    ここで「誤りを抑える」と表現していますが、実際には「あいまいさを減らす」というのが適切な説明です。
    チャンネル容量というのは減らすことのできるあいまいさの最大量を示しています。
  • id:ShinRai
    ajapooさん

    いろいろとありがとうございます。

    エントロピーも非常に理解しづらい概念ですよね。

    私は、符号列の一次独立性を高めるために、誤り訂正符号を追加することが、エントロピーを低くすることかなと思っています。

    あと64種類のコドンから20種類のアミノ酸を指定するときに、頻度の多いアミノ酸には4つ以上のコドンをあてはめることも、エントロピーを低くしているのかなと。

    こういう考えではいけないでしょうか


  • id:ajapoo
    >こういう考えではいけないでしょうか
    エントロピーを下げるという視点では間違いないと思います。

    次にシャノン限界を目指すという視点で話させて頂きます。

    >符号列の一次独立性を高めるために、誤り訂正符号を追加することが、エントロピーを低くすることかなと思っています。
    当初はこのような考えの下で様々なハミング符号や畳み込み符号が考案されてきましたが、シャノン限界には程遠いものでした。
    20年以上この状態が続き一時はシャノンの理論は使えないものだという風潮もありました。

    1992年に発表されたターボ符号は符号化にイテレーション構造を持たせた符号化手法で
    シャノン限界に漸近する手法です。
    http://en.wikipedia.org/wiki/Turbo_code
  • id:ShinRai
    ハミング符号や畳み込み符号では、シャノン限界に近づかない、、、

    TPC(ターボ符号) 、そして最近ではLDPCでしょうか。
    シャノン-1dBくらいで使えるということですよね

    思うに、符号化利得自体がおよそ10dBあり、どのような符号化であっても
    使うことで10dB稼げる

    しかしながら、符号化遅延があるから、その10dBは打ち消されてしまう

    TPCやLDPCのように、イテレーションを実施しても
    シャノン限界に近づくのはどうしてなのでしょうか
    CPUの計算速度が高速化したということ以外に何か理由はあるのでしょうか



  • id:U-tan
    >デジタルデータとアナログデータの区別ができていたのかなあという疑問もあります。
    A Mathematical Theory of Communicationの章立てはhttp://www.jkokuryo.com/literature/bs/review/shannon_1.htmlでみられますが,離散的・連続的という言葉遣いが出てきます.デジタルとアナログのことです.
  • id:ajapoo
    >TPCやLDPCのように、イテレーションを実施しても
    >シャノン限界に近づくのはどうしてなのでしょうか
    >CPUの計算速度が高速化したということ以外に何か理由はあるのでしょうか

    シャノン限界は符号長が無限大ということを想定した式です。
    エルゴード性というもの利用しています。
    http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%AB%E3%82%B4%E3%83%BC%E3%83%89%E7%90%86%E8%AB%96
    なので符号化遅延を考慮していません。
    TPCやLDPCなどを発表された論文のシュミレーション結果は見事にシャノン限界に近づいていますが、
    実際にシュミレーションにかかった時間は符号長をかなり長くして数時間から数十時間になります。
    なので実際に通信システムにシャノン限界に近い誤り率を達成する符号化手法を用いようとすると、
    高価な高速CPUを用いて、更に符号化のための処理遅延が発生するわけです。
    欠点ばっかりに見えますが。宇宙探査機と地球の基地局との通信など通信遅延が大きく、
    処理遅延が問題にならない場合には非常に有効な手段です。
    逆に、携帯電話などは安価なCPUを利用したうえで即応性が求められます。
    このような条件のもとで実現されたターボ符号の誤り率はシャノン限界からは遠いです。
    今後の技術および理論の発展が注目されます。
  • id:ShinRai
    U-tanさん、

    discreteとcontinuousという言葉は確かに使われています。

    しかし、それは本当に、デジタル・アナログでしょうか。

    そこがよく理解できません。
  • id:U-tan
    >しかし、それは本当に、デジタル・アナログでしょうか。
    に答えるかわりに
    >通信路符号化は、送信前・受信後に行なう計算処理であり、計算によって
    >エントロピーを低くして、回線ノイズに対する耐性を加える作業だと思っております。
    >しかし、アナログの符号に対しては、計算できないから、通信路符号化は
    >デジタル符号に限った話になるのでは? いかがですか。
    に答えます.
    情報通信は,集合論的に言えば,彼の地にいる人が全体集合の中からいくつかの元を此の地にいる人に指定することです.離散的なモデルでは有限の全体集合が仮定され,情報源と発信機から情報が通信路に放たれ受信機と受信者が受け取るのです.連続的なモデルでは,振幅や周波数などがある限界の範囲内に制限された連続的関数が送受信されます.帯域が正の通信路が存在すれば,「十分な」時間をかければ,任意の情報量を正確に通信することが可能です.
    『A Mathematical Theory of CommunicationにはPART III・IV・V』があり,離散的通信での議論を前提に連続的通信における情報の一般的な議論がなされます.通信路符号化は,通信路つまり,情報源→発信機→通信路→受信機→受信者,の通信路に受信機・発信機を「かませる」ことでつまり情報源→発信機→通信路→受信機・統合機・発信機→通信路→受信機→受信者することです.これは連続的通信でも可能です.
  • id:U-tan
    ごめんなさい.
    >情報源→発信機→通信路→受信機・統合機・発信機→通信路→受信機→受信者
    直列としてしまってはは全くおかしかったです.論文では送信機・観察者・訂正装置ででてきます.論文のFig.8を見てください.
  • id:ShinRai
    U-tanさん、

    私の理解はこうです。

    離散的な通信では、回線上でやりとりされる符号が、離散・有限(bitなら0,1, mRNAならA, G, U, C)に決まっていますので、受信者はそれらの有限離散信号のうちのどれを受信したかを考えればいい。

    雑音が一定レベルよりも低ければ、ほぼ100%の確率で正しい信号を復元できます。

    一方、アナログな通信では、回線上の雑音によって、連続的関数が歪みます。そしてその歪みがリセットされることはありません。

    シャノンの議論において、離散モデルと連続モデルが同じであるかのように扱われるのがどうしてなのか、そこがわかりません。全然違うシステムじゃないかと思うのです

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません