ヤフー知恵袋で、エラー訂正を解説してといわれたので、ワイの
ホームページの関連ページから簡単に抜粋して説明したら、質問主が何を考えているのか、あっさり削除しよった！かなり不満(ワイのはリードソロモンというのを念頭においたお笑い系のものやけど、ほかの人は、循回符号系でかなり真面目に答えてる人もいた：ほかの人に対しても失礼な奴だと思うで)。
---- (2019.2.7)人の失敗ねちねち直すのは、いけずとか、陰険とかいうんかな？ねちねちというのは、エラー訂正回路が、間違えているのを、根掘り葉掘り探り出して、ねちねち直すという回路の動作を、批判的に解釈したらという言い換え発言です-----
憂さ晴らしに一応ここでもパズルの解説をしとく(本来電子カテゴリーかな？)。 前半のどれが偽物か？を見つけるところは、子供の頃読んだ数学パズルの本で読んだものにも載ってたもので、
最近買った本でもアラブの商人さんの問題だとして、紹介されています。
テレビ番組としての感想は、テレビカテゴリーに入れてます。
問題：複数の袋にそれぞれ複数の金貨が入っている。１袋だけ全部偽物で偽物は少し軽い（手で持ってわかるほど差はない）。袋や金貨の数はいくら多くてもかまわない（一般的な対応必要：数がわからんから一袋の重さも不明）。
この条件で、一度だけ重さを測って偽物を断定せよ。
答え：例えば、本物金貨１００(ｇ)として、偽物は９０(ｇ)とする。金貨の袋は４袋として、３袋目が偽物だったとして解説する。
一袋目から１枚、二袋目から２枚、三袋目から３枚、四袋目から４枚の金貨を取り出して重さを測る。
もし全部本物なら、全本=100(g)*1+100(g)*2+100(g)*3+100(g)*4=1000(g) となるはず。
本件の設定なら、3袋目NG=1000(g)*1+100(g)*2+90(g)*3+100(g)*4=970(g)
（全本-3袋目NG）/誤差 = (1000-970)/(100-90)=3 →偽物３個→３袋目
つまり、３袋目がおかしいというのがわかる。
さて、ここから、パズルではなく、エラー訂正への拡張を考えると、誤差が上記の例のように10gあったというのが、最初から解っているのがおかしい。
これをいかにして求めるか？ もちろん一袋から１枚づつ取り出して、測ったら、10gおかしいのがわかるが、それがわかれば偽物発見で、偽物さがすミッション終了。しかも最悪４袋分回測定が必要。４袋全数検査するというのは、非常に効率悪い検査なんやで。
で、正解は、各袋から１枚づつ取り出して、まとめて、（この場合４枚分）の重さを測る。
期待値＝100+100+100+100=400(g)
この設問の場合、誤差実測定＝100+100+90+100=390
従って、誤差＝期待値－誤差実測定=400-390=10 と、誤り量が求められる。これが求められれば、先の方法でもう一回測定すれば、間違っているのがわかる。
つまり、適当な情報：この問題でいえば、正しい金貨は100gという情報があれば、最初の積和と次の総和の２つの期待値がもとまって、これと２回の測定結果を重ねれば、どの袋がどれくらい
間違っているかがわかるということです。
例えば、金貨の袋、銀貨の袋、銅貨の袋、鉄貨の袋の４袋あって、本物かどうか知りたい場合、それぞれの貨幣の重さを個別に知らなくても、例えば、総和(g)=金貨＋銀貨＋銅貨＋鉄貨と、積和(g)=金貨＊１＋銀貨＊２＋銅貨＊３＋鉄貨＊４、の値という二つの情報を追加してもらっていれば、どれがどれだけおかしいかがわかります。算数の範囲で、エラー訂正ができるんですよ。
ここまで考えよう。二つの未知数（エラーの場所と、エラー量）を、二つの計算式（和と、積和）から求めているのわかりますか？連立２元１次方程式といているんですよ。 同じように、方程式増やすと、エラー一つじゃなく、複数あるエラーを訂正することも可能なんやと。ワイは頭悪いから回路作られへんけど。 さらに悪い子をみんな一緒にすると、愚連隊になって、暴動起こすので、小刻みなグループに小分けして、一人づつ片づけて、みんなきれいにできるようにするんやと。これをインターリーブドと呼びます。ついでに、二重にパリティつくって、さらに訂正能力上げる工夫もありえます。 クロス・インターリーブド・リードソロモン符号というのがCDの訂正用符号としてさいようされています。
興味がわいたらホームページの方も読んでね。ここまでは、最初の
入門のページはこの内容で、算数がわかればだれでもわかるエラー訂正です。算数だと効率悪いので、ガロア体とか難しい数学つかって、回路やプログラムを効率的につくることになりますが、原理は同じ。
PR
