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

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

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

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

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

[編集]

主項を求める[編集]

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

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 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1

X は Don't care を表す。

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

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

となる。

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

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

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

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

必須項を求める[編集]

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

  4 8 10 11 12 15
m4,12 * X X -100
m8,9,10,11 X X X 10--
m8,10,12,14 X X X 1--0
m10,11,14,15 * X X X 1-1-

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

最簡形を求める[編集]

必須項だけでは全ての最小項をカバーできていないので、更なる作業が必要になる。最もシンプルな方法は、試行錯誤して最簡形を見つけることであるが、より系統的な方法として、ペトリック法(en:Petrick's method)がある。このケースでは、次の最簡形を得る。

\begin{align}
f & = B \overline{C} \overline{D} + A \overline{D} + A C\\
  & = B \overline{C} \overline{D} + A \overline{B} + A C
\end{align}

計算量[編集]

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

関連項目[編集]

参考文献[編集]

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

外部リンク[編集]