上の本も参考に・・・
BCH,リード・ソロモン符号の発想は、1961年の論文で発表されました。数学の抽象代数を使う理論です。
以下は、友達から教えてもらいました!
引用元は、グーグルサーチで、刑事コロンボ+エラー訂正 で見つかるところです。
■
昔訂正システム(再生系)開発に従事したことがあります。CDやCDROMイエローブックをもとにして、エラー訂正の原理をわかりやすく解説してみましょう。
初っ端は、昔懐かしい”刑事コロンボ”から”殺しの序曲”で取り上げられた偽金貨発見問題に 題材をとってみました。リードソロモンとかいうキーワードが出没するシステムだったりします。
■
ちなみに、想定しているのは、CDのレッドブックじゃなく、CDROMのイエローブックです(細かいところは、いろいろリサイズしたものですけど)。が、似たようなものです。 CDのレッドブックは音が途切れてはいけないので、C1,C2の二重訂正を繰り返すことはないはずですが、CDROMのイエローブックは、エラーがあるのは厳禁なので、QPという訂正をエラーがなくなるまで繰り返し。エラーがきえなければ、再度ディスク読みなおし。それでもだめなら、OSにディスクエラーと報告。
エラー訂正回路・方式の入門(ecc1)
2022.06.29(since2017.1.1)
(2021.10.09)ここをリンクした刑事コロンボファンサイトみつける。
(2022.06.29)前回コロンボの再放送あったときに、グーグルの検索クリック回数が24回に増えたと報告うけました。今回の放映はどうかなぁと思うとちょっと残念な結果。グーグルの検索の表示順番さがってるし、MSNだとみつからないし、仕方ない結果ではある。 まあ、コロンボ人気に便乗して、興味ない人をむりやり引き込んだだけという意見はあるけれど。
1.基本
「刑事コロンボ」で、高IQ人倶楽部殺人事件「殺しの序曲 」の中で、犯人がコロンボに出題した挿話『偽金貨の見分け方』を、ご存じですか? このなぞなぞに興味を持った人多いようでネット上で解説いっぱいあります。 実は、その回答が、エラー訂正の原理です。 (2018.03.11)他のページで1題目の解答気に食わないと記載したけど、ブルーバックスの”世界の名作推理パズル100 中村義作著”にも類似問題取り上げられていたのでやはり有名パズルだったようです(刑事コロンボで最初見たときに知っている問題のように感じた記憶があるのは本当だったかな)。
Q1.偽金貨の見分け方 殺しの序曲より
複数の袋にそれぞれ複数の金貨が入っている。1袋だけ全部偽物金貨である。袋の数や金貨の数はいくら多くてもいい。偽造金貨は重量が違う。例えば本物の金貨が一枚100gで、偽造金貨は一枚90gとする。この状況で、1回だけ重さを計り、偽物を当てよ(放映の詳細覚えてないので、逸脱しない範囲で問題を作りました:DVD見直せば確認できるけど、話の流れに都合のいい設定が良いのが本音)。
A1. 4袋の例(3袋目が偽物とする)を考える
一袋目から1枚、二袋目から2枚、三袋目から3枚、4袋目から4枚の金貨を取り出して、(1+2+3+4=)10枚の合計重量[(1+2+3+4)*100=1000g 理想値]を、測定する。偽金貨は-10g/枚。
偽物 | 偽 枚数 |
誤差 | 総重量 (g) |
無し | 0 | 0 | 1000 |
1袋目 | 1 | -10 | 990 |
2袋目 | 2 | -20 | 980 |
3袋目 | 3 | -30 | 970 |
4袋目 | 4 | -40 | 940 |
ここからわかるように、期待値(1000g)から、実測値(例えば970g)を引いて、これを1枚の誤差量(10g)で割った値
3 = (1000-970)/10
が間違いの場所・袋(ロケーション)を示すことが分かります。 これがまさに、エラー訂正システムで、エラーの位置を見つけるという事なのです。
これは、TVのなぞなぞでしたが、そのまま実用できるかというと、 誤差(例では-10g)が事前にわかる訳がない(1枚づつ計ったら、それがわかった時点で偽物発見の目的達成です)。
補足ですが、全袋秤に乗せて、一袋づつおろして、重さがおかしなものを探すとかいうのは、一度の測定というルールに反してますし、各袋の金貨の数も不定です。10g軽いのが10枚と、正常なもの9枚と同じ重さですね?だから偽物の袋単体の重さで、10gの誤差起因の端数が見えない場合もあります(各袋数量不明という設定なのでこういうアプローチはだめ)。だったら、枚数不定でなく、例えば、1枚づつ袋から取り出してまとめて図って、1枚づつ取り除いて重量変化見るというのも、やはり、測定は1度という条件にあてはまりません。
もっとも、この例で10枚1kgの中の10gを、ばねばかりで精度よく測れるか?とか、精度足りないから、天秤使う場合、分銅をとっかえひっかえ測定するのを1度というか?とつっこまないように(この測定精度の問題がでないのが、デジタルデータの数値としてのエラー訂正のいいところです)。
2.誤差を知る方法
上記の設問でも、実は、重要な情報が隠れて示されてされています。それは、”正しい金貨の重さが100g”です。この情報をもとに、さらに追加一度の測定で誤差量を知ることができます。わかりますか?実は上の補足でちょこっとヒントがあったりします。
答え
前の例で、4袋すべてから、1枚づつ金貨を抜き取って、4枚まとめて一度に重さを測ります。
:全部本物 :400g
:本件(一枚誤) :390g
1枚の重さの情報から4枚の期待値が導き出され、実測値の差(4*100-390)=誤差:10gが、わかるのです。
誤差が解れば、前述A1の袋ごとの重みづけ(枚数を変える)して、どれが、間違いかを、個別測定しなくても、1度の測定で知ることができるわけです。
つまり、適当な情報がわかっていれば、2回の測定で、偽物の重さ量と、偽物1つを指摘することができるという事です。まさにエラー訂正システムです。
では、ここまで理解できたか、頭の整理をしましょう
Q2.誤差量も測定する拡張版
金貨100g、銀貨90g、銅貨80g、鉄貨50gです(1)。
金貨、銀貨、銅貨、鉄貨1枚づつの重さの合計は ( (1)から計算できるが)、実測310gでした。
金貨*1+銀貨*2+銅貨*3+鉄貨*4の重さ(同様計算できる)は、700gでした。どの貨幣がいくら重さが違うでしょうか?
A2. 銀貨が10g軽い(=80g)というのが正解です。
事前事後の追加情報あれば、誤り(にせもの)の検出、誤差量の算出ができることが理解できたと思います。
話の流れにしたがって、余計なデータを残していますが、もっと汎用的なエラー訂正問題らしい記述に直してみます。
Q3.金貨+銀貨+銅貨+鉄貨の1まいづつの合計は320g。金貨*1+銀貨*2+銅貨*3+鉄貨*4の合計は720gと納品仕様書に記載あります。受け入れ納品チェックで前者が310g、後者が700gです。なにが起きたでしょうか?
訂正問題らしいでしょ?。各硬貨の重さ情報無くても、どれが、いくら誤差があるかがわかります。貨幣の場合は、偽物がわかっても偽物を使えないだけですが、データの場合、どれが、いくら間違っているかわかれば、元の正しいデータに訂正できて、データ全体を使用することが可能になります。 偽物金貨の場合使えないだけといいましたが、この場合も、本物届いたら、その1枚と、偽物に誤差相当の10gの分銅加えて補正し、両社がつりあうかどうかみることで、、今度は本物だと判定に使えます。 訂正というのが、本物の重さ知らなくても、誤差10gを補正して、正しい重さを表現できるという運用例になります。
要するに、データ伝送において、決まった手順による総和と、積和の2つの情報(パリティ)の追加するシステムにすれば、個々の本来の値などしらなくても、エラー訂正が可能であるという事です。
ここまで理解できれば実は、効率(コストパフォーマンス)を優先しなければ、エラー訂正システム(パリティ)を作ることが可能です。
問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 ;シンドローム1と呼称
Si0=Σdi(n) ;シンドローム0と呼称
エラー検出・訂正実行
if (Si1=S1)&(Si0=S0)
then エラーなし
elseif (S1-Si1)/(S0-Si0) =m -> 1..n の整数
then d(m)正=di(m)誤有+(S0-Si0)
else 訂正不能(1ケエラー以上)
簡単・便利でしょ? 違う視点から見てみましょう。 m番目にΔmという誤りがあったとします。すると、
Σdi(n)*n - s1 = 数値 = m*Δm
Σdi(n) - s0 = 数値 = Δm
となりますね? Δmと、mを2つの変数とする連立2元1次方程式を解いているのです。
補足:
ここでは、2パリティで、1ケ訂正ができることを示しました。パリティを増やせば、2個訂正だって可能です。間違い場所nとm、および誤差ΔnとΔmの4つの未知数を、連立4元方程式をたてれば解けます(論理回路で解くのは、ちと難しくなるけど。素になって考えるとどういう回路でこんな方程式解くんだろうねぇ)。
例えば、関連技術としては、オーディオCDのエラー訂正コード系(CIRC)でも2重訂正符号で、最初のC1では4バイトパリティで2け訂正、C2では、C1で見つけた訂正不能場所情報をもとに、4バイトパリティで4ケ訂正(イレ―ジャ:消失訂正というのかな?)ができるようです。ちょっと勉強しとけばよかったなぁ
そうそう、オーディオCDは、CD-ROMと比べて訂正がないとか、弱いという誤解・風評もあるようですが、それは間違い。
CDは上述の2け4けという強力なエラー訂正が実装されています。CD-ROM専用訂正は、1け訂正が2重なのでCDDAの方が強力です(詳細は上のリンク先でも読んでください)。 ただし、CD-ROMにも、このCDの訂正機能が最初に働くので、CD-ROMは、CDと共通の強力な2重訂正による訂正後さらに残った(あるいは間違えて壊して壊した:やりすぎ)エラーに対して、補間(前(後)から推定近似すること)ができない用途が重要なので、たった1バイトのために全滅するくらいなら、記録容量削ってでも、訂正コードを追加してさらに訂正能力を向上させている(ディスク再生時から数えると別グループにわけて4重訂正)と理解してください。音楽なら前後の平均値と、真値は、単発エラーは普通の人は区別できないはずです。極論いえば、上位8bitが正常なら下位8bitに誤りがあっても、音の大きな所ならわからないかもしれません。また、フォトCDのように、静止画なら、1ビットおかしな点があっても、簡単に修正できるし、どのみちリサイズや色補正するあるだろうからと、用途・程度によっては、気にしなくてもよいかもしれません。 しかし、ブログラムなら暴走してPCすら壊すかもしれませんし、データで、例えばスケジュール間違えて、振り込み1日遅れたので倒産という話だってありえます。 だから、1バイトでもだめなら全部捨てるという事もありえるのです(少なくとも、正常データでないということが解れば、別の対策考えることができる)。
定量的に比べると、CDROMが2352バイトに対して、(43ケ/26ケの2重訂正)。 CDの場合24バイトに対して上記訂正なので、同じ単位(24*98=2352)にすると、98*( 2ケ/4ケ)訂正とCDの方がC1訂正可能数だけみても強力です。CDROMはこれだけ訂正された上に、(43/26)*2ケ訂正できるわけですから、データ記録にも安心だと思うでしょう? データ数の数え方にパリティを含むが対象外データもあるCD-ROMとパリティ含まないCDの相違があるから、比較対象が微妙に違うとかいう細かい点は気が付かないように。
試作製品でオーディオリッピングでデータ化けしたというクレームがあって、調べると音楽CDとしての訂正機能(CIRC訂正)時に非常にエラー多い場所に相当する事例で、誤訂正発生(間違って正しいデータを壊してしまう&エラーを見逃す)しても不思議でないので、あまりにエラーが多い場合はあえて訂正符号能力いっぱい使わないで、怪しいものは補正する方が、オーディオシステムとしては安全かもしれないと、お茶を濁す提言(言い訳)に納得してくれたようで、その後音沙汰なしですが、割と定評あるシステムを開発する所だと風の便りに聴いたきがします。
ここで言いたいのは、めいっぱい頑張ると、ぷっつんする可能性があるのでやりすぎないように!という人生訓かな?
パフォーマンスを考慮した場合の問題点(ecc2)
普通の四則演算を使うとパフォーマンスが悪い(早い話乗算難しい)。有効ビットか掛け算そのものが大変だとか。を解説
2017.10.11(since2017.1.1)
効率を論議するのに、まず問題点(コスト)を考えます(余裕があるなら前節のような単純積和で十分だと思います)。(2018.08.19)とはいえちょっとページ末で雑談追記)
問題点を(適当なコストパフェ―マンスで)合理的に克服しているのが、次の節で触れるガロア体と呼ばれる剰余系の演算体系になります。まず問題になる事の解説から。
3-1)掛け算って実はとても大変。
日本では小学校で九九を暗記しますから1桁どうしの掛け算なら条件反射でわかりますが、2桁の掛け算は普通の人が電卓等が使えないなら(暗記しているという噂のインドの人やそろばんの達人ならともかく)、筆算するのが普通だと思います。 これから、ディジタル処理を念頭において考えるので、同様に2進数でのひっ算も表記します。
現行代表的なRISCのARMプロセッサなら、
MUL r2,r0,r1
;r2 = r1 * r0 (32bit)
と、32ビット乗算が、1命令(実行も1ck)で実現できます。つまり一括演算の巨大高速掛け算機を持っているということです。同様に、産業界で重用されるるH8プロセッサでも
MULXU.W R0,ER1
;ER1 = R0 * R1 (16 * 16 ->32)
と、1命令で実行できます(とはいえ、実行に20クロック必要だったり、そもそも動作可能クロック周波数も違うので、ARMと比べればかなり遅い。物量主義でなく繰り返し加算で結果を出すタイプなんでしょう(ひっ算している感覚だと思っていいでしょう)。
一方、Z80などの古い世代のCPUは、乗算命令が存在しません。したがって、プログラムで乗算を実行します。
具体的に、Z80のソフト例や、それイメージしたハードウエア(ゲートレベル)イメージを別ページで、解説します。
先に見といてください( 掛け算まとめ(乗算1) )
任意の数字x任意の数字の回路やソフトの実現が大変だというイメージは乗算1を読んで理解していただけたでしょうか?
でも、一方、固定値の掛け算であれば、引き算とか混ぜて、かなり楽に作れるのも、理解していただけたと思います。
では、これらを総合的に考えて、複雑な掛け算機・掛け算ソフトを用いないで、エラー訂正を行うのはどうすればいいでしょうか?
それには、汎用ではなく、(簡単につくれる)固定値の掛け算機αを用意することです。すると、(α=単位元”1”でない限り) α、α^2、α^3...は、異なる数字になります。n項目は前例で、n倍する(nを乗じて)していましたが、代わりにα^nを乗じることで、方程式を解けば、エラーの場所とエラー量が求められるわけです。汎用の複雑な回路ではなく、固定値の掛け算でコスト削減という作戦です。
ここで、例えばα^4は、同じ掛け算機を4回もつかって、汎用掛け算という負担を繰り返しの時間(回数)に振り替えただけで、本質的に大変なのは変わらないと、考えたあなたへ。 いい考えです、でも、もうひと押し考えましょう。
データd[n]系列に対して、
Σα^n*d[n]
=α^n*d[n] + α^(n-1)*d[n-1] + a^(n-2)*d[n-2] +...+α^2*d[2] + α*d[1] + α^0*d[0]
αでくくってみます。工夫すると、
=α*{ α*(α*....α*( α*( α*d[n]+d[n-1] ) + d[n-2] ) +d[n-3].).).+d[2]) + d[1] } + d[0]
いや、もっと見やすく書くと
=(((....(.(d[n]*α +d[n-1])*α +d[n-2])*α +d[n-3])*α+...)*α+.d[2].)*α +d[1])*α +d[0]
この式の素敵な意味が解りますか?(ちょっと雑談逆ポーランド法)
もとの、Σn*d[n]の計算量は、2n-2回 、Σd[n]の計算量は、n-1回
αを使うとき、すなおに、Σを展開して各項に指数違いのαをかけると、データごとに、掛ける回数が変わり、結局大変で 計算量は Σ(n+1)-3 回
でも、上記αで括った式の意味は、最初のデータd[n]にα倍し、次のデータd[n-1]を加える。この和をα倍して次のデータd[n-2]を加える。 これ以降同様に、またαをかけて、次のデータを加える。つまり、積和の繰り返しで、合計2n-2の計算回数で実現できます。乗算と加算を同じ演算回数カウント正しいか?と疑問のあなたへ。掛け算回数だけ考えても、同じでしょ?
ここで重要なのは、何回目の繰り返しという条件が入るわけでなく、ただ同じ数をかけて、入ってきたデータを順に加算するという単純繰り返しだけでいいというのがポイントです。(有効桁数は、事前に検討して確保しておけば、オーバフローの判定する必要ありません)。
いいかえると、式の変形、計算順番さえ工夫すれば、汎用積算機で、Σn*dnを求めるのと、Σα^n*dnが、ほぼ
同じ計算回数で実現できるのが分かります。 汎用積算機ではなく、比較的簡単につくれる固定積算機の運用で、また、何データ目という判断処理することなく、エラー訂正(パリティ:シンドローム演算)が、時間負担増加すること無くできるわけです。
厳密にいうと、Δmと、Δdm*α^m から、mというロケーション場所を、一発回答はちょっと難しいという問題はあります。 電卓・算数なら、対数つかって算数的に計算できますが、そんな回路・演算ソフトはもっと大変です(さらに正確さを求める訂正に、途中で少数が発生する対数というのもありえません)。
すると、Δdmと、Δdm*α^mから、mを求める方法は、回帰的に
Δdmに、αを繰り返しかけて、Δdm*α^mになる回数を数えるか
Δdm*α^mを、αで繰り返し割って、Δdmになる回数を数えるか
くらいしか、思いつきません。
割り算回路を、ちょっと考えてみます。確かに、1/2とか、1/4とか2のべき乗なら、ビットシフトだけで実現できますが、汎用の割り算ねぇ..思いつくのは、引き算を繰り返して、0になる回数(割り切れない場合は、負にならない直前の回数)を、数えるくらいかな(さすがに安直すぎる)...ひっさんのように、最大値になるようビットシフトしてから、挽るか引けないか(マイナスになる)を、いちいち引いてみながら(確認しながら)、引く数をシフトダウンしながら行く方法しかないですね。
掛け算は、まだ分割加算で最終ビット長さ確保しておけば何とかなるけど、割り算は割り切れるかどうかの判断がはいるので面倒ですね。(単純引き算ではなく、ビットシフトしながら大きな数から順番に引き算して、引けるもと引けないもので割り全結果を求めるのがROMテーブル使わないなら最適解でしょう)。
すると、シンドローム演算にも使うα倍掛け算を兼用し、Δmに繰り返しかけ続けて、Δm*α^mになる回数を数えて、mを求めるのがとりあえず簡単です。
これは、α^mだから難しいという話では無く、ΔmとΔm*nから、割り算して、nを求めるのも回路として難しいという意味です。 こっちもやれといわれると、ひっ算風にビットシフトしながらこのシフトデータで引けるか引けないか判断して、1ビットづつ商を積むのが正解でしょうけど。 Δmに値を順に変えながら掛け算実施して、Δm*mとなるmを求めるというのも、スマートではないですね(要するにnを掛けても、α^nを掛けても、割り算でnを求めるのは難しいという意味です。
3-2)情報量(ビット長)が膨大に
データ8ビットを想定します。掛け算8ビットを実行すると16ビットデータとなりますね?さらに、前述のS1=Σn*Dnを考えるのに、16bitデータ16個の加算と考えると16+4=20bit最大になるのがわかりますね? さらにS0=ΣDnも、上記で12ビットになります。
合計32ビット=4バイト分(データ処理方法を考えると3バイト+2バイトの5バイトが本筋)。 たかだか16バイトデータに訂正用データ=パリティを5バイトつけるというのは、もったいないですね?約24%が本来必要でないデータなんです。
データとその検査という寄り道雑談。
8ビットパソコン(当時マイコンという)の時代には、雑誌にBASIC言語のリスト以外に、機械語ダンプリストが頻繁に載っていて、(普通の人に意味不明の)16進データをひたすらPCに入力すると、間違いなければ、ソフト(ゲームとか)が動いたりしていましたが、機械語は、1ビット違うと、暴走することもありますから、入力間違いを検出するために、データと一緒にチェックサムというエラー検出情報(あくまで検出で訂正ではない)を印刷してました。
チェックサム計算ソフトで自分の入力したデータの計算したチェックサムと、と印刷物の目視比較での間違いを見つけました。この1行(1列)に間違いがあるとわかれば、にじんで見にくいTV画面上の文字をその行列一生懸命見たものです。 (内蔵BASICインタプリタのバグで時々入力が化ける可能性もある)横40文字の見やすいきれいな表示を使うか、大量に見えるがボケた横80モードを使うか、専用モニタ買えない貧乏学生の悩みはつきない。
余談ついでに。TV画面のぼけた文字見るのが大変なので、第二精工舎の安いドットマトリクスプリンタに飛びついた思い出あります(NECやエプソンの定番機15万円くらいに対して半値以下7万円くらいのモノハンマーという廉価版プリンタでうるさく遅かった:漢字ROMなど当然ない英数字ベース。 トラクターフィードという、紙の両端に定間隔で穴が開いていて、それを、ひっかけて紙送りするシステムです。そのプリンタの他の用途として、演習問題で方位ごとに計算して指向性パターンを書けという宿題がでたとき、繰り返し演算面倒だったので、プログラムで計算してついでに、グラフィック印刷して提出した時や、別の授業で興味を持ち予め作っていた最小二乗法の計算ソフトで宿題解いて報告したら、当時まだパソコン(マイコン)使う人少なかったので、講義の担当教授が、研究室配属時ぜひおいでという、お愛想をいただいたことがありました。その研究室に行った人に聞くと、当時使っていた古い計算機上のテープベースの古い専用ソフトをBASIC言語で使いやすいものにしたかったらしい。(配属先抽選大会で、クラス最後から5番目の選択権という)くじ運悪い自分は、選択の余地の無い配属にきまりました。 ただその先生のところへ行きたいか?というと、怖いイメージの先生なので行かなかったかな。
さて本題にもどる。16バイトに1バイトの雑誌市場で受け入れられたチェックサムに対して、訂正場所探して、値まで自動訂正できるとはいえ、めったに誤りがないとすると、5バイトは追加データ量が大きすぎると思いませんか?(機能させるには、これもデータとして、PCに入力しないと、頭の中で暗算でエラー検出・訂正無理です)。
3-1)で示した掛け算がハードでもソフトでも実は大変だという話と、このビット長が多くなりすぎるという問題を、数学的に解決できるのがアイデアが、次節で紹介するガロア体と呼ばれる剰余系計算体系の利用という話になります。
余談ながら、α^n係数をかける場合、α=2の場合でも、2個で2^2→2ビット、16個なら、15ビット桁数が上がってしまいます。さらに、Σ加算でその数に応じて桁数が増えてしまいます。いやですよね?
例えば、ARM64bitプロセッサで、掛け算を含む演算速度も、パリティのバイト長やデータビット長(一言でいえば空メモリ量)も、ハード上余裕があると豪語するなら、以降読む必要ありません。ここまでの情報で訂正システム利用できます。コストパフォーマンスのシステム判断(コストとパフォーマンスの妥協点をどこに置くかの判断)は重要です。
無線通信システムで、単純パリティでなく、それなりの検出コード(EDCコード)付けているものを見たことあります。これECC(エラー訂正コード)にすれば、やり直し通信しなくて、応答性改善できるのにと思ったものです。まあ、受信側が、ビット化けを許容して、ビットずれを起こさないで、最後まで通信してくれれば、何とかなりますが、受信打ち切られたり、ビットずれしちゃうと訂正無理(訂正許容個数を超えてしまう)から、そこまでやりたくないのかな? syncコードで同期検波するんだったら、そこまでやるのがいいと思うんだけど、システム設計に口をはさめるんなら文句を言いたかった:はて何のシステムの噂や、ぐちかな?。
まあ、あと、どの程度のデータ訂正能力をつけるか?(エラーが多い場合に間違って正しいデータを壊す確率とか、訂正グループの分散方法とか)というシステム設計上の問題はありますが、素人なのでここでは、扱いません。システム開発に必要な方は数学の専門家とどうぞ。
(2017.08.19)雑談です。確かにアプリケーションレベルでいえば、通常の四則演算によるシンドローム(積和、と和)で十分という話はあります。ところが、デバドラとかハードに直結する場合、必ずしもそうとは限りません。例えば、データ通信の信号が、GNDにショートしてしまった場合を予想してみましょう。データは0と判断するなら、積和も和も0となって、素直にエラー無しでめでたしめでたしとなってしまいます。 ちょっと思い出せないんだけど、何かのシステムでは、パリティ部分を論理反転して転送する決まりになっていたものがありました。この場合なら、データバスが0固定だという異常事態を簡単に検出することができるでしょう? ハードウエア直結の人の感性では、いろいろ考えるものです(必要かどうかは別として)。 こういうのが、エラー検出能力が優秀ななのかどうなのか数学屋さんの腕の見せ所だったりします。
ところで、GNDをショートして、0になったと仮説していますが、電気的に0という意味では必ずしもありません。通信でもっともPCと親和性があるのは、RS232Cだと思いますがこれは本来±12Vの2値の通信です。初期の8bitや16bitのPCでは価格を抑えるために、0V,5VのRS232Cもどき通信をしていました。パラレルデータとシリアルデータの変換(そこにはパリティの付加・検出もあるし、キャラクタデータ列の先頭示すスタートビットとか、キャラクタ(一般に8ビットですが、7ビットもある)の最後を示すストップビットを付加するとか、そもそも、常時信号ラインを監視して、データを取りこぼさず、CPU:ハードがデータ読み落とさないようにする機能(一言でいうと割り込みを発生させる)のIC(古くは8251UART)が、CPUと同じく5V駆動ですから、わざわざ、±12V用意したくないという意思があったりします。これを解決するのが、マキシムというメーカさんのMAX232シリーズIC。5V単一電源から、±12Vの通信ラインを運用できます。 デバイスメーカの開発ツールを、量産ラインに組み込むための設計仕様書つくるために、オシロで波形をみていたら、-12Vが、Hレベル、+12VがLレベルを示していたあれあれこれ普通なんだっけ?メーカ専用アプリの中で、情報漏洩しないように、細工してるんだっけ?と悩んだ思い出があったりします(考えてみると論理レベルのシリアル通信の解説よく見ますが、物理レベルってこの時まで考えたことなかったです)。
7bitと8bit。アスキーコードは大文字小文字数字と、コントロールコードをいれて、7ビットで欧米では十分だったので、通信が7ビットというのもあります。日本ではかなを必要とするので、どうしても8ビットが必要とされました(漢字はあきらめて2バイトに拡張)。+1bitしてASACII文字埋めて、あまるところに、メーカが特殊なキャラクターを定義していて、キャラクタベースのゲームでなんか愛嬌のある顔文字とか出てくる場合もあります(シャープさんが有名だったかな?)。 絵文字とか、顔文字がいま海外でも流行ってきたようですが、80年代そこそこに遊び心のあるメーカがあったということです。もちろん互換性は無い。 今もキャリア毎に携帯の絵文字キャラクタ違うので、キャリをまたいだメールでは文字化けあるでしょ? はっきり覚えていないけど、メーカ定義のキャラクタを使わないで、ユーザ定義のドット柄を各コードの文字として入れ替え登録するシステムがPC8001用に販売されて、グラフィックベースの遅いものではなく、キャラクタベースで快適に動くんだけど、面白いキャラクタが動き回るゲームが発表されてました(パックマンだか平安京エイリアンだか友達が買って確かの同じゲームでも家のPCメーカ定義キャラでなく、彼のそのゲームに特化したキャラにすることで、いかにも楽しそうに見えるので、ちょっと嫉妬しました(それ買うなら、FDかって、CPMというOSで遊びたかったので私はパス)
ガロア体(もどき)(ecc3)
2021.04.16(sicne2017.1.1)
とんちじゃないけど、上記の問題を解決するのが、ガロア体と呼ばれる剰余系システムです。前に示した四則演算と比べαを則とする剰余系を使うとリードソロモンの演算簡単なのよ。
(2021.04.16) 高速通信システムを手がける人から、ちょっと役に立つかもというメールもらった。 役に立ったと連絡くれた未知の人は初めてかも。なにかお役に立つのならと申し出たけれど、やりたいことがちんぷんかんぷんで断念。
そういえば、プリンタ型番書き間違えていて、旧モデルでも使えるという誤情報を書いていて、失望させてしまった恥ずかしい過去がありましたけど。
以下ガロア体理論をまじめに学んだことない者のたわごとです。勝手な思い込みにもどづく解説なので、内容に責任とれません(パテントなどの権利も不明です)。
訂正に使う演算として、掛け算を考えてみましょう。 例えば、8ビットデータに8を掛けることを考えてみます。定義域は0-255の8ビット幅で、値域は、0-2040と、11bitデータ幅になります。16倍すると最大4080と12ビットデータとなります。ビット長が大きくなることのデメリットは前に述べた通りです。
でも、使う数字の個数は?4を掛けると、0,4,8,12,16..と4つおき256種類になりますね?8倍するなら0,8,16,...の8つおき256種類。つまり、何を掛けるとしても、定義域(掛けられる数8bit)=256個なら、1:1演算結果は、値域の使用個数は、256個だけです。 値域:数値範囲としては、掛ける数によって、もちろん幅は広がります。 重要なのは、その演算が1対1で、逆算ができるということだけです。
1:1の関係がたもてるなら、8bitへの掛け算は、結果も256個(8ビット表現)で表現十分ですよね。剰余系というのがここで注目できます。 逆算が一意に定まる事だけが重要で、計算結果の(数値としてみた)大小関係が、例えば、α^2>α^3であっても、α+2>α+3であっても、あるいは、m*α^k > (m+n)*α^k 等と、普通の数学(実数世界)の大小関係と異なっても、(もちろん大小関係が一般的に普通な場合があっても、)何ら問題ありません。 一対一の一致だけ(等しい事が検出できる事)が重要で数値の大小に意味はありません。
また、数字バラエティ(ようは使う数字の個数)すくないので、m*α^n = j*α^k と重なってしまうものがでるはずです。 でも、問題にはなりませんよ、例えば10進の12という数字を考えてみましょう。 2x6=12ですが、4x3=12で異なる演算結果が値域で偶然一致します。しかし、値域で値が重なっても、6をかけて12になるのは2だけ、4を掛けて12になるのは3だけと、それぞれ、1:1が破たんしないことだけで、十分なのです。
足し算も8bit同士の最大となる加算は255+255=510(9bit)ですが、これも同様に、定義域の数に対して値域の数が1:1ということだけが重要です。これも8bit値域に反映するシステムで十分ですね。まさに剰余系で十分優秀です。
掛け算α倍という演算が、8ビット定義域に対して、8ビット値域に1対1逆算可能な定義ができて、さらに、α倍、α^2倍、α^3倍...が、それぞれ別の値になって、言い換えると{α^n}の集合体として、8ビット値域に収まるという計算体系が定義できるというのが素人考えで8ビットのガロア体という意味なんだろうと勝手に予測してみます。知らんけど(ここ関西弁ののりです)。
(ガロア体は難しそうなので)剰余系として演算どのような定義をすればよいか、考えてみましょうか?
加算は、入力AとBの間の2項の演算です。ビット毎に考えることにすると、論理演算として教科書に出てきやすいのは、AND,OR,EXORの3演算(NAND,NOR,EXNORはこれの論理反転出力なので原理は同じ)。
ANDやORの論理は、ある出力に対して入力Aが判っているときBが判断できるか?という逆演算に、不定(入力1つと、出力がきまっても、もう一方の入力が、0か1か判断できない場合がある)が生じます。したがって、逆算が必要な、今論議している演算方法としては、不向きです。EXORとかEXNORが、有力候補となります。
では×αは? これはここまで、一見αという数字と、入力データとの、2項演算(乗算)のように記述していますが、実は、入力に、α掛けたという出力を求めるという、単項演算です(本当の掛け算ではなく、単なる関数)。
例えば、ビットローテーションはどうでしょうか?8ビットデータのbit名を、A7~A0とします。つまり
A[7-0] = A7*2^7
+A6*2^6
+A5*2^5
+A4*2^4
+A3*2^3
+A2*2^2
+A1*2^1
+A0*2^0
ローテーション演算を行うαという関数に対して
B= α(A[7-0])
= A6*2^7
+A5*2^6
+A4*2^5
+A3*2^4
+A2*2^3
+A1*2^2
+A0*2^1
+A7*2^0
EXCEL風表記:
B= mod(A[7-0] , 128) * 2 + int(A[7-0] /128)
という剰余系掛け算(と勝手によぶ)を定義すると、
入力 | *α^1 | *α^2 | *α^3 | *α^4 | *α^5 | *α^6 | *α^7 | *α^8 | |
bit7 | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 | B7 |
bit6 | B6 | B5 | B4 | B3 | B2 | B1 | B0 | B7 | B6 |
bit5 | B5 | B4 | B3 | B2 | B1 | B0 | B7 | B6 | B5 |
bit4 | B4 | B3 | B2 | B1 | B0 | B7 | B6 | B5 | B4 |
bit3 | B3 | B2 | B1 | B0 | B7 | B6 | B5 | B4 | B3 |
bit2 | B2 | B1 | B0 | B7 | B6 | B5 | B4 | B3 | B2 |
bit1 | B1 | B0 | B7 | B6 | B5 | B4 | B3 | B2 | B1 |
bit0 | B0 | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
1対1の逆算可能な演算で、ビット長が増えないに見えます。しかし、この定義で、α^8=α^0 となってしまって、これ以上高次は、逆算が一意に決まりません(だからこの演算定義はガロア体とは言えない)。けれども、例に挙げていた金貨、銀貨、銅貨、鉄貨の4項しかないなら、使用するα^4,α^3,α^2,αの演算で1対1が確保できればよいので、掛け算αの定義は、これで、十分だと思いませんか? 残念甘い!
入力 | *α^1 | *α^2 | *α^3 | *α^4 | *α^5 | *α^6 | *α^7 | *α^8 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 1 |
2 | 4 | 8 | 16 | 32 | 64 | 128 | 1 | 2 |
3 | 6 | 12 | 24 | 48 | 96 | 192 | 129 | 3 |
4 | 8 | 16 | 32 | 64 | 128 | 1 | 2 | 4 |
5 | 10 | 20 | 40 | 80 | 160 | 65 | 130 | 5 |
6 | 12 | 24 | 48 | 96 | 192 | 129 | 3 | 6 |
7 | 14 | 28 | 56 | 112 | 224 | 193 | 131 | 7 |
.. | .. | .. | .. | .. | .. | .. | .. | .. |
254 | 253 | 251 | 247 | 239 | 223 | 191 | 127 | 254 |
255 | 255 | 255 | 255 | 255 | 255 | 255 | 255 | 255 |
確かに乗数に関しては、7乗までは一意に定まりますが、入力255に対して、αの何乗しても255固定です。データを作るとき、0から100しか使わないという使用条件があったとしても、エラー訂正の時、演算途中の偶然も、誤差255の時も、もう判断不能です。エラー訂正に使えそうもありません。
剰余系で、エラー訂正に使えるαの定義(ガロア体多項式の解の定義)は、思い付で適当に試しても、簡単にうまくいかないようです。 10進実数演算の前述の方法でαは、2倍でも、3倍でも定義し、エラー訂正可能ですのにね(訂正能力:誤訂正抑止能力が高いかどうかは数学屋さんにおまかせします。データの距離のような説明があるんだけど、ちとむずかしい)。
だからこそ特定の”α”を法とする剰余系ガロア体を定義できた数学屋さんえらい。
試しに、この前に、exor1ケのローテーション系回路作ったら、そのどのビットペアで演算するかによって、α^14でもとに戻ったり、α^31でもとに戻ったり。で、使えない(後で調べたら後者は偶然GF(2^5)の生成多項式α^2+1を使った場合でした)。じゃあどうしようかと、イエローブック検索したけど中身は検索不能。 あきらめて、ガロア体をwebで調べると、
みたいな式が見つかりました。なんだか、学がないのでわかりませんねぇ。しかたなく、上記見ながら、桁数に注目して、何気ない気分で、ローテーションとexorの適当な組み合わせで次のような掛け算を定義してみます。教科書みるとビットストリームでの解説なのでそれを思い出しながらなんとなくでっち上げます.. CD-ROMの場合、本来は連続ビットストリームデータでなく、飛び飛びに分散したデータ対により訂正グループ作るので、ビットストリーム定義はピンと来にくい。 まあ、適当に試行錯誤してみましょうか。
B(7-0) = α*A(7-0)
= A6*2^7 +A5*2^6 +A4*2^5 +(A3 (+) A7)*2^4
+(A2 (+) A7)*2^3 +(A1 (+) A7)*2^2 +A0*2^1 +A7*2^0
excelでB1セルに対する上記の計算の定義は(長すぎるので一部エディットしたけどたぶんミスなし)
=MOD(INT(B1/64),2)*128
+MOD(INT(B1/32),2)*64
+MOD(INT(B1/16),2)*32
+MOD( INT(B1/8)+INT(B1/128), 2)*16
+MOD( INT(B1/4)+INT(B1/128), 2)*8
+MOD( INT(B1/2)+INT(B1/128), 2)*4
+MOD(B1,2)*2
+INT(B1/128)
エクセルで何気に上の式調べると、α^1 ~ α^254まで一意に定まり、1~255に対して、α^1~α^254が、それぞれ一意に決まるようです。0に対して、α^nはすべて0になります。0以外の各数字に対して、1~255までの数字が、α^nのどれかにで現れます(数か所抜き出してソートし確認と、後は、255個データの集計が縦横すべて同じになるので、たぶんあってると思います。
まとめると、8bit:256個の要素が、{ 0, α^0, α^1, α^2, ........, α^253, α^254}になっていると推定されます。
例えば、ちょっとずらして、x^8+x^5+x^4+x^3+1とすると、まるでダメなので、生成多項式名乗るだけの価値はあるみたいです。。
このようなα倍回路で、加算はEXORだと仮定すると、シンドローム演算回路例は下記になる。別ページで紹介した一般汎用乗算機とくらべてください。(掛け算単体ではなく)積和:S1=Σ{α*d(n)+d(n-1)}と、和:S0=Σd(n)を併記しても、下記のような単純な回路になる(厳密にいうと、命令から、初期化(リセット)と、必要回数のd(n)の供給と、必要な回数のクロックの繰り返し発生および最終結果保持のためのタイミング回路が必要です。 思い付で作った仮想の演算であるが、案外雰囲気でてると思います。適当に決めた掛け算による仮想体系なので、そのまま運用するのはどうかと思いますが、エラー訂正とはどんなことしているのか?という入門資料として、見てもらえばよいと思います。
ちなみに、この加算アルゴリズムEXORは、引き算と同じ動作になる。与えられたS0と、計算したS0をΣS0計算機にそのまま加えると、同じ(誤差がない)なら、Σ=0、エラーがあれば、Σ計算結果(mにエラーがある場合)=誤差Δdmそのもの。
さて、Δm*α^mから、mの求め方ですが、実数世界では、log演算むずかしいから、回帰的に、Δmにαを順次かけて、Δm*α^mになる回数から、mを求めるという話をしました。それは、Δmα^mを、αで割るという演算が、割り算がそもそも面倒であるし、割り切れる保証がなくその判断もややこしいからです。 しかし、ガロア体の割り算は、一意にきまりますから、どっちでもいい気がします。α^(-1)は
B(7-0)=A(7-0)/α= A0*2^7
+A7*2^6
+A6*2^5
+A5*2^4
+(A4(+)A0)*2^3
+(A3(+)A0)*2^2
+(A2(+)A0)*2^1
+A1*2^0
excel風にいうと、b1セルの値に対する1/α演算定義
=MOD(b1,2)*128
+INT(b1/128)*64
+MOD(INT(b1/64),2)*32
+MOD(INT(b1/32),2)*16
+MOD( INT(b1/16)+MOD(b1,2), 2)*8
+MOD( INT(b1/8)+MOD(b1,2), 2)*4
+MOD( INT(b1/4)+MOD(b1,2), 2)*2
+MOD(INT(b1/2),2)
Δmにα繰り返しかけるのと、Δmα^mを、αで割る事の功罪わかりません。趣味の問題かな?まあ、速度を必要としないなら、シンドローム演算のα倍器を、訂正ロケーション演算に流用すれば、ICの出荷検査も少し楽になるから、うれしいかな?(並行動作できないのが、欠点なので、同じ回路を用途別2組用意するというのも手かもしれない。
この演算で、シンドロームを計算し、データ壊した場合のシンドロームから誤差、ロケーション求めて、訂正する動作を、エクセルで実現してみました。あくまで、exorの加算と、上述のよくわからん式から適当に作った掛け算を使った積和によるものです。実用化されたものと比べ、どの程度の能力あるのか、素人なので、よくわかりません。
エクセル上、場所固定して2ケエラーを乱数発生すると、10数回程度で、誤訂正を発生するので、まあ、実力その程度の訂正アルゴリズム見たいです。(誤訂正:2個エラーなのに、1個エラーだと誤判断して間違いデータ2けそのままで、正常データを壊して3個エラーを見逃す例が10数回程度で発生する。発生した例を、下記エクセルシートに記録として残しています)。 まあだから誤訂正して終わらないように、クロスインタリーブして、複数回確認する手段をとっているんでしょう。いやそもそもそんな大量エラーが発生する環境を想定して、1ケエラー訂正回路を使うのは間違いだという話なんでしょう。 ちなみに、一般にエラー訂正とエラー検出コードが併用されていることがあるのは、誤訂正を検証する意味もあるんでしょう。
エラー検出訂正実施例(エクセルシート) ↓シートの使い方は下記を拡大してちょうだい。
イエローブック見つけられないので、WEB上で見つけた適当な論理を安易に解釈した例を作って、エラー訂正解説しましたが、、オーム社のCD-ROM読本の中に書いてあったかもしれない。でも手持ちが見つからない。近所の大きな本屋にも置いてないし。探して公開情報見つけたら、内容改定も考えます。
しかし、2ケ訂正の場合、どうやって解くんだろう???よう解らん。繰り替えでは遅すぎるからROMテーブルでも使うのが必須?
遠い昔の噂では、2重訂正の片側で、エラー位置を予測するとかいう噂を聞いたかもしれません。
さらに余談ながら、
と、1ビット定義(赤字)の違う式がwebであさると出てきます。 なんかの方式論理では利用するとかなんとか主張されていますが、web上の反論どおり、ガロア体では無いようです( α^50あたりから、1:1の対応崩れます)。 α^nだけだったら、50個以下のグループで使えるという話なのかもしれんが、積和演算する段階で、解を求めるのは不可能だという気がします。 あえてこれを使うというんだとしたら、何なんでしょうね?素人はこの論議見なかったことにするのが、正解かな?
3-4)その他のエラー訂正関連技術紹介
2重リードソロモン・クロスインタリーブ
実は、リアルタイムシンドローム演算ができる(逆ポーランド法でふれた)というのは、大きなごまかしがあります。 例えば、2048バイトに対して、1つのパリティをつけるわけではありません(ここまでの論議は、GF(2^8)の話なので、8ビットの表記255個以上取扱いできませんし(α^254までしか定義できないので、254ケしか一括処理できない)。もちろんGF(2^12)の生成多項式もってくれば、全数一括取扱い可能でしょうが、8ビットデータ扱いなのに、高次の演算回路でビット数増やすの嫌だし、エラー1ケしか対応不能というのは、せっかく回路内蔵するのに、不満です。それより、データをとびとびに間引いて複数のECCグループを作り。いつくかのECCグループごとのパリティ付加を行うほうが、賢い。 これによって、集中するエラーを、異なるECCグループに分配して、各グループ単位で見れば少量エラーとして、訂正できる可能性をあげるという工夫が賢い。 だから、リアルタイム処理するには、単純に言えば、その分割ブロックの数だけ並行した回路必要だし、それぞれの回路を選択的に動かすタイミング回路が別途必要になります。 でもいろんな工夫ができるんだなぁ、これが。 数学は楽しい。 間違ったパリティをつけているとしか思えないディスク作られてがこれを訂正しないのがおかしいという主張があって気分が悪かったのですが、リアルタイム系シンドローム回路による正攻法で対処できたりしました。悪だくみメーカざまみろという反面、別の書き込み機のバグでパリティつけ間違うまれな例が、、シンドローム演算回路が常時働くと、データ正常(パリティ間違い)というデータ群を、エラーアリと判断して、訂正実行してしまい、誤ったパリティがデータの破壊訂正くりかえすので、ドライブとして正しいデータ出せなくなったとか、まあ、どろどろとした話もあったりしました(PQ片側okなら終了というシステムなら救済できたんだけど、このディスクのためだけのために修正するわけにはいかず)。
スクランブル
この辺も引用してより資料が見つかったら、解説するかも。CD-ROMで、アドレスサーチがサブコードQの方が手軽だという理由の一つが、こいつのせいだという話もあります。セクタ・フレームの先頭データを見つけられるように、目印となるあ同期コードがあるのですが、データ中にこのパターンが並びにくいように、同期コードの後ろからある規則にのっとってビット反転させて同期データが見つけやすくする工夫です(逆にいうと、同期コードが確定するまで、データの意味が解らないのでアドレスを読めるようになるのが遅くなります:パターンがあるかないかだけではなく、決まった周期で並んでいるという判断をいれると、見つけるシーケンスは長くなりそうでしょう?)。