Enjoy every moment!: [小筆記] Quine-McCluskey演算法

Quine-McCluskey 演算法是最小化布爾函數的一種方法。它在功能上等同於卡諾圖，但是它的表格形式使它更有效的用做計算機演算法，並且它還給出了檢查布爾函數是否達到了最小化形式的確定性方法。

方法涉及兩步：

找到這個函數的所有素蘊涵項。
使用這些素蘊涵項（implicant）來找到這個函數的本質素蘊涵項，對覆蓋這個函數是必須的其他素蘊涵項也同樣要使用。

例子

最小化一個任意的函數：

$f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14). \,$

	A	B	C	D	f(A,B,C,D)
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

你能輕易的形成這個表的規範的積之和表達式，簡單的通過總和這個函數求值為一的那些極小項(除掉那些不必要項)：

$f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD \,$

第一步找到素蘊涵項

當然，這的確不是最小化的。為了優化，所有求值為一的極小項都首先放到極小項表中，不必要項也可以加入這個表中與極小項組合：

1的數目	極小項	二進制表示
1	m4	0100
1	m8	1000
2	m9	1001
	m10	1010
	m12	1100
3	m11	1011
3	m14	1110
4	m15	1111

現在你可以開始把極小項同其他極小項組合在一起。如果兩個項不同只是一個單一的數字，則可以這個數字替代為一個橫杠，來指示這個數字無關緊要。不再組合的項標記上 "*"。

1的數目	極小項	0-立方	大小為2的蘊涵項	大小為4的蘊涵項
1	m4	0100	m(4,12) -100*	m(8,9,10,11) 10--*
1	m8	1000	m(8,9) 100-	m(8,10,12,14) 1--0*
---------	---------	---------	m(8,10) 10-0	--------------------------
2	m9	1001	m(8,12) 1-00	m(10,11,14,15) 1-1-*
	m10	1010	-----------------------	--------------------------
	m12	1100	m(9,11) 10-1	--------------------------
---------	---------	---------	m(10,11) 101-	--------------------------
3	m11	1011	m(10,14) 1-10	--------------------------
3	m14	1110	m(12,14) 11-0	--------------------------
4	m15	1111	m(11,15) 1-11	--------------------------
4			m(14,15) 111-

第二步找到本質素蘊涵項

沒有項可以繼續進一步這樣組合，所以現在我們構造一個本質素蘊涵項表。縱向是剛才生成的素蘊涵項，橫向是早先指定的極小項。

	4	8	10	11	12	15		=>	A	B	C	D
m(4,12)*	X				X		-100	=>	-	1	0	0
m(8,9,10,11)		X	X	X			10--	=>	1	0	-	-
m(8,10,12,14)		X	X		X		1--0	=>	1	-	-	0
m(10,11,14,15)*			X	X		X	1-1-	=>	1	-	1	-

這裡的每個本質素蘊涵項都標記了星號 - 第二個素蘊涵項能被第三個和第四個所覆蓋，而第三個素蘊涵能被第二個和第一個所覆蓋，因此都不是本質的。如果一個素蘊涵項是本質的，則同希望的一樣，它必須包含在最小化的布爾等式中。在某些情況下，本質素蘊涵形不能覆蓋所有的極小項，此時可採用額外的簡約過程。最簡單的「額外過程」是反覆試驗，而更系統的方式是Petrick方法。在當前這個例子中，本質素蘊涵項不能處理所有的極小項，你可以組合這兩個本質素蘊涵項於兩個非素蘊涵項中的一個而生成：

$f_{A,B,C,D} = BC'D' + AB' + AC \,$