A Fast SOP Minimizer for Logic Funcions Described by Many Product Terms
Petr Fišer, David Toman · 2009
We introduce a fast and efficient minimization method for functions described by many (up to millions) product terms. The algorithm is based on processing a newly proposed efficient representation of a set of product terms a ternary tree. A significant speedup of the look-up of the term operation is achieved, with respect to a standard tabular function representation. The minimization procedure is based on a fast application of basic Boolean operations upon a ternary tree. Minimization of incompletely specified functions is supported as well. The minimization method was tested on randomly generated large sums-of-products and collapsed ISCAS benchmark circuits. The performance of the proposed algorithm was compared with Espresso. A very advantageous application of the new minimization algorithm has been found if it is used for pre-processing a function having a large number of product terms, run prior to Espresso, the total minimization runtime is significantly reduced, whereas the result quality is not affected.