research-article

Exact Logic and Fault Simulation in Presence of Unknowns

Authors:

Michael A. Kochte,

Matthias Sauer,

Stefan Hillebrecht,

Tobias Schubert,

Hans-Joachim Wunderlich,

Bernd BeckerAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 19, Issue 3

Article No.: 28, Pages 1 - 17

https://doi.org/10.1145/2611760

Published: 23 June 2014 Publication History

Abstract

Logic and fault simulation are essential techniques in electronic design automation. The accuracy of standard simulation algorithms is compromised by unknown or X-values. This results in a pessimistic overestimation of X-valued signals in the circuit and a pessimistic underestimation of fault coverage.

This work proposes efficient algorithms for combinational and sequential logic as well as for stuck-at and transition-delay fault simulation that are free of any simulation pessimism in presence of unknowns. The SAT-based algorithms exactly classifiy all signal states. During fault simulation, each fault is accurately classified as either undetected, definitely detected, or possibly detected.

The pessimism with respect to unknowns present in classic algorithms is thoroughly investigated in the experimental results on benchmark circuits. The applicability of the proposed algorithms is demonstrated on larger industrial circuits. The results show that, by accurate analysis, the number of detected faults can be significantly increased without increasing the test-set size.

References

[1]

K. J. Antreich and M. H. Schulz. 1987. Accelerated fault simulation and fault grading in combinational circuits. IEEE Trans. CAD Integr. Circ. Syst. 6, 5, 704--712.

Digital Library

[2]

B. Becker, M. Keim, and R. Krieger. 1999. Hybrid fault simulation for synchronous sequential circuits. J. Electron. Test. Theory Appl. 15, 3, 219--238.

Digital Library

[3]

R. E. Bryant. 1986. Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35, 8, 677--691.

Digital Library

[4]

J. L. Carter, B. K. Rosen, G. L. Smith, and V. Pitchumani. 1989. Restricted symbolic evaluation is fast and useful. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD'89). 38--41.

[5]

H. P. Chang and J. A. Abraham. 1987. The complexity of accurate logic simulation. In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD'87). 404--407.

[6]

H. Chou, K. Chang, and S. Kuo. 2010. Accurately handle don't-care conditions in high-level designs and application for reducing initialized registers. IEEE Trans. CAD Integr. Circ. Syst. 29, 4, 646--651.

Digital Library

[7]

