Circuit structure relations to redundancy and delay

The existence of redundant stuck-faults in a logic circuit is potentially detrimental to high-speed operation, especially when there are false paths that are longer than the circuit delay. Keutzer, Malik, and Saldanha (KMS) in IEEE transactions of Computer Aided Design, vol. 10, no. 4, p. 427, April 1991 have proved that redundancy is not necessary to reduce delay by presenting an algorithm that derives an equivalent irredundant circuit from a given redundant circuit, with no increase in delay. The KMS algorithm consists of an iterative loop of timing analysis, gate duplications, and redundancy removal to successively eliminate long false paths. In this paper we resolve the main bottlenecks of the KMS algorithm by providing an efficient single-pass algorithm to simultaneously remove all long false paths from a given circuit. We achieve this by relating a circuit structure property based on path lengths to the testability (redundancy) and delay. The application of this algorithm to a variety of related logic synthesis problems is described