3 カルノー図

3.1 論理式の簡単化について

論理式を簡単化することは非常に重要です。以前学習したように論理式を簡単 化することにより、スイッチの回路は動作を変えることなく部品点数を減らす ことができました。実際のデジタル回路は、スイッチではなくここが半導体 に変わりますが、基本は同じです。この素子(スイッチや半導体)の削減は、実 際の回路では非常にメリットがあります。まず、製造コストが安くなります。 さらに部品点数が減少することで、信頼性が上がります。まだ、メリットはあ ると思います。ようするに技術者は、要求通り動作するだけだけでなく、より 単純化したものを設計しなくてはなりません。ということで、論理式の簡単化 は重要になります。頭を使うだけで、製造コストが下がることは非常に良いこ とです。

今までは、ブール代数の公理や定理を使って論理式を簡単化してきましたが、 論理変数が多くなると、その作業は大変になります。そこで、論理変数が多く なった場合のテクニックをここで学習します。学習する内容は、カルノー図法 とクワイン-マクラスキー法と呼ばれる方法です。

3変数くらいまではブール代数の公理や定理により簡単化はできます。3〜5変 数くらいになるとカルノー図法が有利になってきます。それ以上になると、ク ワイン-マクラスキー法が使われます。

3.2 論理式の簡単化

3.2.1 カルノー図の例1

カルノー図法は、表を使って $A \cdot B \cdot C+A \cdot B \cdot \bar{C}=A \cdot B$や $A \cdot B \cdot C + A \cdot B = A \cdot B$を見つけ出して、 論理式の簡単化する方法です。

なにはともあれ、カルノー図法というもので、論理式を簡単化して見ましょう。 簡単化する論理式は、

$$Z=\bar{A} \cdot B \cdot \bar{C} \cdot \bar{D} +B \cdot \bar{C} \cdot D +A \cdot \bar{B} \cdot C \cdot D +A \cdot C \cdot D +B \cdot C \cdot D$$ (6)

です。これを簡単化するために、カルノー図のための表をまず作成します。論 理変数が$(A,B,C,D)$と4個なので、それらの値の組み合わせは$2^4=16$個あり ます。この組み合わせを表す表として、図1の 表を作成します。

図 1: カルノー図を作成するための表(4変数)。

この表の縦および横は、それぞれの論理変数の値を示しています。これまで学 習してきた真理値表と論理変数の並びが異なることに注意してください。今ま での真理値表は、2進数で値の小さい順に並んでいました。しかし、カルノー 図は、グレイコードで並んでいます²。この表は特殊で、上の端のセルと 下の端のセル、右端のセルと左端のセルは連続していると考えます。グレイコー ドの場合、そのビットで表せる最大の数と最小の数は1ビットしか異なってい なかったことを思い出してください。

表の枠が出来たならば、その中に論理変数に応じた論理式の値を入れていきま す。式(6)は簡単なので、主加法標準展開しなくても、論理 式の値は分かります。右辺は、5個の項から出来ています。その5個の項のうち、 どれかが1になった場合、論理式の値が1になります。論理式が1になる論理変 数$(A,B,C,D)$の値を探します。今後、論理変数の値はこの並びとします。

右辺第1項の値が1になるのは、$(0,1,0,0)$の場合のみです。そこで、それに 対応するセルに1を書き込みます。図2の2行1列に1を書 き込みます。右辺第2項の場合、$A$の項が無いのでそれは0でも$1$でも良く、 $(0,1,0,1)$と$(1,1,0,1)$のとき論理式の値が1になります。これも、表に1を 書き込みます。同様に右辺第3項は$(1,0,1,1)$、第4項は$(1,0,1,1)$と $(1,1,1,1)$、第5項は$(0,1,1,1)$と$(1,1,1,1)$のとき論理式の値が1となり ます。それぞれ1を書き込みます。

次に、この表の中の全ての1を出来るだけ数の少ない正方形を含む長方形(ルー プ)で囲みます。ただし、囲む場合、次の約束があります。

• 囲んだ長方形の中のセルは、全て1であること。 　
• 囲んだ長方形の中のセルの数は、 $1,2,4,,8,\cdots$のように$2^N$で あること。
• 同じセルを2つ以上のループで共有しても良い。
• カルノー図の上下の端、および左右の端は連続していると考える。

囲んだ結果を、図2に示します。3個のループで、囲まれ たことになります。

図 2: カルノー図の例。式(6)を示している。

