Fast Multilevel Logic Optimization using Local Transformations

Electronic Design Automation (EDA) tools
are widely used for logic synthesis,
equivalence checking, testing, and verification.
Data structures which are compact and enable
efficient boolean reasoning are important
for EDA tools. A data structure, proved to be
successful in many applications, is the
AND/INVERTER graph. This paper presents
a rule-based system that removes redundancies
in such a graph, minimizes its size and reduces
the number of locally reconvergent paths.
The system uses NPN classes of boolean functions
to identify replacement rules for performing
local transformations. The experimental results
of benchmark functions show that the system is
fast. Improvements to this rule-based system are considered.