論理回路2

第7章 順序回路の応用(その1)

−modulo2の論理演算回路−

井澤 裕司  


1 はじめに

一般のコンピュータでは、 2進数による四則演算(加減乗除) が用いられています。

(詳しくは、「論理回路1」第1章、第2章を参照のこと。)

一方、通信や記録の分野では、 伝送時や書き込み・読み出し時に発生する エラーの影響 を取り除く技術として、

誤り訂正 をはじめとする 符号理論 があります。

この符号理論では、通常の2進数とは異なる 「modulo2」 と称する演算が用いられます。

この演算では、2進数の加算における桁上げ操作を 無視 し、 加算と減算 同じ結果 になります。

一般的な感覚からすれば 変則的な演算 に思われますが、 その実用的な価値は高く、

1と0のビット列の中から 誤りの有無を検出 したり、 誤りを訂正 する手法に用いられています。


本章では、その基礎となる演算規則と、 それらを論理回路で実現する方法を中心に解説します。



2 modulo2の演算規則

それでは、 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の 乗算と除算 についても、次の例のように計算することができます。

これらの式は、最初は奇異に思えるかもしれませんが、とにかく慣れるよう努めて下さい。


3  modulo2の演算回路


ここでは、modulo2の加減乗除を実現する 論理演算回路 について解説します。


3.1 加算回路


modulo2の 加算 は簡単です。

定義から、 排他的論理和(EXOR) で実現できることは明らかです。

先ほど述べたように、加算と減算の区別はなく、それらの結果も同じ形になります。

なお、 複数ビット に拡張する場合は、 EXOR をビット数分、並列に配置します。


3.2 D-FFを用いた乗算回路


1ビットの 乗算回路 の出力は1ビットであり、定義式から 論理積(AND) で構成されることは明らかです。

ここで、複数ビット数の 乗算 に拡張してみましょう。

通常の2進数の場合、乗算はビットシフトと加算に分解して計算しました。 (「論理回路1」参照)

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クロックの遅延を 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] では、上位と下位が 逆転 していることに注意して下さい。

[例1] b(x) = x 3+x2+x+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) = x 4+x+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桁を周期とする 循環小数 の形になっています。


次章では、このような循環小数を利用した ランダムパタン発生回路 について説明します


4 まとめ

本章では、 modulo2の定義 とそれらの論理演算回路の構成法 を中心に解説しました。

次章では、この具体的な応用例として「疑似ランダムパタン発生回路」を紹介します。

論理回路2のトップページに戻る