訂正の効率の問題

効率を論議するのに、まず問題点（コスト）を考えます（余裕があるなら前節のような単純積和で十分だと思います）。（2018.08.19）とはいえちょっとページ末で雑談追記）
問題点を（適当なコストパフェ―マンスで）合理的に克服しているのが、次の節で触れるガロア体と呼ばれる剰余系の演算体系になります。まず問題になる事の解説から。

日本では小学校で九九を暗記しますから１桁どうしの掛け算なら条件反射でわかりますが、２桁の掛け算は普通の人が電卓等が使えないなら（暗記しているという噂のインドの人やそろばんの達人ならともかく）、筆算するのが普通だと思います。　これから、ディジタル処理を念頭において考えるので、同様に２進数でのひっ算も表記します。

と、32ビット乗算が、１命令（実行も１ｃｋ）で実現できます。つまり一括演算の巨大高速掛け算機を持っているということです。同様に、産業界で重用されるるH8プロセッサでも

と、１命令で実行できます（とはいえ、実行に20クロック必要だったり、そもそも動作可能クロック周波数も違うので、ARMと比べればかなり遅い。物量主義でなく繰り返し加算で結果を出すタイプなんでしょう（ひっ算している感覚だと思っていいでしょう）。

一方、Z80などの古い世代のCPUは、乗算命令が存在しません。したがって、プログラムで乗算を実行します。

具体的に、Z80のソフト例や、それイメージしたハードウエア（ゲートレベル）イメージを別ページで、解説します。

任意の数字ｘ任意の数字の回路やソフトの実現が大変だというイメージは乗算１を読んで理解していただけたでしょうか？
でも、一方、固定値の掛け算であれば、引き算とか混ぜて、かなり楽に作れるのも、理解していただけたと思います。
では、これらを総合的に考えて、複雑な掛け算機・掛け算ソフトを用いないで、エラー訂正を行うのはどうすればいいでしょうか？

それには、汎用ではなく、（簡単につくれる）固定値の掛け算機αを用意することです。すると、（α＝単位元”１”でない限り）　α、α^2、α^3．．．は、異なる数字になります。ｎ項目は前例で、ｎ倍する（ｎを乗じて）していましたが、代わりにα＾ｎを乗じることで、方程式を解けば、エラーの場所とエラー量が求められるわけです。汎用の複雑な回路ではなく、固定値の掛け算でコスト削減という作戦です。

ここで、例えばα^4は、同じ掛け算機を４回もつかって、汎用掛け算という負担を繰り返しの時間（回数）に振り替えただけで、本質的に大変なのは変わらないと、考えたあなたへ。　いい考えです、でも、もうひと押し考えましょう。

この式の素敵な意味が解りますか？（ちょっと雑談逆ポーランド法）

もとの、Σn*d[n]の計算量は、2n-2回　、Σd[n]の計算量は、n-1回

αを使うとき、すなおに、Σを展開して各項に指数違いのαをかけると、データごとに、掛ける回数が変わり、結局大変で　計算量は　Σ(n+1)-3　回

でも、上記αで括った式の意味は、最初のデータｄ［ｎ］にα倍し、次のデータd[n-1]を加える。この和をα倍して次のデータd[n-2]を加える。　これ以降同様に、またαをかけて、次のデータを加える。つまり、積和の繰り返しで、合計2n-2の計算回数で実現できます。乗算と加算を同じ演算回数カウント正しいか？と疑問のあなたへ。掛け算回数だけ考えても、同じでしょ？

ここで重要なのは、何回目の繰り返しという条件が入るわけでなく、ただ同じ数をかけて、入ってきたデータを順に加算するという単純繰り返しだけでいいというのがポイントです。（有効桁数は、事前に検討して確保しておけば、オーバフローの判定する必要ありません）。

いいかえると、式の変形、計算順番さえ工夫すれば、汎用積算機で、Σn*dnを求めるのと、Σα^n*dnが、ほぼ
同じ計算回数で実現できるのが分かります。　汎用積算機ではなく、比較的簡単につくれる固定積算機の運用で、また、何データ目という判断処理することなく、エラー訂正（パリティ：シンドローム演算）が、時間負担増加すること無くできるわけです。

厳密にいうと、Δmと、Δdm*α^m　から、mというロケーション場所を、一発回答はちょっと難しいという問題はあります。　電卓・算数なら、対数つかって算数的に計算できますが、そんな回路・演算ソフトはもっと大変です（さらに正確さを求める訂正に、途中で少数が発生する対数というのもありえません）。

割り算回路を、ちょっと考えてみます。確かに、1/2とか、1/4とか２のべき乗なら、ビットシフトだけで実現できますが、汎用の割り算ねぇ..思いつくのは、引き算を繰り返して、０になる回数（割り切れない場合は、負にならない直前の回数）を、数えるくらいかな（さすがに安直すぎる）...ひっさんのように、最大値になるようビットシフトしてから、挽るか引けないか（マイナスになる）を、いちいち引いてみながら（確認しながら）、引く数をシフトダウンしながら行く方法しかないですね。