最後に、この3個のループから共通変数を取り出しその論理積を作ります。そ れぞれの論理積の論理和をとり、論理式を作ります。これが簡略化された論理 式となります。図2のループ1の共通変数の論理積は $\bar{A}\cdot B \cdot \bar{C}$です。ループ2の場合は $A \cdot C \cdot D$、 ループ3の場合は$B \cdot D$となります。これらの論理和は、

$$Z=\bar{A}\cdot B \cdot \bar{C}+A \cdot C \cdot D+B \cdot D$$ (7)

となります。これが、式(6)を簡略化した結果です。

どうですか?。ブール代数の演算規則に従い簡単化するよりは、楽でしょう。 どちらを使うかは、問題を見てより作業の少ないほうで論理式を簡単化すれば よいでしょう。

3.2.2 カルノー図の例2

もう一つ例を示します。簡単化したい論理式は、

$$Z=A \cdot \bar{B} \cdot \bar{C} \cdot \bar{D} +\bar{A} \cdot \bar... ...\cdot C +\bar{A} \cdot B \cdot \bar{C} \cdot \bar{D} +A \cdot B \cdot C \cdot D$$ (8)

です。論理変数の並びを$(A,B,C,D)$とします。式(8)の右 辺のそれぞれの項が1となるのは

第1項	$(1,0,0,0)$の場合
第2項	$(0,0,0,0)$ と$(0,0,0,1)$の場合
第3項	$(1,0,0,1)$と$(1,0,1,1)$の場合
第4項	$(0,0,1,0)$と$(0,0,1,1)$と$(0,1,1,0)$と$(0,1,1,1)$の場合
第5項	$(0,1,0,0)$の場合
第6項	$(1,1,1,1)$の場合

です。それぞれのセルに1を書き入れて、それをループで囲むと図のようになります。3個のループができて、その中に1を4個含んで います。ここでよくよく見て欲しいのは、ループ2や3の場合両端が切れていて も、囲むことが出来ることです。実際には左右の端と上下の端は接続されてい ると考えます。

それぞれの共通項を取り出して、論理積を作ると

ループ1	$C \cdot D$
ループ2	$\bar{B} \cdot \bar{C}$
ループ3	$\bar{A} \cdot \bar{D}$

となります。これらの論理積の論理和をとると、簡単化は完了です。最終的な 式は、

$$Z=C \cdot D + \bar{B} \cdot \bar{C} + \bar{A} \cdot \bar{D}$$ (9)

となります。

図 3: カルノー図の例。式(8)を示している。

3.3 カルノー図のための表

これまでは、4変数のためのカルノー図の表を使いましたが、他の場合につい て、図4に示します。要するに、縦と横の変数の値がグ レイコードになっていれば良いわけです。皆さんは、グレイコードを学習した のでそれを使うほうが良いでしょう。グレイコードになっていない表もありま す。その場合でも、隣同士のセルの変数の値の違いは1ビットで、両端の違い も1ビットになっているはずです。

図 4: カルノー図を作成するための表。

3.4 カルノー図法の手順のまとめ

カルノー図法により論理式を簡単化する方法をまとめると、以下のようになり ます。

1. カルノー図の表を作成する
2. 論理式の値が1に対応するセルに、1を書く。論理式の値は、
   • 真理値表が与えられていれば、それから直接導く。
   • 簡単な論理式の場合は、ブール代数に従い計算する。
   • 複雑な場合は、主加法標準展開を行い、その結果を利用する。
   のようにして計算できる。
3. カルノー図の中の1が書かれているセルを出来るだけ少ない長方形(含 正方形)で囲む。この長方形のことをループという。ただし、その囲む ループには、以下の条件がある。
   • 囲んだ長方形の中のセルは、全て1であること。 　
   • 囲んだ長方形の中のセルの数は、 $1,2,4,,8,\cdots$のように$2^N$で あること。
   • 同じセルを2つ以上のループで共有しても良い。
   • カルノー図の上下の端、および左右の端は連続していると考える。
4. 出来るだけ少ない長方形で囲むためには、以下の手順でループを作れ ばよい。
   1. 他の1と隣接していない1をループで囲む。
   2. 2つの隣接セルとして組み合わされて、4つの隣接セルとならな い1をループで囲む。
   3. 4つの隣接セルとして組み合わされて、8つの隣接セルとならな い1をループで囲む。

   4. 8、16と同様に進めて、1が尽きたらループの作業を止める。
5. それぞれのループから共通変数を取り出し、ループ毎に論理積を作り ます。そしてこれらの論理積の論理和を取り論理式を作ります。これが 簡略化された論理式となる。

ホームページ: Yamamoto's laboratory
著者: 山本昌志