しばらくぶりの記事作成になります。自分でも勉強しながらの書き込みなので結構エネルギーを必要としていて、体がそれを支えきれないようです。
ということでちょっと頑張ってみました。
今までの解説の中で色々な計算が出てきました。今はデジタル回路も記述でハード設計できてしまう時代なので、論理の流れさえ理解できてしまえば後は式を書くだけ、ということでしょう。それでも実際に個別にハードを組んでみようかとか、式で書くとこうだけど回路はこんな感じなんだろうな～、などとイメージをしておくのもより効率的な設計が出来る一助になるかも知れませんので、実際のハードの一例を示してみようと思います。
さてなんといっても計算の主役は XOR です。これは XOR(A,B) = AB' + A'B （ここでは A' は A の反転とします）という論理式で真理値表は以前にも示しましたが以下の通りです。
これをハードウェアで書くとこうなります。
論理式をさらに分解してハードウェアで書くとこうなります。
実は昔はここに一つ落とし穴がありました。
分解された回路をよく見て下さい。
たとえば入力 A を固定して置いて、B を変化させたとします。
その結果はインバータ（反転回路）を通って上側の AND 回路に入り、あるいはそのまま下側の AND 回路に入って、右端の OR 回路に入ります。で、一見問題なさそうなのですが、B の変化の結果が出力に反映される際にインバータの遅れ時間分不確定な状態が発生します。まあ普通に使う分には問題ないと思いますが、うっかり次の回路がその不確定部分を拾って何かの処理を行ってしまうと予期せぬことが置きます。こういう問題を知ったときはまだ TTL の時代で TI なども何か工夫していたようです。AND や OR、NAND ゲート、単体フリップフロップが通常の IC（SSI = Small Size IC）扱いだったのに対して、XOR ゲートは MSI = Middle Size IC 扱いだったと思います。結構遅延時間もありました。その代わり前述のような不確定状態はなくしてあったのだと思います。
今はどうなっているのか知りません。CMOS でも論理だけなら同じ状況でしょうが、スイッチ動作なども入れることが出来るので何か工夫が出来るのかも知れません。
もう一つの重要な回路はシフトレジスタです。これはデータをクロックタイミング毎に遅らせて蓄えるもので一種のメモリです。
シンプルにつなぎ合わせたものがこんな感じです。8 ビットをひとかたまりとして、1 クロック入ると次のレジスタに伝えるというものです。中身は D フリップフロップが並んでいるだけです。
ただ遅らせるだけでは役に立ちませんので、この図で云うとたとえば Data10 ～ Data17 と書いてあるところの間に、XOR の出力が 8 個並んでいて、別のところから 8 ビットのデータが与えられて、Data00 ～ Data07 を 1 クロック入ったらその出力と別のところからきた 8 ビットのデータとの XOR 演算して次のレジスタの入力とする、といった案配です。
今別のところから 8 ビットのデータが来る、と書きましたがそれは今までの記事の説明にあったように、ガロア体の中で計算されたもの、つまり α^（**) とα＾(##) の掛け算だったり、割り算だったりします。足し算は XOR で各ビット毎に行えば良いのは説明したとおりなので、掛け算と割り算のハードウェアも考えておかなくてはいけません。
まあ、これは
αを使った計算の実際＞誤り訂正技術
http://blogs.yahoo.co.jp/susanoo2001_hero/11175428.html
で紹介したマトリックスを使ってソフトウェアで参照しながらやっても良いとは思いますが、8 ビット x 2 のアドレス指定が出来るメモリマップを作って、8 ビットの出力を得るという方法でもいいと思います。時間を気にしなければ原始元αを計算する式を使って何回も回していけば答えが出ます。
ちなみにメモリマップと書きましたが、ゲートで構成してもそんなに大きくはなりません。結構簡単化が出来るようです。
ちょっとだけ自慢話
ロジックだって少しは出来た．．．
http://blogs.yahoo.co.jp/susanoo2001_hero/6812303.html
で、大ざっぱにこんな構成になるわけです。
訂正コード付加する場合は、
誤り訂正符号の付け方の実際（リードソロモン符号）
http://blogs.yahoo.co.jp/susanoo2001_hero/11193398.html
ということになってしまうのですが、すでに割り算の分母は固定化されていますので（G(X) 生成多項式）、より簡単な方法でできます。それが次の図です。
四角 T(0), T(1), T(2), T(3) はシフトレジスタです。最初は全部ゼロを入れておきます。
左側から送りたいデータ列（この場合は 6 バイト）を入れていきます。
4 クロック送ったところで、右側に最初の入力データが現れます。これが楕円の掛け算器を通して丸の XOR に与えられて、次のクロックでそれぞれの T の内容が適当に計算されて次から次へと右に送られていきます。6 バイト分送りつきると T(0), T(1), T(2), T(3) に何かのデータが残っています。これが今回の 4 バイトの訂正コードということになります。
これを元の 6 バイトに付加して計 10 バイトのデータを送信データとするわけです。
ここでちょっと悩ましいのが、掛け算器をどう使うかです。メモリマップを使うと結構はゲートサイズになるので時分割で使うことも考えなくてはいけませんが、それだと速度は遅くなります。今回の例の規模だとどっちを使ってもあまり悩ましい問題にならないかも知れませんが、DVD フォーマットのようなケースでは悩みそうです。ただ係数は決まっているのでゲート構成でたくさん並べるのが一番早いかも知れません。
今度は受信側です。とにかくにもエラーがあるかどうかをチェックするためにシンドローム計算をしなくてはいけません。これは受信データが生成多項式 G(X) の各要素で割ることで得られますので、ハードウェアならこういう構成になります。
左から受信データを 4 つの回路に同時に送りつけ、終わったところで D に残っているものが S0, S1, S2, S3 になります。
こちらも掛け算をどうするかが問題になりますが、係数が決まっているのでゲート構成で並べておくのが早そうです。
ちょっと駆け足になってしまいましたが、雰囲気は分かってもらえたでしょうか。
ということでちょっと頑張ってみました。
今までの解説の中で色々な計算が出てきました。今はデジタル回路も記述でハード設計できてしまう時代なので、論理の流れさえ理解できてしまえば後は式を書くだけ、ということでしょう。それでも実際に個別にハードを組んでみようかとか、式で書くとこうだけど回路はこんな感じなんだろうな～、などとイメージをしておくのもより効率的な設計が出来る一助になるかも知れませんので、実際のハードの一例を示してみようと思います。
さてなんといっても計算の主役は XOR です。これは XOR(A,B) = AB' + A'B （ここでは A' は A の反転とします）という論理式で真理値表は以前にも示しましたが以下の通りです。
これをハードウェアで書くとこうなります。
論理式をさらに分解してハードウェアで書くとこうなります。
実は昔はここに一つ落とし穴がありました。
分解された回路をよく見て下さい。
たとえば入力 A を固定して置いて、B を変化させたとします。
その結果はインバータ（反転回路）を通って上側の AND 回路に入り、あるいはそのまま下側の AND 回路に入って、右端の OR 回路に入ります。で、一見問題なさそうなのですが、B の変化の結果が出力に反映される際にインバータの遅れ時間分不確定な状態が発生します。まあ普通に使う分には問題ないと思いますが、うっかり次の回路がその不確定部分を拾って何かの処理を行ってしまうと予期せぬことが置きます。こういう問題を知ったときはまだ TTL の時代で TI なども何か工夫していたようです。AND や OR、NAND ゲート、単体フリップフロップが通常の IC（SSI = Small Size IC）扱いだったのに対して、XOR ゲートは MSI = Middle Size IC 扱いだったと思います。結構遅延時間もありました。その代わり前述のような不確定状態はなくしてあったのだと思います。
今はどうなっているのか知りません。CMOS でも論理だけなら同じ状況でしょうが、スイッチ動作なども入れることが出来るので何か工夫が出来るのかも知れません。
もう一つの重要な回路はシフトレジスタです。これはデータをクロックタイミング毎に遅らせて蓄えるもので一種のメモリです。
シンプルにつなぎ合わせたものがこんな感じです。8 ビットをひとかたまりとして、1 クロック入ると次のレジスタに伝えるというものです。中身は D フリップフロップが並んでいるだけです。
ただ遅らせるだけでは役に立ちませんので、この図で云うとたとえば Data10 ～ Data17 と書いてあるところの間に、XOR の出力が 8 個並んでいて、別のところから 8 ビットのデータが与えられて、Data00 ～ Data07 を 1 クロック入ったらその出力と別のところからきた 8 ビットのデータとの XOR 演算して次のレジスタの入力とする、といった案配です。
今別のところから 8 ビットのデータが来る、と書きましたがそれは今までの記事の説明にあったように、ガロア体の中で計算されたもの、つまり α^（**) とα＾(##) の掛け算だったり、割り算だったりします。足し算は XOR で各ビット毎に行えば良いのは説明したとおりなので、掛け算と割り算のハードウェアも考えておかなくてはいけません。
まあ、これは
αを使った計算の実際＞誤り訂正技術
http://blogs.yahoo.co.jp/susanoo2001_hero/11175428.html
で紹介したマトリックスを使ってソフトウェアで参照しながらやっても良いとは思いますが、8 ビット x 2 のアドレス指定が出来るメモリマップを作って、8 ビットの出力を得るという方法でもいいと思います。時間を気にしなければ原始元αを計算する式を使って何回も回していけば答えが出ます。
ちなみにメモリマップと書きましたが、ゲートで構成してもそんなに大きくはなりません。結構簡単化が出来るようです。
ちょっとだけ自慢話
ロジックだって少しは出来た．．．
http://blogs.yahoo.co.jp/susanoo2001_hero/6812303.html
で、大ざっぱにこんな構成になるわけです。
訂正コード付加する場合は、
誤り訂正符号の付け方の実際（リードソロモン符号）
http://blogs.yahoo.co.jp/susanoo2001_hero/11193398.html
ということになってしまうのですが、すでに割り算の分母は固定化されていますので（G(X) 生成多項式）、より簡単な方法でできます。それが次の図です。
四角 T(0), T(1), T(2), T(3) はシフトレジスタです。最初は全部ゼロを入れておきます。
左側から送りたいデータ列（この場合は 6 バイト）を入れていきます。
4 クロック送ったところで、右側に最初の入力データが現れます。これが楕円の掛け算器を通して丸の XOR に与えられて、次のクロックでそれぞれの T の内容が適当に計算されて次から次へと右に送られていきます。6 バイト分送りつきると T(0), T(1), T(2), T(3) に何かのデータが残っています。これが今回の 4 バイトの訂正コードということになります。
これを元の 6 バイトに付加して計 10 バイトのデータを送信データとするわけです。
ここでちょっと悩ましいのが、掛け算器をどう使うかです。メモリマップを使うと結構はゲートサイズになるので時分割で使うことも考えなくてはいけませんが、それだと速度は遅くなります。今回の例の規模だとどっちを使ってもあまり悩ましい問題にならないかも知れませんが、DVD フォーマットのようなケースでは悩みそうです。ただ係数は決まっているのでゲート構成でたくさん並べるのが一番早いかも知れません。
今度は受信側です。とにかくにもエラーがあるかどうかをチェックするためにシンドローム計算をしなくてはいけません。これは受信データが生成多項式 G(X) の各要素で割ることで得られますので、ハードウェアならこういう構成になります。
左から受信データを 4 つの回路に同時に送りつけ、終わったところで D に残っているものが S0, S1, S2, S3 になります。
こちらも掛け算をどうするかが問題になりますが、係数が決まっているのでゲート構成で並べておくのが早そうです。
ちょっと駆け足になってしまいましたが、雰囲気は分かってもらえたでしょうか。