Multi-level logic optimization by redundancy addition and removal

A multilevel logic optimization technique is presented that is a generalization of redundancy removal and Boolean resubstitution. The network is optimized through iterative addition and deletion of redundant connections. With the use of the connection fault model, the problem of identifying connections that can be made without affecting the network's functionality is converted into the problem of identifying redundant connection faults. Efficient test generation algorithms can thus be applied directly. Techniques that can efficiently locate redundant wires and/or nodes after adding a redundant wire are also proposed. Experiment results on MCNC benchmark circuits show that, on average, a 16% reduction in gate count and a 20% reduction in connection count can be achieved at a low computational cost. The suggested technique can also be applied for timing optimization.>