シャノンの第二基本定理（通信路符号化定理）について

質問

質問Ｎｏ．５１６１７の周波数と情報伝送量の関係から、通信路符号化定理にまで話が発展し、定理の解釈について２つの見解があり、収束しません。
専門家の方の解説をお願いしたいと思います。

論点は、通信路符号化定理が「誤り訂正符号を前提としたものである」という見解と、「誤り訂正符号でない別の符号体系を前提としている」という見解のどちらが正かということです。よろしくお願いします。

http://www.okweb.ne.jp/kotaeru.php3?qid=51617
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=51617
http://www.okweb.ne.jp/iwedding/kotaeru.php3?q_id=51617

回答No.2

stomachman · ベストアンサー

おおおおおおおお昔にやったっきりなので、かなり怪しいですが....

通信路のパーフォーマンスの上限を抑える定理ですよね。
冗長性ってのは、受信できる語がN通りあって、その集合を適当にM個（Ｍ<<N）の部分集合に分類し（Shannonの証明では、たしかランダムに分類するんでした。）、M通りの送信信号に対応させるということでしょう。いわゆる「誤り訂正符号」というのはこの受信信号と送信信号の対応をいちいちコード表でlook upしなくても良いように、システマティックに簡単な計算でできるようにした、というだけのことじゃありませんでしょうか。つまり、誤り訂正符号だってlook　upでデコードしても構わん訳ですし、逆にlook upを許せば、冗長な符号はどれでも（適当に低い誤り率の元で）誤り訂正ができる。従って、誤り訂正符号になっているかどうかは、議論の本質とは関わりがない、と考えますがいかが？
　しかも、おぼろげな記憶に依れば、システマティックな冗長化では、Shannon流ランダムエンコードを越えることができないんじゃありませんでしたっけ？

お礼

stomachman さん、コメントありがとう御座いました。
「目からうろこ」です。そうですね。「誤り訂正符号」かどうかではなくて「冗長性のある符号」かどうかという事が、議論されるべきなのですね。それに気がつかないものだから「広義の誤り訂正符号」なんてややこしいこと言ってました。最初から「冗長性の有る符号」といっておけばよかったと思います。いずれにしてもシャノンの基本第二定理は「広義の誤り訂正符号」じゃなかった「冗長性の有る符号体系」を前提としているという確信が持ててきました。私は、今まで「冗長性のある符号体系」＝「誤り訂正符号体系」（ただし、誤り検出だけのものを除く）　と勝手に理解していました。
たいていのエンコード、デコードなら、「連想記憶でなんとかなるよ」と言いたいところですがランダムエンコードになるとお手上げです。

stomachman さんの博識には舌を（尻尾を）巻きます。本当にありがとう御座いました。

補足

この質問を締め切ります。最終のお礼を補足欄に書かせて頂くことをお許し下さい。
結局、最適な符号というのは冗長符号という結論です。これを誤り訂正符号というかどうかは二の次という事になりました。どうも有り難う御座いました。

回答No.3

Umada

ymmasayannさん、そしてmotsuanさんstomachmanさんこんにちは。早速議論が進んでいますね。
stomachmanさんのご説明に私も納得しました。(「本当に分かっているのか?」と突っ込まれると困ってしまいますが・・・(笑))　この議論における本質は冗長度であり、誤り訂正符号は「第二基本定理の教える符号化法よりはさらに冗長度が必要になる場合もあるが、誤りの検出と訂正をより効率的に行える方法」と理解しました。
ランダムエンコードについては証明の中で確か、「最善の符号化法を用いた時の誤り率を評価したいが、最善の符号の何たるかが全く分からない。そこで取りあえずランダムなものでまず上界を押さえる」てな登場の仕方をしていたようです。で、「最善なやつはそれよりはマシのはず＝それよりマシな符号化法が少なくとも一つ存在する」てな進め方だったと記憶しています。

なんだかまとまらないコメントになってしまい恐縮ですが、当初の問題(Shannonの第二基本定理の「最適な符号化」とは誤り訂正符号なのか?)という問題については私も大いに勉強になりまた納得しております。コメント下さったstomachmanさん、motsuanさん、そして新しい質問として提起して下さったymmasayanさん、ありがとうございました。

お礼

この質問を締め切ります。
結局、最適な符号というのは冗長符号という結論です。これを誤り訂正符号というかどうかは二の次という事になりました。どうも有り難う御座いました。
いい勉強をさせていただきました。今後ともよろしくお願いします。

補足

Umadaさん、今晩は、お待ちしてました。前のところにここへの道案内を書いておいたのですが、事務局から、個人的な議論は規則違反だからと消されてしまいました。
また、お会いできて、議論できるのが嬉しいです。
ここに移って、みなさんの意見を聞いて、結局、シャノンって偉いなというのが実感です。

回答No.1

motsuan

専門化ではないので、ごめんなさい、横槍です。
下のＵＲＬの説明を素直に読むと、
存在定理みたいなもので、（現実的な）符号の構成法は示していないみたいです。
「誤り訂正符号でない別の符号体系」というのは変調方式のようなものを考えていらっしゃるのでしょうか？
実際の伝送路に対しては変調方式によって誤り率がいくらか変わると思いますが
誤り率を限りなく下げることができるとなると訂正符号のように符号を冗長にしていくしかないと思います。

参考URL：

http://www.sr3.t.u-tokyo.ac.jp/code/sh-cct.html

お礼

motsuanさん、こんにちは。コメントありがとうございます。「横やり」だなんてとんでもありません。大歓迎です。

参考ＵＲＬは既に見てはいたのですが、東邦大のＨＰの方が「誤り訂正符号」ライクだったので、前質問コーナーでは、あえて東邦大の方を掲載させていただきました。

おっしゃる通り、定理自体は存在定理だと思います。定理のいう「最適な符号体系」が「広義の誤り訂正符号（未知の符号体系を含める）」を前提条件にしているかどうかがこの質問コーナーの議論の焦点です。
motsuanさんのいわれるように「誤り率を限りなく下げることができるとなると訂正符号のように符号を冗長にしていくしかない」というのは私も同感です。
誤りがあれば冗長度を上げるしかない。冗長度を上げるという事はすなわち、誤り訂正符号だというのが私の考えです。シャノンさんも「最適な符号体系」といわずに「最適な誤り訂正符号体系」と言っておいてくれたら良かったのですが（笑）
先日亡くなられたそうですのでそれも・・・。　余談ですみません。
色々ありがとうございました。議論の展開によって、またご意見お聞かせ下さい。
相手の方が週末頃から、又、出てこられると思います。

補足

この質問を締め切ります。最終のお礼を補足欄に書かせて頂くことをお許し下さい。
結局、最適な符号というのは冗長符号という結論です。これを誤り訂正符号というかどうかは二の次という事になりました。どうも有り難う御座いました。