Don't-Care Aware ESOP Extraction via Reduced Decomposition-Tree Exploration

Exclusive-OR Sum-of-Products expressions (ESOPs) are vital for circuit synthesis of arithmetic functions and emerging technologies. The state-of-the-art ESOP extraction methods are limited in their inefficient exhaustive exploration strategy, significant optimality loss in the divide-and-conquer process, and incapability of handling don’t-cares. This work overcomes these limitations by reduced decomposition exploration with a cost estimation and refinement strategy, generally applicable to incompletely specified functions. Experiments show up to 29× (average 12×) runtime and 28× (average 13×) memory-usage improvements with a quality close to the exact optimum obtained by exhaustive exploration for completely-specified functions, and substantial ESOP simplification with don’t-cares for incompletely-specified functions.