奎因-麦克拉斯基算法

✍ dations ◷ 2025-02-24 04:40:23 #布尔代数,算法

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

相关

  • UNAIDS行政总监联合国艾滋病规划署(英语:Joint United Nations Programme on HIV and AIDS,缩写UNAIDS)是全球范围内组织、推广及协调世界艾滋病运动的机构。规划署旨在唤起全球对艾滋
  • 易性癖性别不安(英语:gender dysphoria),又称性别焦虑、性别不一致,旧称性别认同障碍(英语:gender identity disorder)或易性症,是一个人因为出生时的性别指定而遭受的痛苦。在这种情况下,性
  • Wiki标记语言Wiki标记语言(英语:Wiki markup language),亦称Wikitext语言、wiki代码,是一种轻量级标记语言,用于撰写Wiki网页,例如维基百科。它在HTML基础上进行简化,最终目的是由Wiki软件转换成
  • 世界主义世界主义(英语:Cosmopolitanism)是一种意识形态,可从正义概念的普世性出发,每一个世界公民都不受歧视地自我决定其发展。世界主义则是此世界因互相依存的网络交流的全球状态。世
  • 永和网溪别墅永和网溪别墅,又称网溪别墅,是一栋位于台湾新北市永和区博爱街上的私人宅第,该宅第落成于1919年(大正八年),永和地区首任镇长杨仲佐为首任屋主,后由其子画家杨三郎继承。杨氏开台始
  • 温切斯特坐标:51°03′48″N 1°18′31″W / 51.0632°N 1.3085°W / 51.0632; -1.3085温切斯特(英语:Winchester)是英国南部的一座的城市,位于英格兰东南部的汉普郡,在南唐斯国家公园的西
  • 诸暨诸暨市,为中国浙江省下辖县级市,由绍兴地级市代管。诸暨市经济发达,为全国最具竞争力的县市之一,其综合竞争力2010年位居浙江省第五位,全国百强县(市)第十三位,诸暨因盛产珍珠而号称
  • 佩尔城 (阿拉巴马州)佩尔城(英文:Pell City),是美国阿拉巴马州下属的一座城市。面积约为24.75平方英里(约合 64.1平方公里)。根据2010年美国人口普查,该市有人口12,695人,人口密度为512.93/平方英里(约合
  • 约翰·基特默约翰·基特默(英语:John Kittmer;1967年7月6日-),是一名英国外交官,现任英属印度洋领地专员及英属南极领地专员。基特默在西萨塞克斯郡库克菲尔德(英语:Cuckfield)出生,曾于1988年在剑
  • 北关东自动车道 */?)是日本高速公路(高规格干线道路),起于群马县高崎市高崎系统交流道,经由栃木县东北自动车道,终于茨城县常陆那珂市常陆那珂交流道。略称为北关东道(北関東道/きたかんとうどう