on finding the minimum test set of a bdd-based circuit
The Binary Decision Diagram (BDD) is a powerful vehicle for large-scale functional specification and circuit design. In this paper, we consider the open problem of generating in polynomial time, the exact minimum set (T) of test vectors for detecting all single stuck-at faults in such a BDD-based circuit synthesized with multiplexors. It is shown that for a single-output circuit, T = 2 k , where k is the minimum number of paths that cover all the arcs of the BDD graph. The value of k , and consequently the test set T , can be readily determined by running the max-flow algorithm on a network derived from the BDD, followed by a simple graph traversal. This procedure not only generates the optimal test set in polynomial time, but also obviates the need of employing an ATPG (Automatic Test Pattern Generator) and a fault simulator. For multi-output circuits, the procedure requires slight enhancement.
binary decision diagram (bdd) stuck-at faults multiplexors network flow vlsi testing