TRANSITIVE CLOSURE BASED PROCESS FOR GENERATING TEST VECTORS FOR VLSI CIRCUIT

A process for generating a vector for testing a digital circuit for a given fault first creates a composite circuit including a fault-present version of the circuit and a fault-free version. An implication graph is developed for the composite circuit and its energy function is derived as a combination of binary and ternary terms. All signal states that are consistent with the circuit function minimize the energy function to zero value. The transitive closure is computed for the binary terms, and redundancies, contradictions, fixations, identification and exclusions are identified. By iteration of implication graphs and transitive closures together with arbitrarily assigned signal values all ternary terms of the energy function are converted to binary terms, after which transitive closure recomputes a set of literals that can be used to generate the desired test vector by a standard branch and bound procedure.