Fast Heuristic Area Optimization Algorithm for ESOP Circuits

A fast heuristic algorithm is proposed to reduce the time consumed by area optimization of exclusive-or sum-of-product（ESOP） circuits. The proposed algorithm uses multi-output cubes to represent product terms, it first obtains an initial ESOP cover by using pseudo Kronecker decision diagram based approach, and then iteratively applies heuristic local polarity conversion and local transformation to optimize ESOP. In order to improve the algorithm efficiency, heuristic local polarity conversion only attempts to change the polarity of one variable in cubes, and only accepts the changes that can reduce the area, it helps the algorithm to escape from local minima. Local transformation reduces the area by reshaping cubes with distance of one or two, and helps the algorithm to converge. Experimental results show that, the proposed algorithm can be applied to multi-output circuits with very large number of input variables. In comparison with MPRM circuits, ESOP circuits can reduce the area overhead. In comparison with other area optimization algorithms for ESOP circuits, the proposed algorithm can significantly improve the time efficiency.