エラー訂正回路・方式の入門(ecc1)

2018.03.11(since2017.1.1)
サイトマップ 、　トップ 　<< 訂正 <*> ECC2

１．基本

「刑事コロンボ」で、高IQ人倶楽部殺人事件「殺しの序曲 」の中で、犯人がコロンボに出題した挿話『偽金貨の見分け方』を、ご存じですか？　このなぞなぞに興味を持った人多いようでネット上で解説いっぱいあります。　実は、その回答が、エラー訂正の原理です。　（2018.03.11)他のページで１題目の解答気に食わないと記載したけど、ブルーバックスの”世界の名作推理パズル１００　中村義作著”にも類似問題取り上げられていたのでやはり有名パズルだったようです（刑事コロンボで最初見たときに知っている問題のように感じた記憶があるのは本当だったかな）。

Q１.偽金貨の見分け方　殺しの序曲より

複数の袋にそれぞれ複数の金貨が入っている。１袋だけ全部偽物金貨である。袋の数や金貨の数はいくら多くてもいい。偽造金貨は重量が違う。例えば本物の金貨が一枚100gで、偽造金貨は一枚90gとする。この状況で、１回だけ重さを計り、偽物を当てよ（放映の詳細覚えてないので、逸脱しない範囲で問題を作りました：DVD見直せば確認できるけど、話の流れに都合のいい設定が良いのが本音)。

A1.　４袋の例（３袋目が偽物とする）を考える

一袋目から１枚、二袋目から２枚、三袋目から３枚、４袋目から４枚の金貨を取り出して、(1+2+3+4=）10枚の合計重量[(1+2+3+4)*100=1000g　理想値]を、測定する。偽金貨は-10g/枚。

ここからわかるように、期待値(1000g)から、実測値（例えば970g)を引いて、これを１枚の誤差量(10g)で割った値

３　=　(1000-970)/10

が間違いの場所・袋（ロケーション）を示すことが分かります。　これがまさに、エラー訂正システムで、エラーの位置を見つけるという事なのです。
これは、TVのなぞなぞでしたが、そのまま実用できるかというと、　誤差（例では-10g)が事前にわかる訳がない（１枚づつ計ったら、それがわかった時点で偽物発見の目的達成です）。

補足ですが、全袋秤に乗せて、一袋づつおろして、重さがおかしなものを探すとかいうのは、一度の測定というルールに反してますし、各袋の金貨の数も不定です。１０ｇ軽いのが１０枚と、正常なもの９枚と同じ重さですね？だから偽物の袋単体の重さで、10gの誤差起因の端数が見えない場合もあります（各袋数量不明という設定なのでこういうアプローチはだめ）。だったら、枚数不定でなく、例えば、１枚づつ袋から取り出してまとめて図って、１枚づつ取り除いて重量変化見るというのも、やはり、測定は１度という条件にあてはまりません。　

もっとも、この例で１０枚１ｋｇの中の１０ｇを、ばねばかりで精度よく測れるか？とか、精度足りないから、天秤使う場合、分銅をとっかえひっかえ測定するのを１度というか？とつっこまないように(この測定精度の問題がでないのが、デジタルデータの数値としてのエラー訂正のいいところです)。

２．誤差を知る方法

上記の設問でも、実は、重要な情報が隠れて示されてされています。それは、”正しい金貨の重さが100g”です。この情報をもとに、さらに追加一度の測定で誤差量を知ることができます。わかりますか？実は上の補足でちょこっとヒントがあったりします。

答え
前の例で、４袋すべてから、１枚づつ金貨を抜き取って、４枚まとめて一度に重さを測ります。
　　：全部本物　　　　　：400g
　　：本件（一枚誤）　　：390g　
１枚の重さの情報から４枚の期待値が導き出され、実測値の差(4*100-390)＝誤差：10gが、わかるのです。
誤差が解れば、前述A1の袋ごとの重みづけ（枚数を変える）して、どれが、間違いかを、個別測定しなくても、１度の測定で知ることができるわけです。

つまり、適当な情報がわかっていれば、２回の測定で、偽物の重さ量と、偽物１つを指摘することができるという事です。まさにエラー訂正システムです。

では、ここまで理解できたか、頭の整理をしましょう

Q２.誤差量も測定する拡張版

