Perturb and simplify: optimizing circuits with external don´t cares

Earlier optimization techniques based on Automatic Test Pattern Generation could not handle external don´t cares. We propose a technique that uses external don´t cares during the ATPG guided logic optimization. This technique transforms external don´t cares into internal don´t cares. Thus, the optimization can utilize the external don´t cares to obtain better results. Additionally, we also discuss some perturbation techniques to improve further results of logic optimizers. Based on a careful analysis of don´t cares migration during incremental changes of an optimized circuit, we have developed a strategy to guide optimization. We have performed experiments on MCNC and ISCAS benchmarks and the results are very encouraging.