第4章 組合せ論理回路 (4)

第4章 組合せ論理回路 (4)
Quine McCluskeyの方法
論理変数の作る空間

n-cube
1変数の作る空間
m0
m1
2変数の作る空間
m2 10
0-cube
1-cube
2-cube
m1 m3 11
m0
m0 00
m1
m0
m1 01
論理変数の作る空間(続き)

3変数の作る空間
Cube の結合
– 0-cube 110, 111 は 1-cube 11x に含まれる.
– 0-cube 110 や 1-cube 11x は 2-cube 1xx
に含まれる(覆われている).
Q-M法

カルノー図による方法は
– 直感に頼る.
– 6変数以上であるとやりにくい.

系統的な方法は?
– Q-M法 最良の2次形式を得るアルゴリズミッ
クな手続きを与える.
– あらゆるcubeを系統的に調べ尽くす.
例題
– これらの0-cubeからどのようなcubeができる
か?
隣接する項は“1”の数が
1だけ違うはずである.
“1”の個数でまとめてみる.














0000



0010
00x0
主項

定義 の付いている項はそれ以上に大きい
cubeに含まれている.
の付いていない項は,この関数の中でもっと大
きなcubeに含まれないcubeである.このような
項を主項(prime implicant) という.
0 - cube m13  1101 
  1- cube m13,9  1x01
1- cube
m9  1001

隣接する項は
– 2 k だけ違う.
– “1”の個数の多いほうが値が大きい.
a
b
c
d
定理
最小の積和形式は主項の和で表される

証明 もし主項でないものが含まれている
ならば,それを含む主項で置き換えれば,
さらに小さな式になる.
*
*
*
 


 



必須項をリテラルで表す

*の付いているのが必須項
例題
*
*
*
*
*
     
     


2次必須項
交換可能

定義 交換可能
– 縮小した主項表で,2つの行 a, b が同じ最小
項をカバーするとき,a と b は交換可能であ
るという.
– Aがbに  のあるすべてのカラムに  を持ち,
b に  のないカラムで少なくとも1つの  を
持つときに,a は b を支配するという.
定理
a, b はともに縮小した主項表の行とする.
a のコストは b のコスト以下であるとする.
このとき a が b を支配するかまたは b と
交換可能であれば,b を含まない最小の
積和形式が存在する.
Don’t care の取り扱い

主項を決定するときには“1”として取り扱
い,主項表により必須項を決定するときに
は無視して,最小項のみとする.
乗法標準形の解

f を積和形式で作り,ドモルガンの定理に
よって変換する.