Combinational Test Generation for Various Classes of Acyclic Sequential Circuits

It is known that the complexity of test generation for acyclic sequential circuits is similar to that of combinational ATPG. The general problem, however, requires time-frame expansion and multiple-fault detection and hence does not allow the use of available combinational ATPG programs. The first contribution of this paper is a combinational single-fault ATPG method for the most general acyclic circuit. Without inserting any real hardware, we create a "balanced" ATPG model of the circuit in which all reconverging paths have the same sequential depth. Some primary inputs are duplicated and each combinational ATPG vector for this model circuit is transformed into a test sequence. Although no time-frame expansion is used, a small set of faults still map onto multiple-faults. Those are identified and dealt with again by the single-fault ATPG. The results show at least an order of magnitude saving in the ATPG CPU time. The second contribution consists of new partial-scan algorithms to obtain three subclasses of acyclic circuits, namely, internally balanced, balanced, and strongly balanced, for a general acyclic circuit. Combinational ATPG methods for these subclasses are available in the literature. Results show that in many cases these require hardware overheads quite close to the full-scan.