Functional test generation for synchronous sequential circuits

Abstract

In this work, we present a novel approach to generate functional test sequences for synchronous sequential non scan circuits. The method is applicable when the functional description of the circuit can be obtained in the cubical form or a Personality Matrix (PM). In most synthesis environments, such a description is already available. The faults are modeled as growth (G) and disappearance (D) faults in the cubical description of the irredundant combinational function of the finite state machine (FSM). Considering the combinational logic alone, test vectors for these faults are efficiently derived for the G and D faults in the single output minimized PM using a cube based method developed for programmable logic arrays (PLAs). It is shown that these tests cover 100% of stuck type faults in any irredundant two level implementation and in the multi level implementations of the combinational part obtained through testability preserving transformations, known as algebraic factorization. To derive tests for the sequential circuit, we represent it as an iterative array of the combinational logic whose PM is modified according to the fault. We give new PM based algorithms to obtain state justification and fault propagation sequences. Thus, the cube based algorithm is extended to obtain the entire test sequence. We show that a complete test set for G and D faults guarantees 100% stuck fault coverage in the multi level FSM synthesized using algebraic factorization. We provide a theoretical proof to show that the vectors derived for a complete G and D fault coverage will detect all the detectable stuck faults in the algebraically transformed multi level circuit. Experimental results using some of the MCNC synthesis benchmark circuits show that the functional test generation is up to 1699× faster than a gate level test generator targeting stuck faults in the multi level implementation. We have considered circuits whose functional description consisted of up to 228 flip flops and 86,717 G/D faults. The synthesized multi level circuits contained up to 3563 gates and 9051 stuck faults. For general circuits that are available in their multi level form, we extract the function in the form of a PM and generate the functional test vectors. Experimental results show that for most circuits, the stuck fault coverage of functional vectors is higher than that obtained by a gate level test generator targeting stuck faults in the original circuit. We show, with experimental results using some of the ISCAS89 benchmark circuits, that the stuck fault coverage with functional vectors can be improved by resynthesizing these circuits from the extracted PMs. Here, we have considered 18 circuits, with the largest circuit having 647 gates and 1506 stuck faults. For these circuits, experimental results show that the functional test generation is up to 1606× faster than a gate level test generator targeting stuck faults in the multi level implementation. Large circuits are partitioned as an interconnection of two level functional blocks, and tests are generated for the G and D faults. General combinational functions-for which either the sum of products extraction is computationally expensive or the number of product terms is very large-can be partitioned into moderately sized functional blocks. We present a cube based algorithm for functional test generation in an interconnected structure of two level functional blocks. Some partitioning techniques suitable for functional test generation are discussed. Experimental results on MCNC synthesis benchmark FSMs and some ISCAS89 sequential circuits show that our approach can efficiently obtain functional test sequences which give very high coverage of stuck faults in specific implementations. The method has the added attraction that the functional test sequences are implementation independent and can be obtained even when details of the specific implementation are unavailable. The cube based functional test generation algorithm is much faster than a structure based algorithm targeting stuck faults in a gate level circuit, due to a smaller search space and absence of backtrace and backtracking. It is hoped that the results of the present research will provide a significant advantage in the testing of large complex digital circuits.