金貨100g、銀貨90g、銅貨80g、鉄貨50gです(1)。
金貨、銀貨、銅貨、鉄貨１枚づつの重さの合計は ( (1)から計算できるが）、実測310gでした。
金貨*1+銀貨*2+銅貨*3+鉄貨*4の重さ（同様計算できる）は、700gでした。どの貨幣がいくら重さが違うでしょうか？

A2.　銀貨が10g軽い（＝８０ｇ）というのが正解です。

事前事後の追加情報あれば、誤り（にせもの）の検出、誤差量の算出ができることが理解できたと思います。

話の流れにしたがって、余計なデータを残していますが、もっと汎用的なエラー訂正問題らしい記述に直してみます。

Q3.金貨＋銀貨＋銅貨＋鉄貨の１まいづつの合計は320ｇ。金貨*1+銀貨*2+銅貨*3+鉄貨*4の合計は720gと納品仕様書に記載あります。受け入れ納品チェックで前者が310g、後者が700gです。なにが起きたでしょうか？

訂正問題らしいでしょ？。各硬貨の重さ情報無くても、どれが、いくら誤差があるかがわかります。貨幣の場合は、偽物がわかっても偽物を使えないだけですが、データの場合、どれが、いくら間違っているかわかれば、元の正しいデータに訂正できて、データ全体を使用することが可能になります。　偽物金貨の場合使えないだけといいましたが、この場合も、本物届いたら、その１枚と、偽物に誤差相当の１０ｇの分銅加えて補正し、両社がつりあうかどうかみることで、、今度は本物だと判定に使えます。　訂正というのが、本物の重さ知らなくても、誤差１０ｇを補正して、正しい重さを表現できるという運用例になります。

要するに、データ伝送において、決まった手順による総和と、積和の２つの情報（パリティ）の追加するシステムにすれば、個々の本来の値などしらなくても、エラー訂正が可能であるという事です。

ここまで理解できれば実は、効率（コストパフォーマンス）を優先しなければ、エラー訂正システム（パリティ）を作ることが可能です。

問Q4．オリジナルデータ　d(n).....d(1)があるこのデータのエラー訂正を系を作れ。

回答例A4。
記録系（送信系）

データ系列　d(n)...d(1)　から、パリティ（シンドローム）データを計算する。
S1=Σd(n)*n,
S0=Σd(n)
データとして、d(n)...d(1),S1,S0　を記録する

再生系（受信系）

データを読みだして、それぞれdi(n)とし、下記パリティを計算する。

Si1=Σdi(n)*n 　;シンドローム１と呼称
Si0=Σdi(n) 　　;シンドローム０と呼称

エラー検出・訂正実行
if (Si1=S1)&(Si0=S0) 　
　　　　then エラーなし
elseif (S1-Si1)/(S0-Si0) =m -> 1..n の整数
　　　　then d(m)正=di(m)誤有+(S0-Si0)
else 訂正不能（１ケエラー以上）

簡単・便利でしょ？　違う視点から見てみましょう。　m番目にΔｍという誤りがあったとします。すると、

Σdi(n)*n - s1 =　数値　= m*Δm
Σdi(n) - s0 = 　数値　=　Δm

となりますね？　Δｍと、ｍを２つの変数とする連立２元１次方程式を解いているのです。

補足：
ここでは、２パリティで、１ケ訂正ができることを示しました。パリティを増やせば、２個訂正だって可能です。間違い場所ｎとｍ、および誤差ΔｎとΔｍの４つの未知数を、連立４元方程式をたてれば解けます（論理回路で解くのは、ちと難しくなるけど。素になって考えるとどういう回路でこんな方程式解くんだろうねぇ）。

例えば、関連技術としては、オーディオCDのエラー訂正コード系（CIRC）でも2重訂正符号で、最初のC1では４バイトパリティで２け訂正、C2では、C1で見つけた訂正不能場所情報をもとに、４バイトパリティで４ケ訂正（イレ―ジャ：消失訂正というのかな？）ができるようです。ちょっと勉強しとけばよかったなぁ

そうそう、オーディオCDは、CD-ROMと比べて訂正がないとか、弱いという誤解・風評もあるようですが、それは間違い。

CDは上述の２け４けという強力なエラー訂正が実装されています。CD－ROM専用訂正は、１け訂正が２重なのでCDDAの方が強力です(詳細は上のリンク先でも読んでください)。　ただし、CD-ROMにも、このCDの訂正機能が最初に働くので、CD-ROMは、CDと共通の強力な２重訂正による訂正後さらに残った（あるいは間違えて壊して壊した：やりすぎ）エラーに対して、補間（前（後）から推定近似すること）ができない用途が重要なので、たった１バイトのために全滅するくらいなら、記録容量削ってでも、訂正コードを追加してさらに訂正能力を向上させている（ディスク再生時から数えると別グループにわけて４重訂正）と理解してください。音楽なら前後の平均値と、真値は、単発エラーは普通の人は区別できないはずです。極論いえば、上位８bitが正常なら下位8bitに誤りがあっても、音の大きな所ならわからないかもしれません。また、フォトCDのように、静止画なら、１ビットおかしな点があっても、簡単に修正できるし、どのみちリサイズや色補正するあるだろうからと、用途・程度によっては、気にしなくてもよいかもしれません。　しかし、ブログラムなら暴走してPCすら壊すかもしれませんし、データで、例えばスケジュール間違えて、振り込み１日遅れたので倒産という話だってありえます。　だから、１バイトでもだめなら全部捨てるという事もありえるのです（少なくとも、正常データでないということが解れば、別の対策考えることができる）。
定量的に比べると、CDROMが2352バイトに対して、（43ケ／26ケの２重訂正）。　CDの場合24バイトに対して上記訂正なので、同じ単位（24*98=2352）にすると、98*(　２ケ／4ケ）訂正とCDの方がC1訂正可能数だけみても強力です。CDROMはこれだけ訂正された上に、（43/26）＊２ケ訂正できるわけですから、データ記録にも安心だと思うでしょう？　データ数の数え方にパリティを含むが対象外データもあるCD-ROMとパリティ含まないCDの相違があるから、比較対象が微妙に違うとかいう細かい点は気が付かないように。

試作製品でオーディオリッピングでデータ化けしたというクレームがあって、調べると音楽CDとしての訂正機能（CIRC訂正）時に非常にエラー多い場所に相当する事例で、誤訂正発生（間違って正しいデータを壊してしまう＆エラーを見逃す）しても不思議でないので、あまりにエラーが多い場合はあえて訂正符号能力いっぱい使わないで、怪しいものは補正する方が、オーディオシステムとしては安全かもしれないと、お茶を濁す提言（言い訳）に納得してくれたようで、その後音沙汰なしですが、割と定評あるシステムを開発する所だと風の便りに聴いたきがします。

ここで言いたいのは、めいっぱい頑張ると、ぷっつんする可能性があるのでやりすぎないように！という人生訓かな？

サイトマップ 、　トップ 　<< 訂正 <<*>　 ECC2