This paper presents a nonenumerative automatic test pattern generator for robustly testable path delay faults. In contrast to earlier work by I. Pomeranz, et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 1505-15, Dec. 1995), the pattern generator takes into consideration the conditions for robust propagation while sensitizing sets of paths. This increases the probability of testing them robustly with a single test. Novel algorithms are described which identify sets that contain many such potentially compatible paths. The number of detected faults is estimated using a simple and fast method. The approach compares favorably to that of Pomeranz et al. in both fault detection and time performance.

This paper presents a test pattern generator for path delay faults which generates a polynomial number of test patterns that target a large number of functionally sensitizable faults. The number of these faults may be exponential to the input site. Experimental results are presented on the ISCAS'85 benchmarks.

A recent method proposed that a lower bound on the number of path delay faults excited by a given test set can be computed using a set independent lines that form a cut. For each line in the cut a subcircuit consisting of all paths that contain the line is defined, and a lower bound to the number of excited path delay faults can be obtained by working on the respective subcircuits. A polynomial time algorithm is presented here for computing the maximum cardinality set of independent circuit lines. Experimental results show that the more the subcircuits the better the lower bound on the number of excited path delay faults is. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms, and results in more subcircuits than the previous one.

Nonenumerative path-delay fault coverage estimation for combinational circuits estimates the fault coverage of a given test set without explicit enumeration of all paths in the circuit. In a recent nonenumerative method, it was proposed that a set C of lines be located in the circuit so that the set forms a cut and no lines in the set belong to the same path. Each line in the cut defines a subcircuit consisting of all paths that contain the line. Fault coverage may be obtained by working on all the subcircuits without double-counting path-delay faults. The main result of this paper is a polynomial time algorithm for finding a maximum cardinality set C. Besides its theoretical importance, our extensive experimental results on the ISCAS'85 benchmarks show that the larger the set C (and the number of subcircuits), the better the fault coverage estimation. More subcircuits may be generated only in a heuristic manner. It was proposed to consider two or more line-disjoint cuts C/sub i/. We propose a technique where only one C/sub i/ must be a cut. This scheme is based on novel algorithms and results in more subcircuits than the previous one.

In this paper we present an efficient test pattern generator for robust path delay faults, which we call ATPD. Our CAD tool detects much faster more robust path delay faults than any other existing nonenumerative approach. ATPD generates patterns for a non necessarily polynomial number of path delay faults. The nature of the problem indicates that for a test generator to be efficient it must count nonenumeratively the additional delay paths detected by each generated pair of patterns. ATPD generates each pair of patterns and determines the number of paths covered in a novel way that combines these two phases effectively.

We consider the problem of selecting the proper implementation of each circuit module from a cell library to minimize the propagation delay along every path from any primary input to any primary output. An earlier problem definition, known as the general circuit implementation problem, assumes that each implementation has different delays on the input-output paths in the circuit, and that different implementations may have different areas. We primarily focus on the version of the problem, where no restrictions for the overall area of the circuit exist and therefore we ignore the module areas. We show that this problem is NP-hard even for directed acyclic graphs with two implementations per module, and we present a polynomial time algorithm for trees. We have developed heuristics for combinational and sequential circuits.