無駄にデータを使って情報を表現する方法

暗号を勉強していた時ふと浮かんだ疑問ですが、
「NビットのデータをMビット(M>N)に変換し、Mビットが全て正しければ元のデータが復元でき、1ビットでも異なっていれば元のデータの1ビットも復元できない」(異なっているビットを全て試してみるより有意に多い確率で復元できない)
ような変換は存在するでしょうか。
何かヒントになるようなことでもありましたらお教えください。

No.5 回答者： alice_44 回答日時： 2010/02/26 20:07

No.3 は、秘密鍵方式というつもりで書いたので、

係数行列はナイショにする話です…が、変ですね。
考えが足りませんでした。

エラーの位置が判らないようにということなら、
原データ＋エラー でも既に、エラーが何処に
あるのかは判りません。
そこを敢えて、エラー位置が判らないような符号
を考えるというのであれば、
原データについては、エラー位置を推定する
方法が存在することが前提のハズです。
その推定法を無効化する符号ということですね。

だとすると、その推定法を具体的に仮定しなければ、
話が始まりません。それは、どんなものでしょうか？

この回答へのお礼

エラーの推定法については特に考えていません。
エラー位置を確実に特定できるという前提でも復元できないようにできないか考えています。
ただ、No4にも書きましたが、0/1しか無ければエラー位置を特定できれば復元できてしまうので、意味をなしていませんでした。すみません。
ですので、エラーが確実に起っていない領域とエラーが起こったかもしれない領域が判別できる、言いかえれば情報が消失している場所がありその場所は特定できる、という状況で考えることにします。

お礼日時：2010/02/27 23:14

No.4 回答者： Tacosan 回答日時： 2010/02/26 11:19

「異なったビットの位置は特定できる」

とはどういう意味でしょうか? 例がいくつかあると助かるかもしれません.
あと, これと質問文中の
「1ビットでも異なっていれば元のデータの1ビットも復元できない (異なっているビットを全て試してみるより有意に多い確率で復元できない)」
との関係も分かりません. 「異なったビットの位置は特定できる」ということは「異なっていないビットの位置も特定できる」ということだから, 「元のデータの1ビットも復元できない」ということはありえないと思うのですが.

この回答へのお礼

ああ、本当ですね。すみません、混乱していたようです。
最初はバイトで考えていたのですが、ビットでは異なっていることが分かれば復元できてしまいますね。
では、ビットの「情報が消えた(ビットが異なっているかもしれない)位置が分かる」という前提に変更します。

お礼日時：2010/02/27 21:15

No.3 回答者： alice_44 回答日時： 2010/02/25 23:04

二元体上の N 次元ベクトル空間から、M 次元ベクトル空間の中へ、

単射な一次変換をすれば良いのでは？
変換行列を知らなければ、
像が 1 成分でも違うと、原像は 1 成分も再現できない。

この回答へのお礼

回答ありがとうございます。
具体的な変換行列はどのようなものになるでしょうか。簡単なものだと復元できそうです。
また、「変換行列を知らなければ」ということですが、それは出力データが完全なら変換行列が分からなくとも元データが復元できるということでしょうか。

お礼日時：2010/02/26 01:55

No.2 回答者： f272 回答日時： 2010/02/25 18:57

数は全て2進だと思ってください。

N=1,M=2として，変換fを考えて
f(0)=00
f(1)=11
とします。逆変換gは
g(00)=0
g(11)=1
は分かるけど
g(01)
g(10)
は分からない。
こういうことでしょうか？

この回答へのお礼

はい、たぶんそういうことになると思います。
ただもっとビット数が多くないと意味がないですし、考えにくいと思います。

お礼日時：2010/02/25 23:23

No.1 回答者： Tacosan 回答日時： 2010/02/25 18:45

N ビットのデータに対して「パリティビット」をつけると

・N+1 ビットがすべて正しければ元のデータは復元できる
・N+1 ビットのうち 1ビットでも間違ってしまったら元のデータは復元できない (「どこかが間違っている」ことはわかるけど, 「どこが間違っているか」はパリティでは分からない)
といえるはず.
ということで, 「パリティをつけて 1ビット増やす」ことを繰り返せばいいような気もする.

この回答へのお礼

回答ありがとうございます。
ああ、確かにそうなってしまいますね。
すみませんがこれは私の考えていたこととは違ってしまいます。
「異なったビットの位置は特定できる」という前提でお願いします。

お礼日時：2010/02/25 22:23