本連載はHisa Ando氏による連載「コンピュータアーキテクチャ」の初掲載(2005年9月20日掲載)から第72回(2007年3月31日掲載)までの原稿を再掲載したものとなります。第73回以降、最新のものにつきましては、コチラにて、ご確認ください。
話がちょっと横道にそれるが、ここで論理回路の簡単化に便利なカルノーマップ(Karnaugh Map)について説明しておこう。次の表は6入力、1出力のカルノーマップを示している。便宜上、縦方向を入力A、B、C、横方向を入力D、E、Fとする。そして、入力A～Fの値に対してどのような値を出力すべきかを各欄の中に記入する。通常は、"1"、または"0"を記入するが、どちらが出力されても良い場合は、"＊"を記入する。
ここで注意して欲しいのは、欄の2進数の順序である。通常の2進数の並びではなく、隣接する欄の値は、必ず1ビットしか変化していない。この並び方をGray Codeと言う。左側の縦の列を見ると、まず、最下位のビットは、最初は0、その次は1である。3番目と4番目はこれを反転して1、0とする。次のビットは2ビットずつ連続として、0、0、1、1とする。そして、5～8番目の欄の下位2ビット分は1～4番目の欄を上下反転して記入する。3ビット目は4ビットずつ連続で、0、0、0、0、1、1、1、1と記入する。これで3ビットのGray Codeが出来上がる。横方向の欄も、同じGray Codeの並びとする。
このカルノーマップで隣接する二つの欄は、それが上下でも左右でも、入力は1ビットしか異なっていない欄である。この二つの欄の出力値が"1"であるということは、隣接する欄の間で異なっている入力ビットが"1"であるか"0"であるかに係わらず"1"が出力されるということであり、論理式の中から、この入力項を削除することが出来る。このようにしてみると、上の表で、灰色で塗った二つの欄は出力が"1"であり、入力A,B,Cが101と100で同じ出力となっている。つまり、C入力の値には無関係に、A,Bが1,0、D,E,Fが0,0,1の場合に出力は"1"となる。従って、
- Out=A・*B・*D・*E・F
という論理でこの出力を作ることが出来る。
同様に4個の隣接する欄の出力値が同じであれば、それらの欄の間で異なっている2ビットの入力には出力は影響されないので、それらの入力項を論理式から削除できる。黄色で塗った4つの欄は、CとFの値には依存せず、A,Bが0,0、D,Eが1,0になると出力が"1"になるように論理を構成すれば良い。しかし、実は、カルノーマップの上下、左右の端は反対側とくっついており、ドーナツの表面のようなトーラス、あるいは球面に貼り付けられている形になっている。この関係を考慮すると、クリーム色に塗った4つの欄とも隣接しており、8個の欄の隣接であることが分かる。この場合は、出力はAの値にも依存せず、B,D,Eが0,1,0という条件だけで論理を作れば良い。
ピンクに塗った領域はすべての欄の出力が"1"では無いが、"＊"の欄は出力値を勝手に決めて良い欄であるので、ここでは"1"を出力すると決めれば、8個の欄の隣接となる。
薄い水色に塗った領域は4つ欄の隣接であるが、その上の4つの欄と合わせて考えれば8個の隣接となり、A,B,Dが0,1,0の条件で論理を作れば良い。この場合、A,B,C,Dが0,1,1,0ピンクの下半分の4つの欄は二つの領域に含まれることになるが、問題は無い。結果として、この表は、上記の全ての項をORして、
- Out=(A・*B・*D・*E・F) + (*B・D・*E) + (*A・C・*D) + (*A・B・*D)
で実現できる。
この例題では"＊"の欄が少なかったが、実際の設計ではかなりの欄が"＊"となるケースが多いので、これを上手く使うとANDする入力数やORの項を減らして論理を簡単化できる。このようにカルノーマップは便利な手法であるが、2次元の表に記入するため、6入力を超えると全ての隣接関係を表現できないという制約がある。
