論理回路とブール代数(2) 論理回路の簡単化と回路設計

前章の問題【1】

を例に説明します。どの式でも真理値を求めればカルノー図を作れます。積和形なら、各積項が1になるマスを順に記入する方法が便利です。この例はすでに積和形になっています。 次に、2変数のカルノー図は \(x\) と \(y\) の値の組合せで \(2\times 2\) のマス目を書き、2変数の値

に対応させます(下図参照)。

論理式 \(x + \bar x\cdot y + x\cdot\bar y\) の左側の項から順に考えることにします。

ここまで作図ができたら、4マスのうち3マスに1が書かれた状態になっています（左図）。説明のために左図には3つの項に対応する囲み枠を3つ書いていますが、実際にはこの時点で囲みは書きません。

次の工程が重要です。

すると、すべての1を囲むには、右図のように少なくとも緑と茶の2つの枠が必要になります。また、\((x,y)=(1,1)\) の部分で緑と茶の枠が重なりますが、これは、ちょうど\(2^n\)個のマスを含む枠で、かつ、できるだけ大きく囲むという決まりがあるためです。

後は、囲んだ2つの枠を解釈して積和形の論理式に戻すだけです。茶色の枠は、\(x=1\) で \(y\) は0,1どちらの値もとるので、項 \(x\) を表しています。また、緑の枠も同様に項 \(y\) を表していますので、積和形論理式の形に戻すと、

が得られました。

ANDゲートとNOTゲートからORゲートが構成できることを示します。

つまり、以下の論理回路でORゲートが構成できます。

ORゲートとNOTゲートの関数的完全性については、同様に示せますので省略します。

実際の回路設計ではNANDゲートとよばれる論理ゲートのみを使った回路設計がよくみられます。これは、NANDゲートが技術的には比較的容易に構成可能であること、および、NANDゲートのみで関数的完全性が成り立つことによります。NANDゲートに対応する二項論理演算子を \(\uparrow\) で表し、論理ゲートは右図の記号で表すことにします。NANDゲートとは次のような論理式で定義される論理ゲートです。

NANDゲートの真理値表を下記に示します。

これは、論理積の結果を反転させた関数です。

さて、NANDゲートのみでNOTゲート、ANDゲート、ORゲートがすべて実現できることを示して、NANDゲートのみで、すべての論理関数を構成できることを示しましょう。

まず、2入力データセレクタを論理回路で構成してみましょう。下図がセレクタの図です。この回路は、2つのデータ \(d_0\) と \(d_1\) を入力として受け取ります。そして、セレクタ \(s\) の値に応じて \(d_0\) と \(d_1\) のどちらを \(y\) に出力するか決定します。つまり、\(s=0\) のとき \(y=d_0\)、\(s=1\) のとき \(y=d_1\) となります。この回路は複数回線の通信データを1回線にまとめるときによく用いられますので、回線多重化回路（マルチプレクサ）ともよばれます。

下の表に2入力データセレクタの動作を真理値表として示しました。 \(s=0\) のとき \(y=d_0\)、\(s=1\) のとき \(y=d_1\) となるように、あらゆる入力の組合せを記述していることを確認してください。

カルノー図をつかってこの回路を設計してみましょう。 まず、積和標準形によって出力 \(y\) を記述します。\(y=1\) に対応する最小項を求め、その和をとることにより、次のように積和標準形が得られます。

次に、カルノー図を作成します。左下図のように、最小項に対応するマス目に1を書きます。そして、右下図のように、1の書かれたマス目のみを \(2^n\) 個の単位でできるだけ大きく囲む枠を描きます。

こうして、1を覆った2つの枠に対応する積項を求め、論理和で接続することにより次式を得ます。

よって、2入力セレクタの論理回路は次のようになります。

2進法の数の足し算をする回路を組合せ回路で設計します。まず、1ビットの数 \(x\) と \(y\) の足し算について考えます。すると、計算は次の表のようになります。

和 \(s\) については論理和ではないことに注意してください。2進法の加算として \(1+1=10\) となるので、和は \(s=0\)、桁上げは \(c=1\) となります。（和の記号として \(s\) を使うのは和の英語 sum から、桁上げの記号として \(c\) を使うのは桁上げの英語 carry からです。）

