Exact Minimization of ESOP Expressions Based on Hierarchical Hypercube

To cope with the problem of minimization of exclusive-or sum-of-products(ESOP) expressions for large logic functions, a minimization method is proposed that finds an exact ESOP expression for an arbitrary completely specified function. The n-dimensional hierarchical hypercube(HHC) model is presented to represent logic functions, and a cube EXOR-based transformation diagram is introduced to obtain exact solutions, based on cube geometrical mapping of Exorlink operation. The method also uses a reduced covering function by mapping logic function into HHC model after cube grouping and variable permutation. Then an exact ESOP minimization algorithm based on HHC is obtained. Experimental results on MCNC benchmark circuits show that, in comparison with existing algorithms, the proposed method can be used to find a minimum ESOP expression of a given n-variable function in polynomial time.