[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Identifying Untestable Faults in Sequential Circuits Using Test Path Constraints

  • Published:
Journal of Electronic Testing Aims and scope Submit manuscript

Abstract

The paper proposes a hierarchical untestable stuck-at fault identification method for non-scan synchronous sequential circuits. The method is based on deriving, minimizing and solving test path constraints for modules embedded into Register-Transfer Level (RTL) designs. First, an RTL test pattern generator is applied in order to extract the set of all possible test path constraints for a module under test. Then, the constraints are minimized using an SMT solver Z3 and a logic minimization tool ESPRESSO. Finally, a constraint-driven deterministic test pattern generator is run providing hierarchical test generation and untestability proof in sequential circuits. We show by experiments that the method is capable of quickly proving a large number of untestable faults obtaining higher fault efficiency than achievable by a state-of-the-art commercial ATPG. As a side effect, our study shows that traditional bottom-up test generation based on symbolic test environment generation at RTL is too optimistic due to the fact that propagation constraints are ignored.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Agrawal VD, Chakradhar ST (1995) Combinational ATPG theorems for identifying untestable faults in sequential circuits. IEEE Trans Comput Aided Des 14(9):1155–1160

    Article  Google Scholar 

  2. Brayton RK, Hachtel GD, McMullen CT, Sangiovanni-Vincentelli AL (1984) Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston

  3. Chayakul V, Gajski DD, Ramachandran L (1993) High-Level Transformations for Minimizing Syntactic Variances, DAC (Proceedings of the Design Automation Conference), Dallas, Texas, USA, p 413–418

  4. De Moura L, Bjørner N (2008) Z3: An Efficient SMT Solver. TACAS (International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)), Budapest, Hungary, p 337–340

  5. Dillig I, Dillig T, Aiken A (2010) Small Formulas for Large Programs, Proc. of the 17th intl. conf. on Static Analysis, Springer-Verlag, Berlin, Heidelberg, p 236–252

  6. Fujiwara H, Ooi CY, Shimizu Y (2008) Enhancement of Test Environment Generation for Assignment Decision Diagrams, 9th IEEE Workshop on RTL and High Level Testing, Nov. IEEE, Sapporo, Japan, 45–50

  7. Ghosh I, Fujita M (2000) Automatic test pattern generation for functional RTL circuits using assignment decision diagrams, Proc. DAC (Proceedings of the Design Automation Conference), Los Angeles, California, USA, p 43–48

  8. HLSynth92 benchmarks. http://ftp.ics.uci.edu/pub/hlsynth/HLSynth92

  9. ITC benchmarks. http://www.cerc.utexas.edu/itc99-benchmarks/bench.html

  10. Iyer MA, Long DE, Abramovici M (1996) Identifying sequential redundancies without search. In: Proc. 33rd Annu. Conf. DAC, LasVegas, pp 457–462

    Google Scholar 

  11. Jervan G et al (2002) High-Level and Hierarchical Test Sequence Generation. IEEE HLDVT, Cannes, 169–174

    Google Scholar 

  12. Lee J, Patel JH (1994 Oct) Architectural level test generation for microprocessors, IEEE Trans. CAD (IEEE Transactions on CAD of Integrated Circuits and Systems), Piscataway, New Jersey, USA, p 1288–1300

  13. Liang H-C, Lee CL, Chen EJ (1995) Identifying untestable faults in sequential circuits. IEEE Des Test Comput 12(3):14–23

    Article  Google Scholar 

  14. Long DE, Iyer MA, Abramovici M (2000) FILL and FUNI: Algorithms to identify illegal states and sequentially untestable faults. ACM Trans Des Autom Electron Syst 5(3):631–657

    Article  Google Scholar 

  15. Murray BT, Hayes JP (1988) Hierarchical test generation using precomputed tests for modules, Proc. ITC (Proceedings of the International Test Conference), Washington, D.C., USA, p 221–229

  16. Peng Q, Abramovici M, Savir J (2000) MUST: multiple stem analysis for identifying sequential untestable faults. In: Proc. Int. Test Conf. IEEE, Atlantic City, NJ, USA, p 839–846

  17. Raik J, Fujiwara H, Ubar R, Krivenko A (2008) Untestable fault identification in sequential circuits using model-checking. ATS (Proceedings of the Asian Test Symposium), Sapporo, Japan, p 667–672

  18. Raik J, Rannaste A, Jenihhin M, Viilukas T, Ubar R, Fujiwara H (2011) Constraint-Based Hierarchical Untestability Identification for Synchronous Sequential Circuits, Proc. of the European Test Symposium, IEEE Computer Society, Trondheim, Norway, p 147–152

  19. Raik J, Ubar R (1999) Sequential Circuit Test Generation Using Decision Diagram Models, Proceedings of the DATE Conference, IEEE Computer Society, Munich, Germany, p 736–740

  20. The ECLiPSe Constraint Programming System http://eclipseclp.org/

  21. Vedula V, Abraham J (2002) FACTOR: A Hierarchical Methodology for Functional Test Generation and Testability Analysis, DATE Conf., IEEE Computer Society, Paris, France, p 730–734

  22. Viilukas T, Raik J, Jenihhin M, Ubar R, Krivenko A (2010) Constraint-based test pattern generation at the register-transfer level, 13th IEEE DDECS Symposium, IEEE Computer Society, Vienna, Austria, p 352–357

  23. Zhang L, Ghosh I, Hsiao M (2003) Efficient Sequential ATPG for Functional RTL Circuits, Int. Test Conf., IEEE, Charlotte, NC, USA, p 290–298

Download references

Acknowledgments

The work has been supported by European Commission Framework Program 7 project FP7-ICT-2009-4-248613 DIAMOND, by Research Centre CEBE funded by European Union through the European Structural Funds and by Estonian Science Foundation grants 9429 and 8478.

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Tallinn University of Technology, Raja 15, Tallinn, 12618, Estonia

    Taavi Viilukas, Anton Karputkin, Jaan Raik, Maksim Jenihhin & Raimund Ubar

  2. Faculty of Informatics, Osaka Gakuin University, Suita, Osaka, 564-8511, Japan

    Hideo Fujiwara

Authors
  1. Taavi Viilukas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anton Karputkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jaan Raik
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Maksim Jenihhin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Raimund Ubar
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Hideo Fujiwara
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaan Raik.

Additional information

Responsible Editor: C. Metra

Rights and permissions

Reprints and permissions

About this article

Cite this article

Viilukas, T., Karputkin, A., Raik, J. et al. Identifying Untestable Faults in Sequential Circuits Using Test Path Constraints. J Electron Test 28, 511–521 (2012). https://doi.org/10.1007/s10836-012-5312-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10836-012-5312-5

Keywords

Search

Navigation