クワイン・マクラスキー法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

クワイン・マクラスキー法(—ほう; Quine-McCluskey algorithm/略:QM法)はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。

クワイン・マクラスキー法は3段階からなる。

  1. 関数の主項をすべて求める
  2. 求めた主項を表にまとめ、必須項を求める
  3. 最簡形を求める

[編集]

主項を求める[編集]

以下の真理値表で表されるブール関数を簡単化する。

f
  A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 1 0 0
m5 0 1 1 1 0
m6 0 1 0 0 1
m7 0 1 0 1 0
m8 1 1 0 0 1
m9 1 1 0 1 0
m10 1 1 1 0 X
m11 1 1 1 1 1
m12 1 0 1 0 1
m13 1 0 1 1 1
m14 1 0 0 0 1
m15 1 0 0 1 X

X は Don't care を表す。

この関数の選言標準形は、最小項の和をとって(Don't care は無視する)

f = \overline{A} B \overline{C} \overline{D} + A B \overline{C} \overline{D} + A B C D + A \overline{B} C \overline{D} + A \overline{B} C D + A \overline{B} \overline{C} \overline{D}

となる。

もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数(ハミング重み)ごとに表に列挙する。また Don't care の項も加える。

1の数 最小項 ビット列表現
1 m6 0100
m14 1000
2 m8 1100
m12 1010
m15 1001
3 m10 1110
m13 1011
4 m11 1111

これで最初の準備が整った。1ビットのみが異なっている(ハミング距離が1となる)最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項にはしるし(*)をつける。この印を付けた項が主項となる。

1の数 最小項 ビット列表現
1 m6 0100
m14 1000
2 m8 1100
m12 1010
m15 1001
3 m10 1110
m13 1011
4 m11 1111
1回目の比較
1 m6,8 -100 *
m8,14 1-00
m12,14 10-0
m14,15 100-
2 m8,10 11-0
m10,12 1-10
m12,13 101-
m13,15 10-1
3 m10,11 111-
m11,13 1-11
2回目の比較
m8,10,12,14 1--0 *
m12,13,14,15 10-- *
m10,11,12,13 1-1- *

必須項を求める[編集]

主項のなかから必須項をみつける。横軸に最小項(Don't care でないもの)、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし(X)を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。

  6 8 11 12 13 14
m6,8 * X X -100
m8,10,12,14 X X X 1--0
m12,13,14,15 X X X 10--
m10,11,12,13 * X X X 1-1-

例では2つ必須項が求まった。表中でしるし(*)をつけてある。必須項はその名のとおり、簡単化した関数に必ず含まれていなければならない項である。

最簡形を求める[編集]

式を短くするために主項に番号を振りなおす。m6,8 = e1 , m8,10,12,14 = e2 , m12,13,14,15 = e3 , m10,11,12,13 = e4 とおく。

簡単化した後の関数 f はすべての最小項をカバーしていなければならない。最小項 m8 が含まれる条件はブール代数式で (e1 + e2) となる。f がすべての最小項を含むためには、

e_1 (e_1 + e_2) e_4 (e_2 + e_3 + e_4) (e_3 + e_4) (e_2 + e_3)

を満たす必要がある。これを展開すると

e_1 e_2 e_3 e_4 + e_1 e_2 e_4 + e_1 e_3 e_4

となる。最も簡単なのは e1e2e4 または e1e3e4 である。よって最簡形は

f = e_1 + e_2 + e_4 = B \overline{C} \overline{D} + A \overline{D} + A C

または

f = e_1 + e_3 + e_4 = B \overline{C} \overline{D} + A \overline{B} + A C

である。

計算量[編集]

4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。充足可能性問題というNP困難な問題を対象としているため、実行時間が入力長の指数関数的に増加してしまうのである。n変数関数における主項の数の上限は3nとなる。n = 32とおくと、主項の数は6.5 × 1015を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。

関連項目[編集]

参考文献[編集]

  • 田丸 啓吉 『論理回路の基礎(改訂版)』 工学図書株式会社、1989年ISBN 4-7692-0204-0

外部リンク[編集]