A NEW METHOD BASED ON CUBE ALGEBRA FOR THE SIMPLIFICATION OF LOGIC FUNCTIONS

摘要

In this study an Off-set based direct-cover minimization method for single-output logic functions is proposed represented in a sum-of-products form. To find the sufficient set of prime implicants including the given On-cube with the existing direct-cover minimization methods, this cube is expanded for one coordinate at a time. The correctness of each expansion is controlled by the way in which the cube being expanded intersects with all of K < 2~n Off-cubes. If we take into consideration that the expanding of one cube has a polynomial complexity, then the total complexity of this approach can be expressed as O(n~p)O(2~n), that is, the product of polynomial and exponential complexities. To obtain the complete set of prime implicants including the given On-cube, the proposed method uses Off-cubes expanded by this On-cube. The complexity of this operation is approximately equivalent to the complexity of an intersection of one On-cube expanded by existing methods for one coordinate. Therefore, the complexity of the process of calculating of the complete set of prime implicants including given On-cube is reduced approximately to O(n~p) times. The method is tested on several different kinds of problems and on standard MCNC benchmarks, results of which are compared with ESPRESSO.