奎因-麦克拉斯基算法

✍ dations ◷ 2025-04-26 23:03:30 #布尔代数,算法

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

方法涉及两步:

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

最小化一个任意的函数:

你能轻易的形成这个表的规范的积之和表达式,简单的通过总和这个函数求值为一的那些极小项(除掉那些不关心项):

当然,这的确不是最小化的。为了优化,所有求值为一的极小项都首先放到极小项表中,不关心项也可以加入这个表中与极小项组合:

现在你可以开始把极小项同其他极小项组合在一起。如果两个项只有一个二进制位的数值不同,则可以这个位的数值可以替代为一个横杠,来指示这个数字无关紧要。不再组合的项标记上 "*"。

没有项可以继续进一步这样组合,所以现在我们构造一个本质量蕴涵项表。纵向是刚才生成的素蕴涵项,横向是早先指定的极小项。

这里的每个本质素蕴涵项都标记了星号 - 第二个素蕴涵项能被第三个和第四个所覆盖,而第三个素蕴涵能被第二个和第一个所覆盖,因此都不是本质的。如果一个素蕴涵项是本质的,则同希望的一样,它必须包含在最小化的布尔等式中。在某些情况下,本质量蕴涵形不能覆盖所有的极小项,此时可采用额外的简约过程。最简单的“额外过程”是反复试验,而更系统的方式是Petrick方法。在当前这个例子中,本质量蕴涵项不能处理所有的极小项,你可以组合这两个本质量蕴涵项与两个非素蕴涵项中的一个而生成:

最终的等式在功能上等价于最初的(冗长)等式:

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

相关

  • 正书法正写法,即是文字符号形体的规范和使用规则,包括正字法和正词法。汉字正字法可依据《通用规范汉字表》、《简化字总表》、修订后的《第一批异体字整理表》、《现代汉语通用字表
  • 圣保罗学校世界上有多所学校名为圣保罗学校:圣保罗中学(伦敦)
  • 酸碱电离理论酸碱电离论是1884年由瑞典化学家斯凡特·阿伦尼乌斯提出的一种酸碱理论,该理论认为在水中解离出的正离子全是H+的化合物为酸;解离出的负离子全是OH−的化合物称为碱。该理论是
  • 奥斯卡最佳影片奥斯卡最佳影片奖(英语:Academy Award for Best Picture),由美国电影艺术与科学学院通过业内人士投票,颁给每年得票最高的电影,奥斯卡金像奖之一。此奖项起初被称为最佳作品奖(Best
  • 贝塞麦转炉炼钢法贝塞麦转炉炼钢法最早源于工业革命,是平炉炼钢法发明之前首个从生铁大规模生产钢的廉价工艺,以英国发明人亨利·贝塞麦的名字命名。贝塞麦1855年取得该工艺的专利。不过在1851
  • 玻璃虾玻璃虾科(Pasiphaeidae)是十足目玻璃虾总科(Pasiphaeoidea)下的唯一一个科,下含7属。该科的玻璃虾属、雕玻虾属、阿兰玻虾属、拟玻璃虾属、真玻璃虾属和脆肢虾属生物多生活在海下
  • 分离性遗忘症分离性遗忘症或游离性遗忘症(英语:Dissociative amnesia),又称为心因性失忆症(英语:Psychogenic amnesia),是一种心理疾病。患者会遗忘个人记忆中的重要资料,通常不是由生理因素(如脑
  • 詹姆斯·贝詹姆斯·麦可·贝(英语:James Michael Bay,1990年9月4日-)是一位英国创作型歌手及吉他手。他已发行了几张迷你专辑与一张专辑《喧嚣与寂静(英语:Chaos and the Calm)》。这张专辑曾
  • 因格马尔·特维尔因格马尔·特维尔(爱沙尼亚语:Ingemar Teever;1983年2月24日-)是一位爱沙尼亚足球运动员。在场上的位置是前锋。他现在效力于爱沙尼亚足球甲级联赛球队塔林利瓦迪亚足球俱乐部。
  • 安全室安全室是在私人住宅或商店中,为其中居民面对入室犯罪和其他威胁时,所提供一个安全藏身之处。安全室是经加固的房间,内部通常提供通讯器材,以便使用者可以和执法部门联络。最简单