一些逻辑简化算法已经发展了好几年,并且很多种已经合并到了基于计算机的逻辑简化程序中。类似这样的程序,比如基于Quine-McCluskey算法,就是利用穷举所有可能性来找到最终的最简化表达式。基于穷举查找算法的程序需要很长的执行时间,尤其是处理大量的输入输出。其它的程序,由UC Berkeley开发的并广泛使用的Espresso程序,就是使用启发式(或是基于规则)方法来代替穷举查找。尽管这类程序运行的会快一点(尤其对于中等或大型系统),但他们最终找到的的所谓“很棒”的方案并不是最简化表达式。在很多现实世界工程实践中,最好的情况就是能快速找出相当简化的方案。
Espresso是目前为止使用最为广泛的简化算法,其次是Quine-McCluskey算法。我们将主要介绍这两种算法,但不详细解释。网站上有很多好的参考资料解释了这两种算法是如何工作-我们鼓励你去阅读这些参考资料,这样你对最简化技术会有更好的理解。
Quine-McCluskey逻辑简化算法发展于二十世纪50年代中期,它也是第一个基于计算机的算法,并能够正确的找到最简化逻辑表达式。算法通过穷举的方法找出所有可能的1的分组,然后根据这所有的情况来找出最小的集合并覆盖原来所有最小项的集合(该集合就和输出有效时的所有最小项集合)。由于该算法会找出所有的方案,并选择最好的一个,所以它会消耗大量的计算时间。事实上,即使在现代计算机上,对于一个中等类型的逻辑系统,它也会算上几分钟甚至几个小时。有很多免费的程序可以用Q-M算法同时计算出最简化等式或多个等式。
Espresso发展于二十世纪60年代,并且已经发展成为工业中使用最广泛的逻辑简化程序。Espresso是严格的“基于规则”,这就意味着它不会查找出所有可能的简化方案(尽管很多情况下,它都能找到最简化表示式)。在espresso运行之前,先要创建一个espresso输入文件。这个输入文件实际上就是非简化表达式的所有最小项的列表。Espresso运行结束后会返回一个输出文件,并列出了所有输出表达式需要的项。Espresso可以简化多变量的单一逻辑功能,也可以简化多变量的大量逻辑功能。Espresso会对一个逻辑系统做一些单一化假设,所以它运行的非常快,甚至是大型系统也非常快。
Digimin是一款窗口界面软件,能够让Boozer和Espresso程序运行在Windows环境下。Digimin也提供了简单的真值表输入机制,并能够以SOP和POS等式的形式给出输出。Digimin,很多经典网站都能下载使用,使用简单直观,运行也方便。首先增加功能(选择Action->Add function),然后向该功能增加变量(选择Action->add variables)。当所有的功能和变量都添加完毕,只要再选择MIN功能以及Espresso或Boozer算法就可以了。
从二十世纪 90年代开始,硬件描述语言(HDLs)以及其相关设计工具与设计方法已经逐渐取代了其他数字电路设计的方法。今天,使用HDLs来抽象设计数字电路已经成为了业界的标准。在后面的章节中,我们将介绍HDLs。同样我们可以看到,使用HDL语言环境来定义电路可以在具体搭建电路之前简化电路。这一特性使得设计师可以把精力集中在研究电路行为上,而不用在查找高效率电路结构的细节上花费时间和精力。尽管理解数字电路的结构和功能很重要,但经验已经表明,设计师只要描述了电路的行为特性,并依靠基于计算机的工具就可以极快的找出高效率电路结构,并使之能够执行所有的行为特性。