CIRCUIT STRUCTURE RELATIONS TO REDUNDANCY AND DELAY

The existence of redundant stuck-faults in a logic circuit is potentia lly detrimental to high-speed operation, especially when there are fal se paths that are longer than the circuit delay [13], [10]. Keutzer, M alik, and Saldanha (KMS) [10] have proved that redundancy is not neces sary to reduce delay by presenting an algorithm that derives an equiva lent irredundant circuit from a given redundant circuit, with no incre ase in delay. The KMS algorithm consists of an iterative loop of timin g analysis, gate duplications, and redundancy removal to successively eliminate long false paths. In this paper we resolve the main bottlene cks of the KMS algorithm by providing an efficient single-pass algorit hm to simultaneously remove all long false paths from a given circuit. We achieve this by relating a circuit structure property based on pat h lengths to the testability (redundancy) and delay. The application o f this algorithm to a variety of related logic synthesis problems is d escribed.