Multi-level Logic Optimization By Implication Analysis

Abstract

This paper proposes a new approach to multi-level logic optimization based on ATPG (Automatic Test Pattern Generation). Previous ATPG-based methods for logic minimization suffered from the limitation that they were quite restricted in the set of possible circuit transformations. We show that the ATPG-based method presented here allows (in principle) the transformation of a given combinational network C into an arbitrary, structurally different but functionally equivalent combinational network C'. Furthermore, powerful heuristics are presented in order to decide what network manipulations are promising for minimizing the circuit. By identifying indirect implications between signals in the circuit, transformations can be derived which are “good” candidates for the minimization of the circuit. In particular, it is shown that Recursive Learning can derive “good” Boolean divisors justifying the effort to attempt a Boolean division. For 9 out of 10 ISCAS-85 benchmark circuits our tool HANNIBAL obtains smaller circuits than the well-known synthesis system SIS.