  Redundancy identification is an important step of the design flow that
typically follows logic synthesis and optimization. In addition to reducing
circuit area, power consumption, and delay, redundancy removal also improves
testability. All commercially available synthesis tools include a redundancy
removal engine which is often run multiple times on the same netlist during
optimization. This paper presents a fast heuristic algorithm for redundancy
removal in combinational circuits. Our idea is to provide a quick partial
solution which can be used for the intermediate redundancy removal runs instead
of exact ATPG or SAT-based approaches. The presented approach has a higher
implication power than the traditional heuristic algorithms, such as FIRE, e.g.
on average it removes 37% more redundancies than FIRE with no penalty in
runtime.

Data Structures and Algorithms