The paper presents a flexible and efficient approach to evaluating implications as well as deriving indirect implications in logic circuits. Evaluation and derivation of implications are essential in ATPG, equivalence checking, and netlist optimization. Contrary to other methods, the approach is based on a graph model of a circuit's clause description called implication graph. It combines both the flexibility of SAT-based techniques and high efficiency of structure based methods. As the proposed algorithms operate only on the implication graph, they are independent of the chosen logic. Evaluation of implications and computation of indirect implications are performed by simple and efficient graph algorithms. Experimental results for various applications relying on implication demonstrate the effectiveness of the approach.

Various satisfiability problems in combinational logic blocks as, for example, test pattern generation, verification, and netlist optimization, can be solved efficiently by exploiting the fundamental concepts of propagation and justification. Therefore, fault effect propagation gains further importance. For the first time, we provide the theoretical background for a single path oriented fault effect propagation considering both single and multiple path sensitization. We call this approach SPOP. Furthermore, we formulate necessary and sufficient sensitization conditions for SPOP. From these conditions the best suited algebra for propagation can be derived. Experimental results for stuck-at test pattern generation demonstrate that the new approach is orthogonal to D-frontier based methods. We achieve substantial improvements with respect to test pattern generation time and quality.

This paper presents an ecient approach to path delay fault simulation.We ac celerate fault simulation by more than one order of magnitude with a new speed u p t e chnique called path hashing.An intelligent path identi cation method allows to deal with circuits containing two orders of magnitude more p aths than state-of-the-art tools.Using these techniques larger circuits can be handled with a reasonable amount of time and memory.