Unsatisfiability based efficient design for testability solution for register-transfer level circuits

Loganathan Lingappan, Niraj K. Jha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


In this paper, we present a novel and accurate method for identifying design for testability (DFT) solutions for register-transfer level (RTL) circuits. In this technique, clauses are generated using a satisfiability (SAT) based automatic test pattern generation (ATPG) tool to represent the control and data flow for a module under test in the given RTL circuit. RTL test generation makes use of the concept of pre-computed test sets for different RTL modules. The generated clauses corresponding to different pre-computed test vectors are then resolved by a SAT solver to obtain the test sequences for that module. In case of an unsatisfiable (UNSAT) solution, recent advances in the field of satisfiability enable us to accurately and efficiently identify clauses that are responsible for unsatisfiability (also known as the unsatisfiable segment). We show that adding DFT elements is equivalent to modifying clauses such that the unsatisfiable segment becomes satisfiable. In order to minimize the number of DFT elements added to a circuit, a greedy algorithm is used to select circuit variables for DFT such that all the unsatisfiable segments become satisfiable. Unlike existing DFT techniques that are either inefficient in terms of the amount of test hardware added or take significant time to identify an efficient solution, the proposed DFT technique is both fast and accurate as it is applicable to RTL and mixed gate-level/RTL circuits and uses UNSAT to identify the DFT solutions. Experimental results on benchmarks show that for RTL circuits, the CPU time required to identify pre-computed test vectors for which the SAT ATPG fails to generate test sequences and to select DFT solutions for such cases is two orders of magnitude smaller than the time required for a single run of a gate-level sequential test generator. The DFT solution has very low area overhead (an average of 1.7%) and results in near-100% fault coverage.

Original languageEnglish (US)
Title of host publicationProceedings - 23rd IEEE VLSI Test Symposium, VTS 2005
Number of pages6
StatePublished - 2005
Event23rd IEEE VLSI Test Symposium, VTS 2005 - Palm Springs, CA, United States
Duration: May 1 2005May 5 2005

Publication series

NameProceedings of the IEEE VLSI Test Symposium


Other23rd IEEE VLSI Test Symposium, VTS 2005
Country/TerritoryUnited States
CityPalm Springs, CA

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Unsatisfiability based efficient design for testability solution for register-transfer level circuits'. Together they form a unique fingerprint.

Cite this