TY - JOUR

T1 - Polynomial Time Testability of Circuits Generated by Input Decomposition

AU - Lee, Gueesang

AU - Irwin, Mary Jane

AU - Owens, Robert Michael

N1 - Funding Information:
Manuscript received July 22, 1991; revised November 4, 1992. This work was supported in part by NSF Grant CDA-8914587, Research in Parallel Program Design and Architecture Synthesis.

PY - 1994/2

Y1 - 1994/2

N2 - Polynomial time testability of combinational circuits generated by input decomposition, especially those generated by the logic synthesis tool FACTOR, is considered. First, the complexity of the fault detection problem in this class of circuits is explored using a stuck-at fault model. An O(2K m) algorithm for detecting a single stuck-at fault is given that is faster than the O(16K m), previously reported best algorithm proposed by Fujiwara, where K is the number of inputs in a subcircuit and m the number of signal lines in the circuit. Efficient, polynomial time algorithms are described for generating a test set for all single stuck-at faults in the circuit. The basic strategy is to eliminate backtracks during line. justification by constructing tables or vector sets in each subcircuit, which makes the fault propagation procedure very simple and eventually results in an efficient test generation procedure. This presentation of efficient polynomial time test generation algorithms for FACTOR-generated circuits is important, since it shows that it is possible to synthesize circuits that are optimized for area and are polynomial time testable at the same time.

AB - Polynomial time testability of combinational circuits generated by input decomposition, especially those generated by the logic synthesis tool FACTOR, is considered. First, the complexity of the fault detection problem in this class of circuits is explored using a stuck-at fault model. An O(2K m) algorithm for detecting a single stuck-at fault is given that is faster than the O(16K m), previously reported best algorithm proposed by Fujiwara, where K is the number of inputs in a subcircuit and m the number of signal lines in the circuit. Efficient, polynomial time algorithms are described for generating a test set for all single stuck-at faults in the circuit. The basic strategy is to eliminate backtracks during line. justification by constructing tables or vector sets in each subcircuit, which makes the fault propagation procedure very simple and eventually results in an efficient test generation procedure. This presentation of efficient polynomial time test generation algorithms for FACTOR-generated circuits is important, since it shows that it is possible to synthesize circuits that are optimized for area and are polynomial time testable at the same time.

UR - http://www.scopus.com/inward/record.url?scp=0028380920&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028380920&partnerID=8YFLogxK

U2 - 10.1109/12.262124

DO - 10.1109/12.262124

M3 - Article

AN - SCOPUS:0028380920

SN - 0018-9340

VL - 43

SP - 201

EP - 210

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 2

ER -