新闻资讯
看你所看,想你所想

奎因-麦克拉斯基算法

奎因-麦克拉斯基算法

Quine-McCluskey算法一般指本词条

奎因-麦克拉斯基算法Quine-McCluskey算法)是最小化布尔函式的一种方法。

基本介绍

  • 中文名:奎因-麦克拉斯基算法
  • 外文名:Quine-McCluskey算法

简介

它在功能上等同于卡诺图,但是它具有文字表格的形式,因此它更适合用于电子设计自动化算法的实现,并且它还给出了检查布尔函式是否达到了最小化形式的确定性方法。
方法涉及两步:
  1. 找到这个函式的所有素蕴涵项。
  2. 使用这些素蕴涵项(prime implicant)来找到这个函式的本质素蕴涵项(essential prime implicant),对覆盖这个函式是必须的其他素蕴涵项也同样要使用。

複杂度

儘管在处理多于四个变数的时候比卡诺图更加实用,奎因-麦克拉斯基算法也有使用限制,因为它解决的问题是NP-困难的:奎因-麦克拉斯基算法的运行时间随输入大小而呈指数增长。可以证明对于n个变数的函式,素蕴涵项的数目的上界是3/n。如果n= 32,则可能超过6.1 * 10,或617万亿个素蕴涵项。有大量变数的函式必须使用潜在的非最优的启发式方法来最小化。

例子

最小化一个任意的函式:
ABCDf
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方法。在当前这个例子中,本质素蕴涵项不能处理所有的极小项,你可以组合这两个本质素蕴涵项与两个非素蕴涵项中的一个而生成:
最终的等式在功能上等价于最初的(冗长)等式:

转载请注明出处海之美文 » 奎因-麦克拉斯基算法

相关推荐

    声明:此文信息来源于网络,登载此文只为提供信息参考,并不用于任何商业目的。如有侵权,请及时联系我们:ailianmeng11@163.com