Polynomial time testability of combinational circuits generated by inp
ut decomposition, especially those generated by the logic synthesis to
ol 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(2(K) m) algorithm for detecting a single stuck-at fault is
given that is faster than the O(16(K) m), previously reported best al
gorithm proposed by Fujiwara, where K is the number of inputs in a sub
circuit and m the number of signal lines in the circuit. Efficient, po
lynomial time algorithms are described for generating a test set for a
ll single stuck-at faults in the circuit. The basic strategy is to eli
minate backtracks during line justification by constructing tables or
vector sets in each subcircuit, which makes the fault propagation proc
edure very simple and eventually results in an efficient test generati
on procedure. This presentation of efficient polynomial time test gene
ration algorithms for FACTOR-generated circuits is important, since it
shows that it is possible to synthesize circuits that are optimized f
or area and are polynomial time testable at the same time.