On finding the minimum test set of a BDD-based circuit

ABSTRACT

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 = 2k, 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.

REFERENCES

• 1: Akers, S. B. Binary decision diagrams. IEEE Trans. Computers, C-27(6), 1978, 509--516.
• 2: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 3: Wolfgang Günther , Rolf Drechsler, ACTion: combining logic synthesis and technology mapping for MUX-based FPGAs, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.14, p.1321-1334, Dec. 2000 [doi>10.1016/S1383-7621(00)00027-8 ]
• 4: Drechsler, R., Shi, J., and Fey, G. Synthesis of Fully Testable Circuits From BDDs. IEEE Trans. CAD, 23(3), 2004, 440--443.
• 5: Ebendt, R., Fey, G., and Drechsler, R. Advanced BDD Optimization. Springer Verlag, Berlin, 2000.
• 6: Hochbaum, D. Graph Algorithms and Network Flows. IEOR 266 Notes, UC Berkeley, 2003.
• 7: RELAX-IV: A Faster Version of the RELAX Code for Solving Minimum Cost Flow Problems (Bertsekas, D.P., and Tseng, P.), Rutgers U.
• 8: Somenzi, F., CUDD: CU Decision Diagram Package. http://bessie.colorado.edu/~fabio/ CUDD.
• 9: Abramovici, M., Breuer, M. A., and Friedman, A. D. Digital System Testing and Testable Design. Computer Science Press, New York, 1990.
• 10: Dilworth, R. P. A decomposition theorem for partially ordered sets. Ann. Math. 51, 1950, 161--166.
• 11: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 12: Dimitrios Kagaris , Spyros Tragoudas, Maximum independent sets on transitive graphs and their applications in testing and CAD, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.736-740, November 09-13, 1997, San Jose, California, United States
• 13: Picard, J. C. Maximal closure of a graph and applications to combinatorial problems. Management Science, 22, 1976, 1268--1272.
• 14: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 15: Yang, S. Logic Synthesis and Optimization Benchmarks User Guide. Tech. Rep., MCNC, 1991.
• 16: Sentovich, E., et al. SIS: A System for Sequential Circuit Synthesis. Tech. Rep., Univ. Calif., Berkeley, CA, 1992.
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Maitrali Marik , Ajit Pal, Energy-aware Logic Synthesis and Technology Mapping for MUX-based FPGAs, Proceedings of the 17th International Conference on VLSI Design, p.73, January 05-09, 2004
• 19: Harary, F. Graph Theory. Addison Wesley, 1973.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.3 Reliability and Testing**

General Terms:
Algorithms, Reliability

Keywords:
VLSI testing, binary decision diagram (BDD), multiplexors, network flow, stuck-at faults