An Efficient Algorithm for Generating Complete Test Sets for Combinational Logic Circuits

Stephen S. Yau, Yu Shan Tang

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


An algorithm for generating the complete test set of each stuck-at-0 (s-a-0) and stuck-at-1 (s-a-1) single fault in a combinational logic circuit is presented. The algorithm has been programmed to handle large circuits and is based on some properties of Boolean differences that make the generation of the complete test set very efficient. This algorithm can be modified so that it can be programmed on computers with small storage space. The modified algorithm can efficiently generate a subset of the complete test set of each of the faults under consideration. Some discussion is given to provide some insight into the relationship among undetectable faults, tests for detectable single faults, and circuit redundancies. Some ideas on the construction of test sets for detecting multiple faults based on Boolean differences are presented.

Original languageEnglish (US)
Pages (from-to)1245-1251
Number of pages7
JournalIEEE Transactions on Computers
Issue number11
StatePublished - Nov 1971
Externally publishedYes


  • Algorithms Boolean difference combinational logic circuits complete test sets redundancies single faults and multiple faults storage stuck-at-0 (s-a-0) and stuck-at-1 (s-a-1)
  • undetectable faults

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'An Efficient Algorithm for Generating Complete Test Sets for Combinational Logic Circuits'. Together they form a unique fingerprint.

Cite this