論理回路の簡単化のクワイン法とクワイン・マクラスキー法について

$論理回路の簡単化のクワイン法とクワイン・マクラスキー法について$

1. クワイン法とクワイン・マクラスキー法
2. クワイン法の手順
2.1. クワイン法の例題
3. クワイン・マクラスキー法の手順
3.1. クワイン・マクラスキー法の例題

1. クワイン法とクワイン・マクラスキー法

クワイン法とクワイン・マクラスキー法(QM法)は、論理回路の簡単化を行うことができる手法の一つです。簡単化はカルノー図を使えばできますが、変数が増えると簡単化が難しくなります。また、カルノー図は直観的であるため、人間にはわかりやすいがコンピュータで処理を行うことには向いていません。一方で、クワイン・マクラスキー法はカルノー図では向いていないコンピュータにおける処理や変数が増えても対応可能です。

2. クワイン法の手順

クワイン法の手順は以下のようになります。

step1 主加法標準展開を行う。
step2 圧縮を行う。
step3 主項図を用いて最簡形を求める。

具体的な手法は、例題を見て手順を確認してみましょう。

2.1. クワイン法の例題

以下の論理式の最簡形をクワイン法を用いて求めよ。

(1)$Y=A\cdot B\cdot D+A\cdot B\cdot C\cdot\overline{D}+A\cdot B\cdot\overline{C}\cdot\overline{D}$

(2)$Y=\overline{A}\cdot C+\overline{A}\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{B}\cdot D+A\cdot B\cdot C\cdot \overline{D}$

(1)step1の主加法標準展開を行うと、

$$Y=A\cdot B\cdot C\cdot D+A\cdot B\cdot\overline{C}\cdot D+A\cdot B\cdot C\cdot\overline{D}+A\cdot B\cdot\overline{C}\cdot\overline{D}$$

となる。次に求めた、最小項を2進数に対応させます。

$2進数に対応$

次に、step2の圧縮表を作ります。まず、一番左に、最小項を２進数の数が小さい順に並べます。

各項に対して、$A\cdot(B+\overline{B})=A$のように圧縮を行います。例えば、最小項の内、$A\cdot B\cdot C\cdot D$と$A\cdot B\cdot C\cdot\overline{D}$を圧縮すると、$A\cdot B\cdot C$となります。圧縮はできなくなるまで行います。まず、1次圧縮を行うと以下のようになる。

次に、2次圧縮を行うと以下のようになる。

よって、主項は2次圧縮の項であることから、$A\cdot B$であることが分かった。

step3の主項図を作ると以下のようになる。$A\cdot B$の場合、主項図の作り方は$A\cdot B$が最小項に含まれているときに〇を交点上に書く。

したがって、論理式は必須となる部分を考えると

$$Y=A\cdot B$$

となる。
(2)主加法標準展開を行うと、

$$Y=\overline{A}\cdot\overline{B}\cdot\overline{C}\cdot\overline{D} + \overline{A}\cdot\overline{B}\cdot\overline{C}\cdot D + \overline{A}\cdot\overline{B}\cdot C\cdot\overline{D} + \overline{A}\cdot\overline{B}\cdot C\cdot D + \overline{A}\cdot B\cdot C\cdot\overline{D} \\ + \overline{A}\cdot B\cdot C\cdot D + A\cdot\overline{B}\cdot\overline{C}\cdot D + A\cdot\overline{B}\cdot C\cdot D + A\cdot B\cdot C\cdot \overline{D}$$

となる。

圧縮表を作ると以下のようになる。圧縮ができた項にはチェックをつける。

$圧縮表$

よって、主項はチェックマークのついていないものであるから、$\overline{A}\cdot \overline{B}$、$\overline{A}\cdot C$、$\overline{B}\cdot D$、$B\cdot C\cdot\overline{D}$であることが分かった。

主項図を作ると以下のようになる。

表の列に関して〇が一つしか含まれていない部分は必ず必要な部分であるから、その部分を紫色の線で引く。紫色の線上の〇のある行の主項が最簡形の論理式の一つであるから、最簡形は以下のようになります。

$$Y=\overline{A}\cdot \overline{B}+\overline{A}\cdot C+\overline{B}\cdot D+B\cdot C\cdot\overline{D}$$

3. クワイン・マクラスキー法の手順

クワイン・マクラスキー法はクワイン法が改良された方法です。例題を用いて説明します。例題は先ほどの例題の(2)と同じ問題です。

3.1. クワイン・マクラスキー法の例題

以下の論理式の最簡形をクワイン・マクラスキー法を用いて求めよ。

$$Y=\overline{A}\cdot C+\overline{A}\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{B}\cdot D+A\cdot B\cdot C\cdot \overline{D}$$

主加法標準展開を行うと、

となる。最小項を2進数に対応させた数の１の個数に関して着目し表をつくる。

ハミング距離が1である数を選択して、圧縮を行う。ハミング距離が1である数は例えば100と110が挙げられ、圧縮を行うと1_0とする。このような1bitだけ違う（先ほどの例だと真ん中の部分）数をハミング距離が1であるという。また、圧縮した部分は　$\mathrm{＿}$　で表記して、チェックをつける。