この論理回路は2入力、2出力ですので、\(f_1(x,y)=s\) と、\(f_2(x,y)=c\) の2つの論理関数から回路を設計することになります。まず、簡単な桁上げの方から見てみましょう。桁上げの \(f_2(x,y)=c\) は真理値表からANDゲートそのものであることがわかります。

次に、和の \(f_1(x,y)=s\) は、 入力 \(x\) と \(y\) のどちらか1つが1のときのみ、出力 \(s\) が1となるような回路です。この回路はXORゲートとして様々な場面で用いられます。XORは exclusive or の省略形で、日本語では排他的論理和といいます。

よって、半加算器はXORゲートを用いると左下図のようになります。また、半加算器を右下図のように表現することにします。

前節の半加算器は、このままでは複数桁の2進法の数の足し算には使えません。なぜなら、上位の桁では下位の桁からの桁上りを考慮する必要があるからです。つまり、下位からの桁上げ \(c_{\text{in}}\) と上位への桁上げ \(c_{\text{out}}\) の2つの桁上げを考慮する必要があります。これは3つの1ビットの数 \(x\)、\(y\)、\(c_{\text{in}}\) を足す加算器と考えればよいので、真理値表は次のようになります。

詳細な計算は省きますが、2つの半加算器を2段繋げば、3つの1ビットの数の和が求められることは明らかでしょう。ここでは、\((x+y)+c_{\text{in}}\) の順に足し合わせています。上位への桁上げ \(c_{\text{out}}\) は、2つの半加算器のいずれかの桁上げがあれば、上位に送るだけですのでORゲートを用います。このORゲートの2つの入力が2つとも1になることはないことに注意してください。

よって、全加算器は半加算器とORゲートを用いて左下図のように構成できます。また、全加算器を右下図のように表現することにします。

これで、複数桁の2つの2進数の数を足し合わせる回路を構成する準備ができました。 あとは、組み合わせるだけです。

まず、入力となる2進法の数 \(x\) と \(y\) をそれぞれ4ビットとします。各桁の1ビットの値を、それぞれ \(x_i\) と \(y_i\) で次のように表します。

たとえば、\(x=1011\) のときは \(x_1=1\), \(x_2=1\), \(x_3=0\), \(x_4=1\) となります。 すると、4ビットの加算器は下記のように構成できます（計算結果は \(s=s_4s_3s_2s_1\)）。最上位の桁上げ \(c_{\text{out}}\) は5桁目（あふれ）を表します。

ブール代数による式を論理回路として表現するときには、遅延時間を考慮する必要があります。 論理関数としては、結合律がなりたちますので次式の両辺は等価です。

しかし、論理回路としては左辺は左図、右辺は右図のようになります。

左辺はANDゲートが3段、右辺は2段の深さです。値が入力されてから論理回路の値が決まるまでの時間を論理回路の遅延時間といいます。左図では、入力 \(w\) と \(x\) は3段のANDゲートを通るため、この部分が左図の回路の遅延時間を決定づけています。つまり、右の論理回路より、左の論理回路の方が遅延時間が長くなってしまうのです。遅延は素子、電圧、負荷などに依存し、個別の論理ICではナノ秒単位の場合もあります。例えば仮に各ゲートの遅延を同じ100ピコ秒とすれば、3段で300ピコ秒、2段で200ピコ秒となります（1ピコ秒は10^-12秒）。

この遅延時間は、先ほど作った加算器でも問題になります。先の4ビット加算器では、各桁の全加算器が下の桁からの桁上げを受け取ってから計算するため、桁上げが最下位から最上位へ順に伝わるのを待つ必要があります。この方式を桁上げ伝搬加算器(リップルキャリー加算器)とよびます。桁数が増えるほど桁上げの伝搬段数が増え、遅延時間が長くなります。そこで、桁上げをあらかじめ別経路でまとめて計算する桁上げ先見加算器(キャリールックアヘッド加算器)など、より速い加算回路が考案されています。回路は論理関数として正しいだけでは十分でなく、遅延時間まで考えて設計する必要があるのです。