デジタル通信において,誤り検出・訂正符号化はなくてはならない重要な技術です.この誤り訂正符号のおかげで,送信側から受信側に一度しか送信しなくても,1ビットの誤りもなく伝送が可能になります.送信側で,誤り訂正符号を計算して付け足すことは,エントロピーを低減させることになると思うのですが,誤り訂正符号をエントロピー的に説明しているHPがあったら教えてください.

回答の条件
  • URL必須
  • 1人2回まで
  • 13歳以上
  • 登録:2010/06/20 05:27:41
  • 終了:2010/06/27 05:30:03

回答(0件)

回答はまだありません

  • id:koriki-WeKan
    やり直しのための工業数学
    http://www.cqpub.co.jp/hanbai/books/33/33181.htm
  • id:ShinRai
    本のご紹介ありがとうございます。
    書店で探してみます。

    「ノイマンとコンピュータの起源」の第8章で、ノイマンが、ハミング符号をエントロピーの例として論じているという表現がありました。原典は確かめていませんが



    ノイマンとコンピュータの起源 / ウィリアム・アスプレイ著 ; 杉山滋郎, 吉田晴代訳
    出版者 東京 : 産業図書
    出版年 1995.9
    大きさ xii, 393p ; 22cm
    別書名 原タイトル:John von Neumann and the origins of modern computing
    一般注記 文献目録: p347-366
    フォン・ノイマンの著作目録: p367-378
  • id:T_SKG
    例えば、下記URL(パワーポイントです)
    http://www.cck.dendai.ac.jp/~koyama/it/m/05channel.ppt
    で、スライドの46ページ目の図が直感的で解り易いですが、本当に理解したいなら、前のコメントの
    方の進めておられる書籍等を時間を掛けて読むことをお勧めします。

    パワーポイントをお持ちでない場合は、マイクロソフトが提供しているビューワーが必要です。
    http://www.microsoft.com/downloads/details.aspx?displaylang=ja&familyid=048DC840-14E1-467D-8DCA-19D2A8FD7485
  • id:ShinRai
    T SKGさま

    貴重な情報ありがとうございました。

    理解してみます
  • id:ShinRai
    p46の図をみると、エントロピーが、送信によって減っています。

    熱力学の第二法則では、エントロピーは増加することになっています。

    どうして送信によって、エントロピーが減るのでしょう。

    秩序は減り、その分、乱雑さが増すのではないでしょうか。

    ちょっと理解できません。
  • id:taka-hr
    どちらかというと同じサイトですが

    http://www.cck.dendai.ac.jp/~koyama/it/m/02info.ppt

    を読んだほうがいいと思います。

    一般の(特定の形式を持たないデータの)デジタル通信に関して言うと、誤り検出・訂正符号がない場合(データだけを送る場合)には、0がくる確率と1がくる確率は同確率であると考えられます。その場合、0か1かの1ケタが表す情報量は 7ページの定義にあるように、p = 1/2 なので自己情報量 I(p) = -log2(1/2) = 1 (単位:bit) になります。これがビットの定義です。

    通信路で考えると、1ケタ(シンボル)の 0 か 1 を受け取ることで 1bit の情報を知ることができる、ということになります。

    誤り検出・訂正符号のない場合のエントロピーは 16 ~ 26 ページにあるとおりですが、情報量の期待値なので、0 である確率が 1/2, 1である確率が1/2 であるとして計算すると

    H(S) = 1/2 (-log2(1/2)) + 1/2 (-log2(1/2) = 1

    になります。まぁ期待値 1bit/ケタ(シンボル)、すなわち1つのシンボルを受け取った時1bitの情報を受け取ったということなので直感的にもわかると思います。

    誤り訂正符号を、単純化するためにたとえば 1bit ごとに 1bit の偶数パリティをつける、すなわち 2ケタずつ繰り返すことで冗長度を持たせることを考えます。つまり、元データが 00101011 であるときに、1ケタごとにパリティをつけて 0000110011001111 と表記するということです(これは 05-channel.ppt の 10ページの(b)にも同じ例があります)。

    このときは、ある1ケタ目のシンボルを受け取った場合、次も同じシンボルである確率が高いことがわかっていて、もし違うものが来たらそれは誤りを検出したということになります。

    別の言い方をすると、2ケタ受け取ると 1bit の情報が得られることになります。誤りがないものと仮定すると、00 の確率が 1/2, 11 の確率が 1/2, 01 と 10 の確率は 0 になりますので、H(S) = 1/4 (-log2(1/4)) + 1/4(-log2(1/4) = 1/2 となってエントロピーが下がっています。

    誤りがあると仮定する場合にも、通常は誤り確率は 1/2 よりかなり小さい数値をとりますので、同様に計算すれば H(S) < 1 になることがわかります。

    ほかの誤り検出符号についても、要するにデータ部分 n bit に対して誤り検出符号に m bit を割り当てると考えると、n + m ケタのシンボルを受信して n bit の情報を得ることになりますから、誤りがない場合のエントロピーとしては n / (n + m) になります。


    また、T_SKG さんが紹介している46ページの相互情報量については、通信路の誤りの話なのでちょっと今回の質問とは別の切り口の話です。

    左の図をみるとエントロピーが下向きに減っているように見えますが、これは時間経過などで自然に減ることを表しているのではなくて、情報 Y を知ることであいまいさがなくなる(情報を得る) ことを指していますので、第2法則とはあまり関係ありません。

    ですが、右の図で言っているのは、通信路にノイズが乗るなどで誤りが発生して、そのために事後エントロピーH(X|Y)ぶんだけのあいまいさが発生するということを指しています。

    54ページ以降あたりに通信路容量というのがでてきますが、おおざっぱに言うと通信するとエントロピーが増えるために、もとの情報を伝達するために使えるエントロピーが減る、ということを言っています。

    63ページに通信路符号化定理がでてきますが、A^n のなかから M 個の符号語を選ぶ、というのは、データ部分 n bit に対して誤り検出符号に m bit を割り当てる例でいうと、2 ^ (n + m) bit の符号語から 2^n 個の符号語を選ぶことに相当します(n bit が決まれば m bit 分は計算可能 = 依存関係があるため)。

    そうすると、R = n / (n + m) [ビット / 記号] ということになります。さっきも出てきた式ですが。

    これで64ページにある通信路符号化定理を適用すると、通信を行う時には、通信路容量(= (通信したときに増えるエントロピーを除外した)伝送可能なエントロピー)よりも少ないエントロピーの情報しか送ることができない、ということを示していることになります。

    逆の言い方をすると、通信路容量に合わせて誤り訂正符号を適切に選ぶことが必要で、C [ビット / 記号]しか情報を送ることのできない通信路には、R [ビット / 記号] < C となるように適切な量の誤り訂正符号を付加することが「最低限」必要だということです。

    ここで「最低限」というのは、65ページの説明にあるとおりで、最適な符号化方式を使えば R = C とできることは証明されていても、その符号化方式を求めることができないためなので、実際に適用する際にはたとえば m bit のパリティを付加しても誤り検出できない!といった現象が発生することになります。
  • id:ShinRai
    上で触れたノイマンがハミングを論じた箇所です:


    [In the Illinois lectures von Neumann next discussed Hamming’s work on error-detecting and error-correcting codes. He then showed how the digital system with a base (binary, decimal, etc.) is an application of information theory. “Digitalization is just a very clever trick to produce extreme precision out of poor precision. By writing down 30 binary digits with 30 instruments, each of which is only good enough that you can distinguish two states of it (with intrinsic errors maybe on the 10 percent level), you can represent a number to approximately one part in a billion. The main virtue of the digital system is that we know no other trick which can achieve this. From the information point of view it is clear that this can be done, because the entropy in 30 binary instruments is 30 units, and something which is known to one part in a billion has an entropy of the logarithm of a billion (to the base two), or about 30 units.”

    He then pointed out that while organisms use mixed analog-pulse systems for transmitting information, they never (to the best of our knowledge) use a coded digital system with a base. Rather, when “the nervous system transmits a number, it transmits it by what is essentially a frequency modulation trick and not as a coded digital aggregate.” He suggested that the reason for this is that the frequency modulation method is more reliable than the digital system.]

    I have been trying to justify the suspicion that a theory of information is needed and that very little of what is needed exists yet. Such small traces of it which do exist, and such information as one has about adjacent fields indicate that, if found, it is likely to be similar to two of our existing theories: formal logics and thermodynamics. It is not surprising that this new theory of information should be like formal logics, but it is surprising that it is likely to have a lot in common with thermodynamics.

    J. von Neumann “Third Lecture: Statistical Theories of Information “より

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

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

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

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