情報理論

情報理論で下の問題が分かりません。

１６進数４桁のデータを使って毎秒１データの速度で通信している。
通信機器が故障して１データ３桁で受信されるようになった。
いずれか１桁が消滅するようになったのだが,
消滅する桁は均等に分布し,どの桁か予想ができない。
このときの通信路容量を求めよ。

よろしくお願いします。

No.1 回答者： stomachman 回答日時： 2001/01/27 20:03

へんてこな故障の仕方もあったもんですねえ。

　AABBを送れば、どの文字が欠けても（そしてどれが欠けたか分からなくても）、受けた３文字のうち最初がAで最後がBです。だから少なくとも2文字、情報量として毎秒2bitまでは全く誤り無しに送れるのは確かですね。

上限の方はどうでしょうか。ランダムコードの誤り訂正符号の理論をちょっと応用すればできそうですけど....

No.2 回答者： punchan_jp 回答日時： 2001/01/27 20:30

よくわかりませんが、どの桁が消失しようと、毎秒3桁受信できるわけですよね？で、どの桁が消滅するか予想はできないけど、受信してみたらどの桁がきえたかはわかるんですね？送信側がそれを知っているなら、3桁のデータにパリティ桁をつけて送ってやれば、受信側で完全に復元できるんではないですか？それなら、容量も単純にわかりますよね？それともそれ以外の条件がついてるんでしょうか。

この回答へのお礼

ご回答ありがとうございます。
多分,受信してもどれが消えたデータかは分からないと思います。
例えば０００を受信しても,もとのデータが１０００なのか,００００なのか
０１００なのか,・・・
私はそのように解釈しました。
分かりにくくて申しわけありません。

お礼日時：2001/01/27 21:06

No.3 回答者： stomachman 回答日時： 2001/01/30 22:49

１回あたり3文字しか届かないんだから、上限は高々３bit。

どの文字か欠けたか分からないので、3bit未満なのは確か。 1文字パリティを入れてもダメですね。

　普通の通信路容量の計算では、ランダムに誤りが発生し、通信が失敗したらやり直す、ということを含めて平均何bit送れるか、という問題ですから、４文字以上の単位でメッセージを構成する場合も考察しなくてはダメですが、この場合には丁度４文字毎に１文字欠けるという所が特殊ですんでかえって常套手段が使えない....

No.4 回答者： arika 回答日時： 2001/01/31 12:44

通信路容量がよくわかりませんが、

かならず、３桁で送れるなら、ＳＴＯＭＡＣＨＭＡＮさんのコメントからヒントをえて考えると、送りたいデータがＡＢなら、この伝送路にＡＡＢＢとして送れば、ＡＡＢ，ＡＢＢのいずれかで到達するので、この受信データからＡＢを抽出することは可能と思えます。
ということは、１６進４桁を2桁づつに切り分けて
２回送ればＯＫです。
単位はわかりませんが、１６進４桁を１ワードとすると、
０．５ワード／秒ってことになりそうですが、
どうでしょうか？

もし答えなどがわかったら教えておいてください。

No.5 回答者： punchan_jp 回答日時： 2001/02/19 11:32

「暇なときに」ということで暇が少しできたので補足要求込みの追加回答を。

普通符号理論では、データの一部が忽然と消えるというモデルじゃ
なくて、消失したことがわかる異常なデータに化けるというモデル
を使うんですけど、kazu3さんのモデルを使うということにして…

ただ、問題設定の確認ですが、「16進数4桁のデータ」とはどうい
う意味かはっきりさせてもらえないでしょうか？私の解釈は16進数
1桁というのは4ビットを表すから、それが4桁ということは1データ
=4x4ビットというものなんですが、これでいいのでしょうか？場合
によっては16進数などというと、0-9A-F の文字をASCIIで送るとい
う解釈もこじつけられますので。

stomachmanさんの解釈は1データ=4ビットということですね？その
解釈で、4ビットのデータのうちどれか1ビットが忽然と姿を消すの
だとすると、2回繰り返し法で送って毎秒2ビットというのが上限の
ような気がしますね。

で、私の解釈の1データ=4x4ビットが正しいとしたとき、繰り返し
で送ればarikaさんのいうように毎秒8ビットで送ることができます。
でも、少し工夫すればもうちょっと増やせます。各桁4ビットのう
ち1ビットを同期用に使い、必ず 0 1 0 1 と送ることにします。つ
まり、---0, ---1, ---0, ---1 という感じですね。こうすれば、
このうちの一つがごっそり消えたとき、どれが消えたかは必ず判明
します。そうなれば、4x3ビットのデータを送ったときにどれか一
つが消えて、しかもどれが消えたかわかる場合に帰着できますから、
一つをパリティ桁にしてしまえば確実に9ビットは送れます。

もともと、16ビット中4ビットが消失して、その位置を表す2ビット
の情報量も失なわれたとおおまかに考えられますから、10ビット送
れたらうれしいところですが、その方法はちょっと思いつきません。

話はもどって、1データ=4x1ビットの解釈で2ビット送れるのはこの
説明に矛盾するように見えますが（2 > 4-1-2）、失なわれた位置
を特定せずに復元できる方法なので、矛盾はしていません。
（って、どこかで答えた情報量の話の再燃か？^^;）