掛け算は、まだ分割加算で最終ビット長さ確保しておけば何とかなるけど、割り算は割り切れるかどうかの判断がはいるので面倒ですね。（単純引き算ではなく、ビットシフトしながら大きな数から順番に引き算して、引けるもと引けないもので割り全結果を求めるのがROMテーブル使わないなら最適解でしょう）。
すると、シンドローム演算にも使うα倍掛け算を兼用し、Δｍに繰り返しかけ続けて、Δm*α^mになる回数を数えて、ｍを求めるのがとりあえず簡単です。

これは、α＾ｍだから難しいという話では無く、ΔｍとΔｍ＊ｎから、割り算して、ｎを求めるのも回路として難しいという意味です。こっちもやれといわれると、ひっ算風にビットシフトしながらこのシフトデータで引けるか引けないか判断して、１ビットづつ商を積むのが正解でしょうけど。　Δｍに値を順に変えながら掛け算実施して、Δｍ＊ｍとなるｍを求めるというのも、スマートではないですね（要するにｎを掛けても、α^nを掛けても、割り算でｎを求めるのは難しいという意味です。

データ８ビットを想定します。掛け算８ビットを実行すると１６ビットデータとなりますね？さらに、前述のS1＝Σn*Dnを考えるのに、１６ｂｉｔデータ１６個の加算と考えると16+4=20bit最大になるのがわかりますね？　さらにS0=ΣDnも、上記で12ビットになります。
合計32ビット＝４バイト分（データ処理方法を考えると３バイト＋２バイトの５バイトが本筋）。　たかだか１６バイトデータに訂正用データ＝パリティを５バイトつけるというのは、もったいないですね？約24%が本来必要でないデータなんです。

データとその検査という寄り道雑談。
8ビットパソコン（当時マイコンという）の時代には、雑誌にBASIC言語のリスト以外に、機械語ダンプリストが頻繁に載っていて、（普通の人に意味不明の）１６進データをひたすらPCに入力すると、間違いなければ、ソフト（ゲームとか）が動いたりしていましたが、機械語は、１ビット違うと、暴走することもありますから、入力間違いを検出するために、データと一緒にチェックサムというエラー検出情報（あくまで検出で訂正ではない）を印刷してました。
チェックサム計算ソフトで自分の入力したデータの計算したチェックサムと、と印刷物の目視比較での間違いを見つけました。この１行（１列）に間違いがあるとわかれば、にじんで見にくいTV画面上の文字をその行列一生懸命見たものです。　（内蔵BASICインタプリタのバグで時々入力が化ける可能性もある）横４０文字の見やすいきれいな表示を使うか、大量に見えるがボケた横８０モードを使うか、専用モニタ買えない貧乏学生の悩みはつきない。　
余談ついでに。TV画面のぼけた文字見るのが大変なので、第二精工舎の安いドットマトリクスプリンタに飛びついた思い出あります（NECやエプソンの定番機15万円くらいに対して半値以下７万円くらいのモノハンマーという廉価版プリンタでうるさく遅かった：漢字ROMなど当然ない英数字ベース。　トラクターフィードという、紙の両端に定間隔で穴が開いていて、それを、ひっかけて紙送りするシステムです。そのプリンタの他の用途として、演習問題で方位ごとに計算して指向性パターンを書けという宿題がでたとき、繰り返し演算面倒だったので、プログラムで計算してついでに、グラフィック印刷して提出した時や、別の授業で興味を持ち予め作っていた最小二乗法の計算ソフトで宿題解いて報告したら、当時まだパソコン（マイコン）使う人少なかったので、講義の担当教授が、研究室配属時ぜひおいでという、お愛想をいただいたことがありました。その研究室に行った人に聞くと、当時使っていた古い計算機上のテープベースの古い専用ソフトをBASIC言語で使いやすいものにしたかったらしい。（配属先抽選大会で、クラス最後から５番目の選択権という）くじ運悪い自分は、選択の余地の無い配属にきまりました。　ただその先生のところへ行きたいか？というと、怖いイメージの先生なので行かなかったかな。　

さて本題にもどる。１６バイトに１バイトの雑誌市場で受け入れられたチェックサムに対して、訂正場所探して、値まで自動訂正できるとはいえ、めったに誤りがないとすると、５バイトは追加データ量が大きすぎると思いませんか？（機能させるには、これもデータとして、PCに入力しないと、頭の中で暗算でエラー検出・訂正無理です）。

3-1)で示した掛け算がハードでもソフトでも実は大変だという話と、このビット長が多くなりすぎるという問題を、数学的に解決できるのがアイデアが、次節で紹介するガロア体と呼ばれる剰余系計算体系の利用という話になります。

余談ながら、α^n係数をかける場合、α＝２の場合でも、２個で2^2→２ビット、１６個なら、15ビット桁数が上がってしまいます。さらに、Σ加算でその数に応じて桁数が増えてしまいます。いやですよね？

