Test register insertion with minimum hardware cost

ABSTRACT

Implementing a built-in self-test by a "test per clock" scheme offers advantages concerning fault coverage, detection of delay faults, and test application time. Such a scheme is implemented by test registers, for instance BILBOs and CBILBOs, which are inserted into the circuit structure at appropriate places. An algorithm is presented which is able to find the cost optimal placement of test registers for nearly all the ISCAS'89 sequential benchmark circuits, and a suboptimal solution with slightly higher costs is obtained for all the circuits within a few minutes of computing time. The algorithm can also be applied to the Minimum Feedback Vertex Set problem in partial scan design, and an optimal solution is found for all the benchmark circuits. The resulting self-testable circuits are analyzed. It is found that often CBILBOs lead to a minimum hardware overhead and also simplify test scheduling and test control.

REFERENCES

• 1: LaNae J. Avra, Allocation and Assignment in High-Level Synthesis for Self-Testable Data Paths, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.463-472, October 26-30, 1991
• 2: F. Brglez, D. Bryan, K. Kozminski: "Combinational Profiles of Sequential Benchmark Circuits", Int. Syrup. on Circuits and Systems, 1989, pp. 1929-1934
• 3: K.-T. Cheng , V. D. Agrawal, A Partial Scan Method for Sequential Circuits with Feedback, IEEE Transactions on Computers, v.39 n.4, p.544-548, April 1990 [doi>10.1109/12.54847]
• 4: Srimat T. Chakradhar , Arun Balakrishnan , Vishwani D. Agrawal, An exact algorithm for selecting partial scan flip-flops, Proceedings of the 31st annual conference on Design automation, p.81-86, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196285]
• 5: Christos A. Papachristou , Scott Chiu , Haidar Harmanani, A data path synthesis method for self-testable designs, Proceedings of the 28th conference on ACM/IEEE design automation, p.378-384, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127698]
• 6: 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
• 7: R. Gupta , M. A. Breuer, The Ballast Methodology for Structured Partial Scan Design, IEEE Transactions on Computers, v.39 n.4, p.538-544, April 1990 [doi>10.1109/12.54846]
• 8: S. Das Gupta, R. G. Walther, E. B. Eichelberger, T. W. Williams: "An Enhancement to LSSD and Some Applications of LSSD in Reliability, Availability and Serviceability", FTCS, 1981, pp. 32-34
• 9: C.L. Hudson, G. D. Peterson: "Parallel Self-Test with Pseudo-Random Test Patterns", International Test Conference, Washington DC, 1987, pp. 954-963
• 10: B. Koenemann, J. Mucha, G. Zwiehoff: "Built-In Logic Block Observation Techniques", Test Conference, Cherry Hill NJ, 1979, pp. 37-41
• 11: A. Krasniewski, S. Pilarski: "Circular Self-Test Path: A Low Cost BIST Technique for VLSI Circuits", Transactions on CAD, Jan. 1989, pp. 46-55
• 12: A. Kunzmann , J. J. Wunderlich, An analytical approach to the partial scan problem, Journal of Electronic Testing: Theory and Applications, v.1 n.2, p.163-174, May 1990 [doi>10.1007/BF00137392]
• 13: Tien-Chien Lee , Niraj K. Jha , Wayne H. Wolf, Behavioral synthesis of highly testable data paths under the non-scan and partial scan environments, Proceedings of the 30th international conference on Design automation, p.292-297, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164897]
• 14: D.H. Lee, S. M. Reddy: "On Determining Scan Flip- Flops in Partial-Scan Designs", International Conference on CAD, 1990, pp. 322-325
• 15: A. Mujumdar, R. Jain, K. Saluja: "Behavioral Synthesis of Testable Designs", International Symposium on Fault-Tolerant Computing, 1994, pp. 436-445
• 16: M.J. Ohletz, T. W. Williams, J. P. Mucha: "Overhead in Scan and Self-Test Designs", International Test Conference, 1987, pp. 460-470
• 17: L.-T. Wang, E. J. McCluskey: "Concurrent Built-in Logic Block Observer (CBILBO)", Int. Symposium on Circuits and Systems, 1986, pp. 1054-1057
• 18: H.-J. Wunderlich: "Self Test Using Unequiprobable Random Patterns", FTCS, 1987, pp. 258-263

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Algorithms, Theory

Keywords:
Built-in self-test, test register insertion, BILBO, CBILBO