論理回路２
第７章 順序回路の応用（その１）
−modulo2の論理演算回路−
井澤 裕司
一般のコンピュータでは、 2進数による四則演算（加減乗除） が用いられています。
（詳しくは、「論理回路1」第1章、第2章を参照のこと。）
一方、通信や記録の分野では、 伝送時や書き込み・読み出し時に発生する エラーの影響 を取り除く技術として、
誤り訂正 をはじめとする 符号理論 があります。
この符号理論では、通常の2進数とは異なる 「modulo2」 と称する演算が用いられます。
この演算では、2進数の加算における桁上げ操作を 無視 し、 加算と減算 は 同じ結果 になります。
一般的な感覚からすれば 変則的な演算 に思われますが、 その実用的な価値は高く、
1と0のビット列の中から 誤りの有無を検出 したり、 誤りを訂正 する手法に用いられています。
本章では、その基礎となる演算規則と、 それらを論理回路で実現する方法を中心に解説します。
それでは、 modulo2の演算 とはどのようなものか、説明しましょう。
modulo2の加算 は、 排他的論理和 EXOR（丸プラス） を用いて、次のように表されます。
以下、表記の簡略化のため、簡単に プラス（＋） で表すことにします。
3番目までの式は、とくに問題はありませんが、4番目の式では、2進数の加算における 「桁上げ」を無視 しています。
modulo2の加算は、このように 「桁上げ操作」 を行わない2進数の加算に等価です。
次に、減算を定義するため、 (-a) ＋ a = 0 を満たす (-a) 、すなわち [加算の逆元] を求めます。
0 と 1 の場合について、 ［加算の逆元］ は次のように定義されます。
これらの式と上の加算の結果より、
が成立します。
これより、 modulo2の演算 では、 加算（プラス）と減算（マイナス） に違いはなく、 同じ結果 になることがわかります。
一方、 modulo2の乗算 は以下のようになります。
ここで、 （a-1）・a = 1 を満たす ［除算の逆元] （a-1） を求めます。
上の乗算の結果から、 （1-1） = 1 となり、 a = 0 のとき （a-1） は存在しないことがわかります。
modulo2 の変数 x を用いた 多項式 についても、以下のように 加算と減算 を行うことができます。
同様に、 多項式 を用いたmodulo2の 乗算と除算 についても、次の例のように計算することができます。
これらの式は、最初は奇異に思えるかもしれませんが、とにかく慣れるよう努めて下さい。
３ modulo2の演算回路
ここでは、modulo2の加減乗除を実現する 論理演算回路 について解説します。3.1 加算回路
modulo2の 加算 は簡単です。
定義から、 排他的論理和（EXOR） で実現できることは明らかです。
先ほど述べたように、加算と減算の区別はなく、それらの結果も同じ形になります。
なお、 複数ビット に拡張する場合は、 EXOR をビット数分、並列に配置します。
1ビットの 乗算回路 の出力は1ビットであり、定義式から 論理積（AND） で構成されることは明らかです。
ここで、複数ビット数の 乗算 に拡張してみましょう。
通常の2進数の場合、乗算はビットシフトと加算に分解して計算しました。 （「論理回路１」参照）
modulo2の場合も同様で、 ビットシフト と 排他的論理和（EXOR） で実現します。
1 を1ビット目、 x を2ビット目、 x2 を3ビット目とし、それぞれ1という値を持つと考えます。
例えば、 x+1 は2ビットで、 （11） に対応します。
同様に、 x4 +x+1 は5ビットで、 （10011） に対応します。
なお、
x+1 = 1+x
x4+x+1 = 1+x+x4
が成立するのは明らかです。
このmodulo2の乗算を論理回路を用いて表してみましょう。
ビットシフトを実現するのに、 時間的なシフト（すなわちシフトレジスタ）を用いると、論理回路を簡略化することができます。
ビットシフトは、シフトレジスタで構成します。
具体的には、クロック入力のあるフリップフロップ（例えばD-FF）を用います。
このとき、ビットの上位・下位と、時間的なシフトの方向の対応により、2通りの計算方法が存在します。
すなわち、ビットの上位から先に計算する場合と、下位から計算する場合です。
いずれの方法でも、同じ結果が得られることは言うでもありません。
(1) ビットの下位から計算する場合
はじめに、ビットの下位から先に計算する方法を紹介しましょう。[例1] b(x) = x 3+x2+x+1
このとき、上位の桁ほど時間的には遅れることになります。
ここで、1クロックの遅延を x で表します。
例えば、連続する3ビットの時系列信号 [0、1、1] を x 2+x で表すことができます。
この信号 （x2+x） に x を通す（掛ける）と、 全体が1クロック遅延して、 x 3+x2 [0、0、1、1] となります。
また、 x 4+x+1 は5ビットの時系列信号 [1、1、0、0、1] に対応することがわかります。
ビット列 （10011） と、時系列の信号 [1、1、0、0、1] では、上位と下位が 逆転 していることに注意して下さい。
いま、3ビットの数値 a(x) = x 2+x と 4ビットの数値 b(x) = x 3+x2+x+1 の乗算を考えます。
b(x) = x3+x2+x+1 のとき次の式が成立します。
a(x) b(x) = a(x) x3+ a(x) x2+ a(x) x + a(x)
すなわち、 a(x) と、 これを1クロック、2クロック、3クロック遅延した4種類の信号の 排他的論理和（EXOR） をとれば、 その積が求まります。
これらの乗算は、以下の回路で実現できます。
なお、 a(x) は3ビット（3クロック）の時系列信号 [0、1、1] で表しています。
b(x) は4本の垂直の信号線 （すべて1） で表されていることに注意して下さい。
上の図より、以下の式が成立します。
ここで、 b(x) は以下のようになります。
このとき出力 c(x) = x 5+ x となり、6ビットの時系列信号 [0、1、0、0、0、1] が得られます。
最も下位のビットは 0 で、 a(x) の下位ビット入力した1クロック目に出力されます。
また、最上位のビット 1 は、 a(x) の下位ビットを入力した5クロック後に出力されます。
[例2] b(x) =x3+x+1
次に、5ビットの数値 a(x)=x4+x+1 と 4ビットの数値 b(x) =x3+x+1 の乗算について考えてみましょう。
この乗算回路とタイムチャートを、以下の図に示します。
入力 a(x)=x4+x+1 は、時系列の5ビットデータ [1、1、0、0、1] に対応します。
もう一方の入力 b(x)=x3+x+1 は、時系列の4ビットデータでは [1、1、0、1] に対応しますが、この場合固定した4本の信号線 （1011） で表されます。
左側のEXORが上位、右側のEXORが下位に対応することに注意して下さい。
最も下位のビットは 1 (1) で、1クロック目に出力されます。
また、最後に出力された 1 は最上位の8ビット目 (x7) であり、8クロック目に出力されます。
なお、 b(x) が時間的に変わりうる場合は、これらのAND回路が必要となりますが、 b(x) が一定の場合、単純な配線だけで構成することが可能です。
その場合、左側のEXORも省略することができます。
なお、 b(x) を可変とする場合でも、 a(x) が計算されている期間は、 b(x) を一定の値に保つ必要があることは言うまでもありません。
(2) ビットの上位から計算する場合
ビットの上位から先に計算するとき、下の桁ほど時間的には遅れることになります。
1クロックの遅延を x-1 で表すとき （xではありません）、 1+x-1 は連続する2ビットの時系列信号 [1、1] に対応します。
また、 1+x-1 に x-1 を通す（掛ける）と、 x-1+x-2 、すなわち [0、1、1] になり、1クロック遅延することになります。
同様に 1+x-1+x-4 は5ビットの時系列信号 [1、1、0、0、1] に対応します。
ビット列 （11001） と、時系列の信号 [1、1、0、0、1] は、同じ順のビット列となっていることに注意して下さい。
先ほどと同じように、5ビットの数値 a(x) = x4+x+1 と 4ビットの数値 b(x) = x3+x2+x+1 の乗算を考えましょう。
次のブロック図で、1クロックの遅延回路が x-1 で表されている点に注意して下さい。
上図より、次式が得られます。
x -1 は1クロックの遅延を表すため、 x は過去の方向に1クロックさかのぼる操作に対応します。
実際には、信号を遅らすことはできても、時間をさかのぼって過去の信号を求めることはできません。
（信号の記録・保存自体は、過去において将来のために信号を遅らせている操作に相当します。）
そこで、演算操作の全体を時間が遅れる方向にシフトして実現します。
例えば、当初計算しようとした b(x) = x3+x2+x+1 の代わりに b(x)' = b(x) / x3 = 1+x-1+x-2+x-3 を用いることにします。
同様に、 a(x) = x4+x+1 の代わりに a(x)' = a(x) / x4 = 1+x-3+x-4 を計算します。
それらの積は a(x)' b(x)' = 1+x-2+x-4+x-5+x-7 となりますが、これに x7 を乗じると、求める a(x) b(x) = x7+x5+x3+x2+1 となることは明らかです。
これは、7クロック分遅れて、 積 (c) が出力されることに相当します。
この回路図とフローチャートを次の図に示します。
上位のビットから下位ビットの順に、乗算の結果が出力されていることに注意して下さい。
3.3 D-FFを用いた除算回路（上位→下位）
乗算と同様に、遅延素子（例えばD-FF）を用いて 除算（割り算）回路 を構成することができます。[例1] b(x) = x4 + x3 + x2 + x + 1
除算 の場合、上位から計算する手法が用いられます。
これは、除算では割り切れない場合があるからです。
その場合、必要なビットまで下位の方向に商を求める操作を繰り返します。
除算の回路では、 乗算に比べ回路が若干複雑になります。
これは、出力が入力側に戻るフィードバックのループが生じるためです。
以下、具体的な例を用いて詳しく説明しましょう。
下の図に、 c(x) = a (x) / b(x) の 除算 を行う回路を示します。ただし、遅延素子を x-1 で表しています。
ここで、 b(x) = x4+x3+x2+x+1 としています。
出力を c(x) とすると、それぞれの 遅延素子（x-1で表記） の出力は、それぞれ図のようになっています。
出力部分で、右端の遅延素子の 出力 = c(x) とおくと、次式が得られます。
｛カッコ｝ をはずすために 分配側 を用いて展開し、 c(x) を移項して整理すると、次の式が導かれます。
ここで、b(x) は、次式で表されます。
すなわち、出力 c(x) は、 除算 a(x) / b(x) の商になっていることがわかります。
[例2] b(x) = x4+x2+1
次に、別の b(x) を用いた場合について、論理回路がどのように変化するのか、検証してみましょう。
今度は、 b(x) = x4+x2+1 とします。
このときの回路図は、次のようになります。
上の式を導出してみましょう。
最終段の遅延素子 （xで表記） について、以下の関係が成立します。
{カッコ} をはずして分配側を用いて展開し、 c(x) を移項すると、次の式が得られます。
これより、 b(x) が以下のように求められます。
［例3］ b(x) = x5+x2+1
次に、5次の b(x) = x5+x2+1 の例を示します。
回路は以下の通りです。
回路図から入出力の関係を求めると、以下のようになります。
これより、次式が成立します。
このような 除算回路 の構成は理解できたと思います。
次に、実際の除算が行われる動作について、詳しく眺めてみましょう。
今度は、4次の b(x) = x4+x+1 を用います。
回路は、以下のようになります。
ここで、 a(x) は次のようにします。
この結果、商の c(x) は次のようになります。
ここで、商を計算すると、以下のようになります。
このような 除算 の動作とその タイムチャート を、次の図に示します。
a(x) =x4 から4クロック遅れて、 c(x) の1項目 (1) が出力され、2クロック0が続いたあと、 x -3とx-4 が1になっていることがわかります。
なお、この商は、15桁を周期とする 循環小数 の形になっています。
次章では、このような循環小数を利用した ランダムパタン発生回路 について説明します。
４ まとめ
本章では、 modulo2の定義 とそれらの論理演算回路の構成法 を中心に解説しました。
次章では、この具体的な応用例として「疑似ランダムパタン発生回路」を紹介します。
論理回路2のトップページに戻る