例えば、ARM64bitプロセッサで、掛け算を含む演算速度も、パリティのバイト長やデータビット長（一言でいえば空メモリ量）も、ハード上余裕があると豪語するなら、以降読む必要ありません。ここまでの情報で訂正システム利用できます。コストパフォーマンスのシステム判断（コストとパフォーマンスの妥協点をどこに置くかの判断）は重要です。

無線通信システムで、単純パリティでなく、それなりの検出コード（EDCコード)付けているものを見たことあります。これECC（エラー訂正コード）にすれば、やり直し通信しなくて、応答性改善できるのにと思ったものです。まあ、受信側が、ビット化けを許容して、ビットずれを起こさないで、最後まで通信してくれれば、何とかなりますが、受信打ち切られたり、ビットずれしちゃうと訂正無理（訂正許容個数を超えてしまう）から、そこまでやりたくないのかな？　syncコードで同期検波するんだったら、そこまでやるのがいいと思うんだけど、システム設計に口をはさめるんなら文句を言いたかった：はて何のシステムの噂や、ぐちかな？。

まあ、あと、どの程度のデータ訂正能力をつけるか？（エラーが多い場合に間違って正しいデータを壊す確率とか、訂正グループの分散方法とか）というシステム設計上の問題はありますが、素人なのでここでは、扱いません。システム開発に必要な方は数学の専門家とどうぞ。

（2017.08.19）雑談です。確かにアプリケーションレベルでいえば、通常の四則演算によるシンドローム（積和、と和）で十分という話はあります。ところが、デバドラとかハードに直結する場合、必ずしもそうとは限りません。例えば、データ通信の信号が、GNDにショートしてしまった場合を予想してみましょう。データは０と判断するなら、積和も和も０となって、素直にエラー無しでめでたしめでたしとなってしまいます。　ちょっと思い出せないんだけど、何かのシステムでは、パリティ部分を論理反転して転送する決まりになっていたものがありました。この場合なら、データバスが０固定だという異常事態を簡単に検出することができるでしょう？　ハードウエア直結の人の感性では、いろいろ考えるものです（必要かどうかは別として）。　こういうのが、エラー検出能力が優秀ななのかどうなのか数学屋さんの腕の見せ所だったりします。
ところで、GNDをショートして、０になったと仮説していますが、電気的に０という意味では必ずしもありません。通信でもっともPCと親和性があるのは、RS232Cだと思いますがこれは本来±12Vの２値の通信です。初期の8bitや16bitのPCでは価格を抑えるために、０V，５VのRS232Cもどき通信をしていました。パラレルデータとシリアルデータの変換（そこにはパリティの付加・検出もあるし、キャラクタデータ列の先頭示すスタートビットとか、キャラクタ（一般に8ビットですが、7ビットもある）の最後を示すストップビットを付加するとか、そもそも、常時信号ラインを監視して、データを取りこぼさず、CPU：ハードがデータ読み落とさないようにする機能（一言でいうと割り込みを発生させる）のIC（古くは８２５１UART）が、CPUと同じく5V駆動ですから、わざわざ、±12V用意したくないという意思があったりします。これを解決するのが、マキシムというメーカさんのMAX232シリーズIC。５V単一電源から、±12Vの通信ラインを運用できます。　デバイスメーカの開発ツールを、量産ラインに組み込むための設計仕様書つくるために、オシロで波形をみていたら、－１２Vが、Hレベル、＋１２VがLレベルを示していたあれあれこれ普通なんだっけ？メーカ専用アプリの中で、情報漏洩しないように、細工してるんだっけ？と悩んだ思い出があったりします（考えてみると論理レベルのシリアル通信の解説よく見ますが、物理レベルってこの時まで考えたことなかったです）。

7bitと8bit。アスキーコードは大文字小文字数字と、コントロールコードをいれて、７ビットで欧米では十分だったので、通信が７ビットというのもあります。日本ではかなを必要とするので、どうしても8ビットが必要とされました（漢字はあきらめて２バイトに拡張）。+1bitしてASACII文字埋めて、あまるところに、メーカが特殊なキャラクターを定義していて、キャラクタベースのゲームでなんか愛嬌のある顔文字とか出てくる場合もあります（シャープさんが有名だったかな？）。　絵文字とか、顔文字がいま海外でも流行ってきたようですが、80年代そこそこに遊び心のあるメーカがあったということです。もちろん互換性は無い。　今もキャリア毎に携帯の絵文字キャラクタ違うので、キャリをまたいだメールでは文字化けあるでしょ？　はっきり覚えていないけど、メーカ定義のキャラクタを使わないで、ユーザ定義のドット柄を各コードの文字として入れ替え登録するシステムがPC8001用に販売されて、グラフィックベースの遅いものではなく、キャラクタベースで快適に動くんだけど、面白いキャラクタが動き回るゲームが発表されてました（パックマンだか平安京エイリアンだか友達が買って確かの同じゲームでも家のPCメーカ定義キャラでなく、彼のそのゲームに特化したキャラにすることで、いかにも楽しそうに見えるので、ちょっと嫉妬しました（それ買うなら、FDかって、CPMというOSで遊びたかったので私はパス）.