ガロア体

（2021.04.16)　高速通信システムを手がける人から、ちょっと役に立つかもというメールもらった。　役に立ったと連絡くれた未知の人は初めてかも。なにかお役に立つのならと申し出たけれど、やりたいことがちんぷんかんぷんで断念。

そういえば、プリンタ型番書き間違えていて、旧モデルでも使えるという誤情報を書いていて、失望させてしまった恥ずかしい過去がありましたけど。

以下ガロア体理論をまじめに学んだことない者のたわごとです。勝手な思い込みにもどづく解説なので、内容に責任とれません（パテントなどの権利も不明です）。

訂正に使う演算として、掛け算を考えてみましょう。　例えば、８ビットデータに８を掛けることを考えてみます。定義域は0-255の８ビット幅で、値域は、0-2040と、11bitデータ幅になります。16倍すると最大4080と12ビットデータとなります。ビット長が大きくなることのデメリットは前に述べた通りです。
でも、使う数字の個数は？４を掛けると、0,4,8,12,16..と４つおき256種類になりますね？８倍するなら0,8,16,...の８つおき256種類。つまり、何を掛けるとしても、定義域（掛けられる数8bit）=256個なら、１：１演算結果は、値域の使用個数は、256個だけです。　値域：数値範囲としては、掛ける数によって、もちろん幅は広がります。　重要なのは、その演算が１対１で、逆算ができるということだけです。
１：１の関係がたもてるなら、8bitへの掛け算は、結果も256個（8ビット表現）で表現十分ですよね。剰余系というのがここで注目できます。　　逆算が一意に定まる事だけが重要で、計算結果の（数値としてみた）大小関係が、例えば、α＾2＞α^3であっても、α＋２＞α＋３であっても、あるいは、m*α^k > (m+n)*α^k　等と、普通の数学（実数世界）の大小関係と異なっても、（もちろん大小関係が一般的に普通な場合があっても、）何ら問題ありません。一対一の一致だけ（等しい事が検出できる事）が重要で数値の大小に意味はありません。

また、数字バラエティ（ようは使う数字の個数）すくないので、m*α^n = j*α^k と重なってしまうものがでるはずです。　でも、問題にはなりませんよ、例えば１０進の１２という数字を考えてみましょう。　２ｘ６＝１２ですが、４ｘ３＝１２で異なる演算結果が値域で偶然一致します。しかし、値域で値が重なっても、６をかけて１２になるのは２だけ、４を掛けて１２になるのは３だけと、それぞれ、１：１が破たんしないことだけで、十分なのです。

足し算も8bit同士の最大となる加算は255＋255＝510（9bit)ですが、これも同様に、定義域の数に対して値域の数が１：１ということだけが重要です。これも8bit値域に反映するシステムで十分ですね。まさに剰余系で十分優秀です。

掛け算α倍という演算が、８ビット定義域に対して、８ビット値域に１対１逆算可能な定義ができて、さらに、α倍、α^2倍、α^3倍...が、それぞれ別の値になって、言い換えると{α＾n}の集合体として、８ビット値域に収まるという計算体系が定義できるというのが素人考えで８ビットのガロア体という意味なんだろうと勝手に予測してみます。知らんけど（ここ関西弁ののりです）。

（ガロア体は難しそうなので）剰余系として演算どのような定義をすればよいか、考えてみましょうか？
加算は、入力AとBの間の２項の演算です。ビット毎に考えることにすると、論理演算として教科書に出てきやすいのは、AND,OR,EXORの３演算（NAND,NOR,EXNORはこれの論理反転出力なので原理は同じ）。

ANDやORの論理は、ある出力に対して入力Aが判っているときBが判断できるか？という逆演算に、不定（入力１つと、出力がきまっても、もう一方の入力が、０か１か判断できない場合がある）が生じます。したがって、逆算が必要な、今論議している演算方法としては、不向きです。EXORとかEXNORが、有力候補となります。

