跳至內容

奎因-麥克拉斯基算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

奎因-麥克拉斯基算法Quine-McCluskey算法)是最小化布爾函數的一種方法。它在功能上等同於卡諾圖,但是它具有文字表格的形式,因此它更適合用於電子設計自動化算法的實現,並且它還給出了檢查布爾函數是否達到了最小化形式的確定性方法。

方法涉及兩步:

  1. 找到這個函數的所有素蘊涵項
  2. 使用這些素蘊涵項(prime implicant)來找到這個函數的本質素蘊涵項(essential prime implicant),對覆蓋這個函數是必須的其他素蘊涵項也同樣要使用。

複雜度

儘管在處理多於四個變量的時候比卡諾圖更加實用,奎因-麥克拉斯基算法也有使用限制,因為它解決的問題是NP-困難的:奎因-麥克拉斯基算法的運行時間隨輸入大小而呈指數增長。可以證明對於n個變量的函數,素蘊涵項的數目的上界是3n/n。如果n = 32,則可能超過6.1 * 1014,或617萬億個素蘊涵項。有大量變量的函數必須使用潛在的非最優的啟發式方法來最小化。

例子

最小化一個任意的函數:

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

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

第一步找到素蘊涵項

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

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

現在你可以開始把極小項同其他極小項組合在一起。如果兩個項只有一個二進制位的數值不同,則可以這個位的數值可以替代為一個橫槓,來指示這個數字無關緊要。不再組合的項標記上 "*"。

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

第二步找到本質素蘊涵項

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

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方法英語Petrick's_method。在當前這個例子中,本質素蘊涵項不能處理所有的極小項,你可以組合這兩個本質素蘊涵項與兩個非素蘊涵項中的一個而生成:

最終的等式在功能上等價於最初的(冗長)等式:

參見

外部連結