Identification of unsettable flip-flops for partial scan and faster ATPG

ABSTRACT

State justification is a time-consuming operation in test generation for sequential circuits. In this paper, we present a technique to rapidly identify state elements (hip-hops) that are either difficult to set or unsettable. This is achieved by performing test generation on certain transformed circuits to identify state elements that are not settable to specific logic values. Two applications that benefit from this identification are sequential circuit test generation and partial scan design. The knowledge of the state space is shown to be useful in creating early backtracks in deterministic test generation. Partial scan selection is also shown to benefit from the knowledge of the difficult-to-set hip-hops. Experiments on the ISCAS89 circuits are presented to show the reduction in time for test generation and the improvements in the testability of the resulting partial scan circuits.

REFERENCES

• 1: D. E. Long , M. A. Iyer , M. Abramovici, Identifying sequentially untestable faults using illegal states, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.4, April 30-May 03, 1995
• 2: Mahesh A. Iyer , Miron Abramovici, Sequentially Untestable Faults Identified Without Search ("Simple Implications Beat Exhaustive Search!"), Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.259-266, October 02-06, 1994
• 3: O. Coudert and J. C. Madre, "Symbolic Computation of the Valid States of a Sequential Machine: Algorithms and Discussion," in Proc. of the Intl. Workshop on Formal Methods in VLSI Design, Jan. 1991.
• 4: H. Touati, H. Savoj, B. Lin, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Implicit State Enumeration of Finite State Machines Using BDD's," in Proc. of the Intl. Conf. on Computer-Aided Design, pp. 130-133, Nov. 1990.
• 5: Carl Pixley, Introduction to a Computational Theory and Implementation of Sequential Hardware Equivalence, Proceedings of the 2nd International Workshop on Computer Aided Verification, p.54-64, June 18-21, 1990
• 6: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 7: K.-T. Cheng and H.-K. T. Ma, "On the Over-Specification Problem in Sequential ATPG Algorithms," IEEE Trans. on Computer Aided Design, vol. 12, pp. 1599-1604, Oct. 1993.
• 8: Thomas Niermann , Janak H. Patel, HITEC: a test generation package for sequential circuits, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 9: E. Trischler, "Incomplete Scan Path with an Automatic Test Generation Methodology," in Proc. of the Intl. Test Conf., pp. 153-162, Nov. 1980.
• 10: V. Chickermane and J. H. Patel, "An Optimization Based Approach to the Partial Scan Design Problem," in Proc. of the Intl. Test Conf., pp. 377-386, Sept. 1990.
• 11: Prashant S. Parikh , Miron Abramovici, Testability-based partial scan analysis, Journal of Electronic Testing: Theory and Applications, v.7 n.1-2, p.61-70, Aug./Oct. 1995 [doi>10.1007/BF00993314]
• 12: V. Chickermane and J. H. Patel, "A Fault Oriented Partial Scan Design Approach," in Proc. of the Intl. Conf. on Computer-Aided Design, pp. 400-403, Nov. 1991.
• 13: 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]
• 14: D. H. Lee and S. M. Reddy, "On Determining Scan Flipflops in Partial Scan Designs," in Proc. of the Intl. Conf. on Computer-Aided Design, pp. 322-325, Nov. 1990.
• 15: Srimat T. Chakradhar , Arun Balakrishnan , Vishwani D. Agrawal, An exact algorithm for selecting partial scan flip-flops, Journal of Electronic Testing: Theory and Applications, v.7 n.1-2, p.83-93, Aug./Oct. 1995 [doi>10.1007/BF00993316]
• 16: Tatiana Orenstein , Zvi Kohavi , Irith Pomeranz, An optimal algorithm for cycle breaking in directed graphs, Journal of Electronic Testing: Theory and Applications, v.7 n.1-2, p.71-81, Aug./Oct. 1995 [doi>10.1007/BF00993315]
• 17: H.K.T. Ma, S. Devadas, A. R. Newton, and A. Sangiovanni- Vincentelli, "An Incomplete Scan Design Approach to Test Generation for Sequential Machines," in Proc. of the Intl. Test Conf., pp. 730-734, Sept. 1988.
• 18: Elizabeth M. Rudnick , Janak H. Patel, Combining deterministic and genetic approaches for sequential circuit test generation, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.183-188, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217527]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**
          Subjects: Test generation**

General Terms:
Design, Experimentation, Reliability, Theory

Keywords:
ATPG, ISCAS89 circuits, deterministic test generation, difficult-to-set hip-hops, hip-hops, logic testing, partial scan, sequential circuits test generation, state elements, state justification, transformed circuits, unsettable flip-flops identification