计算机科学

首页 > 计算机科学

奎因-麦克拉斯基算法

2018-07-27 10:04:53     所属分类:算法

奎因-麦克拉斯基算法Quine-McCluskey算法)是最小化布尔函数的一种方法。它在功能上等同于卡诺图,但是它具有文字表格的形式,因此它更适合用于电子设计自动化算法的实现,并且它还给出了检查布尔函数是否达到了最小化形式的确定性方法。

方法涉及两步:

  1. 找到这个函数的所有素蕴涵项。
  2. 使用这些素蕴涵项(prime implicant)来找到这个函数的本质素蕴涵项(essential prime implicant),对覆盖这个函数是必须的其他素蕴涵项也同样要使用。

目录

  • 1 复杂度
  • 2 例子
    • 2.1 第一步找到素蕴涵项
    • 2.2 第二步找到本质素蕴涵项
  • 3 参见
  • 4 外部链接

复杂度

尽管在处理多于四个变量的时候比卡诺图更加实用,奎因-麦克拉斯基算法也有使用限制,因为它解决的问题是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
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338740.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


相关推荐
爱淘宝