Simplification of Single-Output Boolean Functions by Exact Direct Cover Algorithm Based on Cube Algebra

摘要

Due to the nature of the exact two-level Boolean functions minimization methods most of practical applications rely on heuristic ones that are generally realized by a three step cyclic algorithm. First, the algorithm selects an On-minterm and it generates the set of prime implicants for this On-minterm; second, it determinates the essential prime implicant from among the generated prime implicants; and third, it performs a covering operation. The goal of this study, if the determination of the essential prime implicant is impossible, postponed the selection of essential prime implicant for this On-minterm and save it for a status word. When a new essential prime implicant determined, retrieve the status word. The proposed minimization algorithm is tested on several different kinds of problems and on standard MCNC benchmarks results of which are compared with ESPRESSO. The results show that proposed algorithm obtains exact results and faster than ESPRESSO.