S. Hillebrecht, M. A. Kochte, H.-J. Wunderlich, and B. Becker. 2012. Exact stuck-at fault classification in presence of unknowns. In Proceedings of the 17^th IEEE European Test Symposium (ETS'12). 98--103.

[8]

A. Jain, V. Boppana, R. Mukherjee, J. Jain, M. Fujita, and M. Hsiao. 2000. Testing, verification, and diagnosis in the presence of unknowns. In Proceedings of the IEEE VLSI Test Symposium (VTS'00). 263--268.

Digital Library

[9]

S. Kajihara, K. Saluja, and S. M. Reddy. 2004. Enhanced 3-valued logic/fault simulation for full scan circuits using implicit logic values. In Proceeding of the IEEE European Test Symposium (ETS'04). 108--113.

Digital Library

[10]

S. Kang and S. A. Szygenda. 2003. Accurate logic simulation by overcoming the unknown value propagation problem. Simul. 79, 2, 59--68.

[11]

M. Keim, B. Becker, and B. Stenner. 1996. On the (non-) resetability of synchronous sequential circuits. In Proceedings of the IEEE VLSI Test Symposium (VTS'96). 240--245.

Digital Library

[12]

M. A. Kochte, S. Kundu, K. Miyase, X. Wen, and H.-J. Wunderlich. 2011. Efficient bdd-based fault simulation in presence of unknown values. In Proceedings of the 20^th IEEE Asian Test Symposium (ATS'11). IEEE Computer Society, 383--388.

Digital Library

[13]

M. A. Kochte and H.-J. Wunderlich. 2011. SAT-based fault coverage evaluation in the presence of unknown values. In Proceedings of the Design, Automation and Test in Europe Conference (DATE'11). IEEE Computer Society, 1--6.

[14]

S. Kundu, I. Nair, L. Huisman, and V. Iyengar. 1991. Symbolic implication in test generation. In Proceedings of the Conference on European Design Automation (DATE'91). IEEE Computer Society Press, 492--496.

Digital Library

[15]

H. K. Lee and D. S. Ha. 1991. An efficient, forward fault simulation algorithm based on the parallel pattern single fault propagation. In Proceedings of the International Test Conference (ITC'91). IEEE Computer Society, 946--955.

Digital Library

[16]

S. Mitra and K. S. Kim. 2004. X-compact: An efficient response compaction technique. IEEE Trans. CAD Integr. Circ. Syst. 23, 3, 421--432.

Digital Library

[17]

M. Naruse, I. Pomeranz, S. M. Reddy, and S. Kundu. 2003. On-chip compression of output responses with unknown values using lfsr reseeding. In Proceedings of the IEEE International Test Conference (ITC'03). IEEE Computer Society, 1060--1068.

[18]

A. Ramdas and O. Sinanoglu. 2012. Toggle-masking scheme for x-filtering. In Proceedings of the IEEE European Test Symposium (ETS'12). IEEE Computer Society, 1--6.

[19]

E. M. Rudnick, J. H. Patel, and I. Pomeranz. 1996. On potential fault detection in sequential circuits. In Proceedings of the IEEE International Test Conference (ITC'96). IEEE Computer Society, 142--149.

Digital Library

[20]

J. Savir, and S. Patil. 1993. Scan-based transition test. IEEE Trans. CAD Integr. Circ. Syst. 12, 8, 1232--1241.

Digital Library

[21]

J. Savir and S. Patil. 1994. On broad-side delay test. In Proceedings of the IEEE VLSI Test Symposium (VTS'94). 284--290.

Digital Library

[22]

C. Scholl and B. Becker. 2001. Checking equivalence for partial implementations. In Proceedings of the Design Automation Conference (DAC'01). ACM Press, New York, 238--243.

Digital Library

[23]

T. Schubert, M. Lewis, and B. Becker. 2010. Antom—Solver description. SAT race. http://baldur.iti.uka.de/sat-race-2010/descriptions/solver_12.pdf.

[24]

Y. Tang, H. J. Wunderlich, P. Engelke, I. Polian, B. Becker, J. Schloffel, F. Hapke, and M. Wittke. 2006. X-masking during logic bist and its impact on defect coverage. IEEE Trans. VLSI Syst. 14, 2, 193--202.

Digital Library

[25]

G. S. Tseitin. 1968. On the complexity of derivation in propositional calculus. http://www.decision-procedures.org/handouts/Tseitin70.pdf.

[26]

M. Turpin. 2003. The dangers of living with an x (bugs hidden in your verilog). http://www.arm.com/files/pdf/Verilog_X_Bugs.pdf.

[27]

E. G. Ulrich and T. Baker. 1988. The concurrent simulation of nearly identical digital networks. In Papers on Twenty-Five years of Electronic Design Automation (25 years of DAC). ACM Press, New York, 318--323.

Digital Library

[28]

J. A. Waicukauski, E. B. Eichelberger, D. O. Forlenza, E. Lindbloom, and T. Mccarthy. 1985. Fault simulation for structured VLSI. VLSI Syst. Des. 6, 12, 20--32.

[29]

C. Wilson, D. Dill, and R. Bryant. 2000. Symbolic simulation with approximate values. In Proceedings of the 3^rd International Conference on Formal Methods in Computer-Aided Design. W. Hunt and S. Johnson, Eds., Lecture Notes in Computer Science, vol. 1954, Springer, 507--522.

Digital Library

[30]

P. Wohl, J. A. Waicukauski, and F. Neuveux. 2008. Increasing scan compression by using x-chains. In Proceedings of the IEEE International Test Conference (ITC'08). IEEE Computer Society, 1--10.

Cited By

Holst SKampmann MSprenger AReimer JHellebrand SWunderlich HWen X(2020)Logic Fault Diagnosis of Hidden Delay Defects2020 IEEE International Test Conference (ITC)10.1109/ITC44778.2020.9325234(1-10)Online publication date: 1-Nov-2020
https://doi.org/10.1109/ITC44778.2020.9325234
Pradhan MBhattacharya BChakrabarty KBhattacharya B(2019)Predicting ${X}$ -Sensitivity of Circuit-Inputs on Test-Coverage: A Machine-Learning ApproachIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816938:12(2343-2356)Online publication date: Dec-2019
https://doi.org/10.1109/TCAD.2018.2878169
Lin XReddy S(2019)On Generating Fault Diagnosis Patterns for Designs with X Sources2019 IEEE European Test Symposium (ETS)10.1109/ETS.2019.8791510(1-6)Online publication date: May-2019
https://doi.org/10.1109/ETS.2019.8791510
Show More Cited By

Index Terms

Exact Logic and Fault Simulation in Presence of Unknowns
1. Hardware
  1. Hardware test
  2. Robustness
    1. Hardware reliability

Recommendations

Efficient BDD-based Fault Simulation in Presence of Unknown Values
ATS '11: Proceedings of the 2011 Asian Test Symposium

Unknown (X) values, originating from memories, clock domain boundaries or A/D interfaces, may compromise test signatures and fault coverage. Classical logic and fault simulation algorithms are pessimistic w.r.t. the propagation of X values in the ...
Improving accuracy in path delay fault coverage estimation
VLSID '96: Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication

A recently published method computes path delay fault coverage from the count of the number of path faults newly sensitized by a simulated vector pair. Such an estimate is pessimistic since several paths may share a set of lines. In this paper, we ...
Sequential circuit fault simulation using logic emulation

A fast fault simulation approach based on ordinary logic emulation is proposed. The circuit configured into our system that emulates the faulty circuit's behaviour is synthesized from the good circuit and the given fault list in a novel way. Fault ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 19, Issue 3

June 2014

257 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/2634048

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 23 June 2014

Accepted: 01 January 2014

Revised: 01 October 2013

Received: 01 May 2013

Published in TODAES Volume 19, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
482
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Holst SKampmann MSprenger AReimer JHellebrand SWunderlich HWen X(2020)Logic Fault Diagnosis of Hidden Delay Defects2020 IEEE International Test Conference (ITC)10.1109/ITC44778.2020.9325234(1-10)Online publication date: 1-Nov-2020
https://doi.org/10.1109/ITC44778.2020.9325234
Pradhan MBhattacharya BChakrabarty KBhattacharya B(2019)Predicting ${X}$ -Sensitivity of Circuit-Inputs on Test-Coverage: A Machine-Learning ApproachIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816938:12(2343-2356)Online publication date: Dec-2019
https://doi.org/10.1109/TCAD.2018.2878169
Lin XReddy S(2019)On Generating Fault Diagnosis Patterns for Designs with X Sources2019 IEEE European Test Symposium (ETS)10.1109/ETS.2019.8791510(1-6)Online publication date: May-2019
https://doi.org/10.1109/ETS.2019.8791510
Scheibler KErb DBecker BFanucci LTeich J(2016)Accurate CEGAR-based ATPG in presence of unknown values for large industrial designsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972032(972-977)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972032
Erb DScheibler KKochte MSauer MWunderlich HBecker B(2016)Mixed 01X-RSL-Encoding for fast and accurate ATPG with unknowns2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2016.7428101(749-754)Online publication date: Jan-2016
https://doi.org/10.1109/ASPDAC.2016.7428101
Erb DKochte MReimer SSauer MWunderlich HBecker B(2015)Accurate QBF-Based Test Pattern Generation in Presence of Unknown ValuesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.244031534:12(2025-2038)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1109/TCAD.2015.2440315
Scheibler KErb DBecker B(2015)Improving test pattern generation in presence of unknown values beyond restricted symbolic logic2015 20th IEEE European Test Symposium (ETS)10.1109/ETS.2015.7138738(1-6)Online publication date: May-2015
https://doi.org/10.1109/ETS.2015.7138738
Becker BSauer MScholl CWimmer R(2015)Modeling Unknown Values in Test and VerificationFormal Modeling and Verification of Cyber-Physical Systems10.1007/978-3-658-09994-7_5(122-150)Online publication date: 6-Jun-2015
https://doi.org/10.1007/978-3-658-09994-7_5
Scheibler KBecker BJobstmann B(2014)Using Interval Constraint Propagation for Pseudo-Boolean Constraint SolvingProceedings of the 14th Conference on Formal Methods in Computer-Aided Design10.5555/2682923.2682958(203-206)Online publication date: 21-Oct-2014
https://dl.acm.org/doi/10.5555/2682923.2682958
Erb DScheibler KKochte MSauer MWunderlich HBecker B(2014)Test pattern generation in presence of unknown values based on restricted symbolic logic2014 International Test Conference10.1109/TEST.2014.7035350(1-10)Online publication date: Oct-2014
https://doi.org/10.1109/TEST.2014.7035350
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents