A synthesis-based test generation and compaction algorithm for multifaults

Srinivas Devadas, Kurt Keutzer, Sharad Malik

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Because of its inherent complexity, the problem of automatic test pattern generation for multiple stuck-at faults (multifaults) has been largely ignored. Recently, the observation that multifault testability is retained by algebraic factorization demonstrated that single fault (and therefore multifault) vector sets for two-level circuits could give complete multifault coverage for multilevel circuits constructed by algebraic factorization. Unfortunately, in using this method the vector set size can be much larger than what is really required to achieve multifault coverage, and the approach has some limitations in its applicability. In this article we first present a multifault test generation and compaction strategy for algebraically factored multilevel circuits, synthesized from two-level representations. We give a basic sufficiency condition for multifault testability of such networks. We next focus on the relationship between hazard-free robust path-delay-fault testability and multifault testability. We show that the former implies the latter for arbitrary multilevel circuits. This allows the use of previously developed composition rules that maintain path-delay-fault testability for the synthesis of multifault testable circuits. We identify a class of multiplexor-based networks and prove an interesting property of such networks-if the networks are fully single stuck-at fault testable, or made fully single stuck-at fault testable, they are completely multifault testable. We give a multifault test generation and compaction algorithm for such networks. We provide experimental results which indicate that a compacted multifault test set derived using the above strategies can be significantly smaller than the test set derived using previously proposed procedures. These results also indicate the substantially wider applicability of our procedures, as compared to previous techniques.

Original languageEnglish (US)
Pages (from-to)91-104
Number of pages14
JournalJournal of Electronic Testing
Issue number1
StatePublished - Feb 1 1993

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'A synthesis-based test generation and compaction algorithm for multifaults'. Together they form a unique fingerprint.

Cite this