では×αは？　これはここまで、一見αという数字と、入力データとの、２項演算(乗算）のように記述していますが、実は、入力に、α掛けたという出力を求めるという、単項演算です（本当の掛け算ではなく、単なる関数）。
例えば、ビットローテーションはどうでしょうか？８ビットデータの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の逆算可能な演算で、ビット長が増えないに見えます。しかし、この定義で、α^8=α^0　となってしまって、これ以上高次は、逆算が一意に決まりません（だからこの演算定義はガロア体とは言えない）。けれども、例に挙げていた金貨、銀貨、銅貨、鉄貨の４項しかないなら、使用するα^4,α^3,α^2,αの演算で１対１が確保できればよいので、掛け算αの定義は、これで、十分だと思いませんか？　残念甘い！

入力	*α^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の時も、もう判断不能です。エラー訂正に使えそうもありません。

剰余系で、エラー訂正に使えるαの定義（ガロア体多項式の解の定義）は、思い付で適当に試しても、簡単にうまくいかないようです。　１０進実数演算の前述の方法でαは、２倍でも、３倍でも定義し、エラー訂正可能ですのにね（訂正能力：誤訂正抑止能力が高いかどうかは数学屋さんにおまかせします。データの距離のような説明があるんだけど、ちとむずかしい）。
だからこそ特定の”α”を法とする剰余系ガロア体を定義できた数学屋さんえらい。
試しに、この前に、ｅｘｏｒ１ケのローテーション系回路作ったら、そのどのビットペアで演算するかによって、α^14でもとに戻ったり、α^31でもとに戻ったり。で、使えない（後で調べたら後者は偶然GF(2^5)の生成多項式α＾２+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

ｅｘｃｅｌで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)

エクセルで何気に上の式調べると、α＾１　～　α^254まで一意に定まり、１～255に対して、α^1～α^254が、それぞれ一意に決まるようです。０に対して、α＾ｎはすべて０になります。０以外の各数字に対して、１～２５５までの数字が、α＾ｎのどれかにで現れます（数か所抜き出してソートし確認と、後は、２５５個データの集計が縦横すべて同じになるので、たぶんあってると思います。
まとめると、８ｂｉｔ：256個の要素が、｛ 0, α^0, α^1, α^2, ........, α^253, α^254}になっていると推定されます。

例えば、ちょっとずらして、x^8+x^5+x^4+x^3+1とすると、まるでダメなので、生成多項式名乗るだけの価値はあるみたいです。。

このようなα倍回路で、加算はEXORだと仮定すると、シンドローム演算回路例は下記になる。別ページで紹介した一般汎用乗算機とくらべてください。（掛け算単体ではなく）積和：S１＝Σ｛α＊ｄ（ｎ）＋d(n-1)｝と、和：S0＝Σｄ（ｎ）を併記しても、下記のような単純な回路になる（厳密にいうと、命令から、初期化（リセット）と、必要回数のd(n)の供給と、必要な回数のクロックの繰り返し発生および最終結果保持のためのタイミング回路が必要です。　思い付で作った仮想の演算であるが、案外雰囲気でてると思います。適当に決めた掛け算による仮想体系なので、そのまま運用するのはどうかと思いますが、エラー訂正とはどんなことしているのか？という入門資料として、見てもらえばよいと思います。

ちなみに、この加算アルゴリズムＥＸＯＲは、引き算と同じ動作になる。与えられたＳ０と、計算したＳ０をΣＳ０計算機にそのまま加えると、同じ（誤差がない）なら、Σ＝０、エラーがあれば、Σ計算結果（ｍにエラーがある場合）＝誤差Δdmそのもの。

さて、Δｍ*α^mから、mの求め方ですが、実数世界では、log演算むずかしいから、回帰的に、Δ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の出荷検査も少し楽になるから、うれしいかな？（並行動作できないのが、欠点なので、同じ回路を用途別２組用意するというのも手かもしれない。

この演算で、シンドロームを計算し、データ壊した場合のシンドロームから誤差、ロケーション求めて、訂正する動作を、エクセルで実現してみました。あくまで、ｅｘｏｒの加算と、上述のよくわからん式から適当に作った掛け算を使った積和によるものです。実用化されたものと比べ、どの程度の能力あるのか、素人なので、よくわかりません。

