用编码算法求本源蕴涵项并构成布尔函数的近似最小化表达式

USING AN ENCODING ALGORITHM TO FIND PRIME IMPLICANTS AND CONSTRUCT A NEAR MINIMAL TWO LEVEL EXPRESSION FOR A BOOLEAN FUNCTION

本文提出了一个有效的化简布尔函数的算法。本源蕴涵项是通过小项的编码运算获得的。使用该算法可得到一个函数的近似最小化解,其近似程度不低于Arevala和Bredson提由的算法(以下简称A-B法)。本算法的主要恃点是:1.运算速度快;2.运算时间随变量个数增加的速度明显低于现行各种算法。因此,尤其适用于大规模逻辑设计问题。

An efficient algorithm to simplify boolean functions is presented in thispaper.The PIS are found through the code operating of the minterms of a function,and consequently a near minimal sum-of-products expression of the function isformed.Experiments have shown that the algorithm is distinguished from other methodsin two characteristics.First the short time to solve a problem is taken.Second,whenincreasing the number of the variables,the operational time can increase at a low rate.Therefore,it is especialy suitable to the applications for large logic designs.