A TRANSITIVE CLOSURE ALGORITHM FOR TEST-GENERATION

We present a transitive closure based test generation algorithm. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. To compute the transitive closure, we start with an implication graph whose vertices are labeled as the true and false states of all signals. A directed edge (x, y) in this graph represents the controlling influence of the true state of signal x on the true state of signal y that are connected through a wire or a gate. Since the implication graph only includes local pairwise (or binary) relations, it is a partial representation of the netlist. Higher-order signal relationships are represented as additional ternary relations. The transitive closure of the implication graph contains global pairwise logical relationships among all signals. Some signal dependencies result in conflicts, and, hence, identify redundancies. Other dependencies like fixations, identifications, and exclusions are also determined from the transitive closure. Sensitization of physical and logical dominators, unique path sensitization, static and dynamic learning, and other techniques that are useful in determining necessary signal assignments are implicit in the process. A key feature of the algorithm is that dependencies derived from the transitive closure are used to reduce ternary relations to binary relations that in turn dynamically update the transitive closure. The signals are either determined from the transitive closure or are enumerated until the Boolean equation is satisfied. We present experimental results on the ISCAS 1985 and the combinational parts of ISCAS 1989 benchmark circuits demonstrating efficient test generation and redundancy identification. Results on four state-of-the-art production VLSI circuits are also reported.