エクセル上、場所固定して２ケエラーを乱数発生すると、１０数回程度で、誤訂正を発生するので、まあ、実力その程度の訂正アルゴリズム見たいです。（誤訂正：２個エラーなのに、１個エラーだと誤判断して間違いデータ２けそのままで、正常データを壊して３個エラーを見逃す例が１０数回程度で発生する。発生した例を、下記エクセルシートに記録として残しています）。　まあだから誤訂正して終わらないように、クロスインタリーブして、複数回確認する手段をとっているんでしょう。いやそもそもそんな大量エラーが発生する環境を想定して、１ケエラー訂正回路を使うのは間違いだという話なんでしょう。　ちなみに、一般にエラー訂正とエラー検出コードが併用されていることがあるのは、誤訂正を検証する意味もあるんでしょう。

イエローブック見つけられないので、WEB上で見つけた適当な論理を安易に解釈した例を作って、エラー訂正解説しましたが、、オーム社のCD-ROM読本の中に書いてあったかもしれない。でも手持ちが見つからない。近所の大きな本屋にも置いてないし。探して公開情報見つけたら、内容改定も考えます。

しかし、２ケ訂正の場合、どうやって解くんだろう？？？よう解らん。繰り替えでは遅すぎるからROMテーブルでも使うのが必須？
遠い昔の噂では、２重訂正の片側で、エラー位置を予測するとかいう噂を聞いたかもしれません。

と、１ビット定義（赤字）の違う式がwebであさると出てきます。　なんかの方式論理では利用するとかなんとか主張されていますが、web上の反論どおり、ガロア体では無いようです（　α＾５０あたりから、１：１の対応崩れます）。　α^nだけだったら、５０個以下のグループで使えるという話なのかもしれんが、積和演算する段階で、解を求めるのは不可能だという気がします。　あえてこれを使うというんだとしたら、何なんでしょうね？素人はこの論議見なかったことにするのが、正解かな？

２重リードソロモン・クロスインタリーブ
　　　実は、リアルタイムシンドローム演算ができる(逆ポーランド法でふれた)というのは、大きなごまかしがあります。　例えば、2048バイトに対して、１つのパリティをつけるわけではありません(ここまでの論議は、GF(2^8）の話なので、8ビットの表記255個以上取扱いできませんし（α^254までしか定義できないので、254ケしか一括処理できない）。もちろんGF(2^12)の生成多項式もってくれば、全数一括取扱い可能でしょうが、8ビットデータ扱いなのに、高次の演算回路でビット数増やすの嫌だし、エラー１ケしか対応不能というのは、せっかく回路内蔵するのに、不満です。それより、データをとびとびに間引いて複数のECCグループを作り。いつくかのECCグループごとのパリティ付加を行うほうが、賢い。　これによって、集中するエラーを、異なるECCグループに分配して、各グループ単位で見れば少量エラーとして、訂正できる可能性をあげるという工夫が賢い。　だから、リアルタイム処理するには、単純に言えば、その分割ブロックの数だけ並行した回路必要だし、それぞれの回路を選択的に動かすタイミング回路が別途必要になります。　でもいろんな工夫ができるんだなぁ、これが。　数学は楽しい。　間違ったパリティをつけているとしか思えないディスク作られてがこれを訂正しないのがおかしいという主張があって気分が悪かったのですが、リアルタイム系シンドローム回路による正攻法で対処できたりしました。悪だくみメーカざまみろという反面、別の書き込み機のバグでパリティつけ間違うまれな例が、、シンドローム演算回路が常時働くと、データ正常（パリティ間違い）というデータ群を、エラーアリと判断して、訂正実行してしまい、誤ったパリティがデータの破壊訂正くりかえすので、ドライブとして正しいデータ出せなくなったとか、まあ、どろどろとした話もあったりしました（PQ片側okなら終了というシステムなら救済できたんだけど、このディスクのためだけのために修正するわけにはいかず）。

スクランブル
この辺も引用してより資料が見つかったら、解説するかも。CD-ROMで、アドレスサーチがサブコードQの方が手軽だという理由の一つが、こいつのせいだという話もあります。セクタ・フレームの先頭データを見つけられるように、目印となるあ同期コードがあるのですが、データ中にこのパターンが並びにくいように、同期コードの後ろからある規則にのっとってビット反転させて同期データが見つけやすくする工夫です（逆にいうと、同期コードが確定するまで、データの意味が解らないのでアドレスを読めるようになるのが遅くなります：パターンがあるかないかだけではなく、決まった周期で並んでいるという判断をいれると、見つけるシーケンスは長くなりそうでしょう？）。