奎因-麦克拉斯基算法

✍ dations ◷ 2025-10-26 07:17:46 #布尔代数,算法

奎因-麦克拉斯基算法(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\,}

相关

  • 西日耳曼语支西日耳曼语支是日耳曼语族中最大的一支,包括德语、英语,还包括荷语、南非语和弗里西语。日耳曼语族其他的分支尚有北日耳曼语支和东日耳曼语支。西日耳曼语支下面有各种分支语
  • 皇纪神武天皇即位纪元,又称日本皇纪或简称皇纪,是日本的纪年方式之一,以日本神话中的第一代天皇神武天皇的即位元年开始起算,比现行西历早660年。即西元2020年等于皇纪2680年,以此类
  • 奔奔石奔奔(Benben)是从太初水域升起的原始丘,在古埃及宗教赫里奥波里斯的创世神话中,原始丘是由雌雄同体混沌水神努恩(Nun)巨卵而生成的,然后诞生了亚图姆又衍生为九柱神团共同成为宇
  • 实学四配颜回 · 孟子 · 曾参 · 孔伋日本藤原惺窝 · 林罗山 · 室鸠巢新井白石 · 雨森芳洲朝鲜薛聪 · 权近 · 吉再 · 安珦 · 李穑李滉 · 王仁 · 李齐贤 
  • 襄城县襄城县是中华人民共和国河南省许昌市下辖的一个县。古称氾城。面积920平方公里,2010年人口83万。县政府驻城关镇烟城东路。2018年在中部六省各县中综合实力排第69位,有煤炭、
  • 戴安·弗西戴安·弗西(Dian Fossey,1932年1月16日-1985年12月27日)是一位研究山地大猩猩的美国动物学家,曾在卢旺达火山国家公园丛林中研究大猩猩种群18年。1983年她出版著作《迷雾中的大猩
  • 袴田里见袴田里见(1904年8月11日-1990年5月10日),日本社会运动家,原日本共产党副委员长,后成为反共主义者。出生在青森县上北郡下田村(今奥入濑町)。1919年从高等小学校毕业后,前往东京的攻玉
  • 2017年中国内地一周票房冠军2017年中国内地一周票房冠军为2017年中国内地一周内的电影票房冠军列表,列表将星期一到星期天视为一周。除特别注明外,均为《中国电影报》数据。
  • 克伦民主佛教军5旅 若开民族军 克伦民族联盟 缅甸缅甸内战克伦民主佛教军 - 5旅(缅甸语:ဒီမိုကရက်တစ်ကရင်အကျိုးပြုတပ်မတော် - တပ်မဟာ 5,英语:Democrat
  • 传奇世界《传奇世界》(英文名:The World Of Legend)是由盛趣信息技术(上海)有限公司(盛大网络控股)开发,盛大网络服务运营的一款奇幻动作类MMORPG 2D网络游戏,于2003年6月正式发布运营,7月28日