A test methodology for finite state machines using partial scan design

This paper presents an efficient automatic test pattern generation technique for loop-free circuits. A partial scan technique is used to convert a sequential circuit (finite state machine) with arbitrary feedback paths into a pipelined circuit for testing. Test generation for these modified circuits can be performed with a modified combinational automatic test pattern generator (ATPG), which is much faster than a sequential ATPG. A combinational model is obtained by replacing all flipflops by buffers. It is shown that a test vector for a fault in this model obtained by a combinational test generator can be expanded into a sequence of identical vectors to detect the same fault in the original sequential circuit. This technique may abort a few faults which can then be resolved with a sequential ATPG. Experiments on the ISCAS89 circuits show that only 30% to 70% of flipflops require scanning in larger circuits and 96% to 100% fault coverage for almost all the circuits without resorting to a sequential ATPG.This research was sponsored by the Semiconductor Research Corporation, Contract 90-DP-142.     

Improving path delay testability of sequential circuits

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible     

Efficient sensitization of multi-bit-paths for testing embedded modules in synchronous sequential circuits

This article presents SPLASH, an algorithm that can sensitize several independent bitpaths simultaneously. SPLASH includes several new concepts and techniques aiming at a significant improvement and acceleration of the path sensitization for testing embedded modules in combinational and synchronous sequential circuits. The transparent paths are used to apply module test patterns through circuit inputs and observe the responses at circuit outputs. It consequently automates an important task of modular test generation, supplying a test pattern assembly program with a specification how to transform module test patterns into circuit level pattern.A number of experiments using combinational and sequential benchmark circuits as well as industrial designs demonstrate the efficiency of the approach.     

Design of testable sequential circuits by repositioning flip-flops

This paper presents a technique to enhance the testability of sequential circuits by repositioning flip-flops. A novel retiming for testability technique is proposed that reduces cycle lengths in the dependency graph, converts sequential redundancies into combinational redundancies, and yields retimed circuits that usually require fewer scan flip-flops to break all cycles (except self-loops) as compared to the original circuit. Our technique is based on a new minimum cost flow formulation that simultaneously considers the interactions among all strongly connected components (SCCs) of the circuit graph to minimize the number of flip-flops in the SCCs. A circuit graph has a vertex for every gate, primary input and primary output. If gatea has a fanout to gateb, then the circuit graph has an arc from vertexa to vertexb. Experimental results on several large sequential circuits demonstrate the effectiveness of the proposed retiming for testability technique in reducing the number of partial scan flip-flops.     

Testability and test generation for majority voting fault-tolerant circuits

The testability of majority voting based fault-tolerant circuits is investigated and sufficient conditions for constructing circuits that are testable for all single and multiple stuck-at faults are established. The testability conditions apply to both combinational and sequential logic circuits and result in testable majority voting based fault-tolerant circuits without additional testability circuitry. Alternatively, the testability conditions facilitate the application of structured design for testability and Built-In Self-Test techniques to fault-tolerant circuits in a systematic manner. The complexity of the fault-tolerant circuit, when compared to the original circuit can significantly increase test pattern generation time when using traditional automatic test pattern generation software. Therefore, two test pattern generation algorithms are developed for detecting all single and multiple stuck-at faults in majority voting based circuits designed to satisfy the testability conditions. The algorithms are based on hierarchical test pattern generation using test patterns for the original, non-fault-tolerant circuit and structural knowledge of the majority voting based design. Efficiency is demonstrated in terms of test pattern generation time and cardinality of the resulting set of test patterns when compared to traditional automatic test pattern generation software.     

Integration of hierarchical test generation with behavioralsynthesis of controller and data path circuits

This paper describes the first behavioral synthesis system that incorporates a hierarchical test generation approach to synthesize area-efficient and highly testable controller/data path circuits. Functional information of circuit modules is used during the synthesis process to facilitate complete and easy testability of the data path. The controller behavior is taken into account while targeting data path testability. No direct controllability of the controller outputs through scan or otherwise is assumed. The test set for the combined controller/data path is generated during synthesis in a very short time. Near 100% testability of combined controller and data path is achieved. The synthesis system easily handles large bit-width data path circuits with sequential loops and conditional branches in their behavioral specification, and scheduling constructs like multicycling, chaining and structural pipelining. An improvement of about three to four orders of magnitude was usually obtained in the test generation time for the synthesized benchmarks as compared to an efficient gate-level sequential test generator. The testability overheads are almost zero. Furthermore, in many cases at-speed testing is also possible     

An Asynchronous Design for Testability and Implementation in Thin-film Transistor Technology

This paper presents a scan chain design for dual-rail asynchronous circuits. This is a true asynchronous scan chain because no clock is needed even in scan mode. This is a full-scan design for testability (DfT) so only combinational automatic test pattern generation (ATPG) is needed and the fault coverage of generated test patterns is very high. This technique can be applied to various kinds of asynchronous circuits, including pipelines, state machines, and interconnects. Experiments on an 8051 datapath circuit show that the coverage is as high as 99.59%. This technique has been proven to work successfully in 8 μm Thin-film transistor (TFT) technology on the glass.     

Partial scan flip-flop selection by use of empirical testability

Partial serial scan as a design for testability technique permits automatic generation of high fault coverage tests for sequential circuits with less hardware overhead and less performance degradation than full serial scan. The objective of the partial scan flip-flop selection method proposed here is to obtain maximum fault coverage for the number of scan flip-flops selected. Empirical Testability Difference (ETD), a measure of potential improvement in the testability of the circuit, is used to successively select one or more flip-flops for addition or deletion of scan logic. ETD is calculated by using testability measures based on empirical evaluation of the circuit with the acutal automatic test pattern generation (ATPG) system. In addition, once such faults are known, ETD focuses on the hard-to-detect faults rather than all faults and uses heuristics to permit effective selection of multiple flip-flops without global optimization. Two ETD algorithms have been extensively tested by using FASTEST ATPG [1, 2] on fourteen of the ISCAS89 [3] sequential circuits. The results of these tests indicate that ETD yields, on average, 35% fewer uncovered detectable faults for the same number of scanned flip-flops or 27% fewer scanned flip-flops for comparable fault coverage relative to cycle-breaking methods.This work was performed while the author was with the University of Wisconsin-Madison.     

Built-in test of CMOS state machines with realistic faults: asystem perspective

The design of built-in test systems for large arrays is approached from the viewpoint of detecting real faults in the mask layers of a typical CMOS process. The resulting testable design and built-in test system provides a practical compromise between the costly hardware augmentation plaguing existing techniques and circuit independence of the test procedure. Built-in testability is achieved independently of feedback. Therefore, combinational and sequential circuits can be tested in parallel with exactly the same hardware and method. The test-specific hardware overhead decreases rapidly with increasing circuit size and falls below 10% for large arrays with more than 100 product terms. No additional gate delays are introduced into the critical path by the test circuitry. The normal circuit performance is, therefore, left intact with the exception of a minimal degradation associated with adding tristate capability to the input buffers     

TESTCHIP: a chip for weighted random pattern generation,evaluation, and test control

In self-testable circuits, additional hardware is incorporated for generating test patterns and evaluating test responses. A built-off test strategy is presented which moves the additional hardware to a programmable extra chip. This is a low-cost test strategy in three ways: (1) the use of random patterns eliminates the expensive test-pattern computation; (2) a microcomputer and an ASIC (application-specific IC) replace the expensive automatic test equipment; and (3) the design for testability overhead is minimized. The presented ASIC generates random patterns, applies them to a circuit under test, and evaluates the test responses by signature analysis. It contains a hardware structure that can produce weighted random patterns corresponding to multiple programmable distributions. These patterns give a high fault coverage and allow short test lengths. A wide range of circuits can be tested as the only requirement is a scan path and no other test structures have to be built in     

TAO: regular expression-based register-transfer level testabilityanalysis and optimization

In this paper, we present testability analysis and optimization (TAO), a novel methodology for register-transfer level (RTL) testability analysis and optimization of RTL controller/data path circuits. Unlike existing high-level testing techniques that cater restrictively to certain classes of circuits or design styles, TAO exploits the algebra of regular expressions to provide a unified framework for handling a wide variety of circuits including application-specific integrated circuits (ASICs), application-specific programmable processors (ASPPs), application-specific instruction processors (ASIPs), digital signal processors (DSPs), and microprocessors. We also augment TAO with a design-for-test (DFT) framework that can provide a low-cost testability solution by examining the tradeoffs in choosing from a diverse array of testability modifications like partial scan or test multiplexer insertion in different parts of the circuit. Test generation is symbolic and, hence, independent of bit width. Experimental results on benchmark circuits show that TAO is very efficient, in addition to being comprehensive. The fault coverage obtained is above 99% in all cases. The average area and delay overheads for incorporating testability into the benchmarks are only 3.2% and 1.0%, respectively. The test generation time is two-to-four orders of magnitude smaller than that associated with gate-level sequential test generators, while the test application times are comparable     

The optimistic update theorem for path delay testing in sequential circuits

For sequential circuit path delay testing, we propose a new update rule for state variables whereby flipflops are updated with their correct values provided they are destinations of at least one robustly activated path delay fault. Existing algorithms in the literature, for robust fault simulation and test generation, assign unknown values to off-path latches that have non-steady signals at their inputs in the previous vector. Such procedures are pessimistic and predict low fault coverages. They also have an adverse effect on the execution time of fault simulation especially if the circuit has a large number of active paths. The proposed update rule avoids these problems and yet guarantees robustness.     

IDDQ detectability of bridges in CMOS sequentialcircuits

Differences between controllability conditions for I_DDQ detectability in CMOS combinational and sequential circuits in the presence of bridging defects are presented. The usual detectability condition for current testability of bridges in combinational circuits is shown to fail for defective sequential circuits. New conditions for sequential circuits are presented     

Resynthesis of Combinational Circuits for Path Count Reduction and for Path Delay Fault Testability

Path delay fault model is the most suitable model for detectingdistributed manufacturing defects which can cause delayfaults. However, the number of paths in a modern design can beextremely large and the path delay testability of many practicaldesigns is very low. In this paper we show how to resynthesize acombinational circuit in order to reduce the total number of paths inthe circuit. Our results show that it is possible to obtain circuitswith a significant reduction in the number of paths while notincreasing area and/or delay of the longest sensitizable path in thecircuit.Research on path delay testing shows that in many circuits a largeportion of paths does not have a test that can guarantee detection ofa delay fault. The path delay testability of a circuit would increaseif the number of such paths is reduced. We show that addition of asmall number of test points into the circuit can help reducing thenumber of such paths in the given design.     

Parallel sequence fault simulation for synchronous sequential circuits

A novel parallel sequence fault simulation (PSF) algorithm for synchronous sequential circuits is presented. The algorithm successfully extend the parallel pattern method for combinational circuits to sequential circuits by proposing a multiple-pass mechanism to overcome the state dependency in sequential circuits. The fault simulation is performed in parallel by partitioning the entire sequence into subsequences of equal length. Furthermore, techniques are developed to minimize the number of simulation passes. Notably, two compact counters, C _x and C _d , are proposed to faciliate the early stabilization detection of faulty circuit simulation with minimum space overhead. The experimental results on the benchmark circuits show that the speedup ratio over a serial sequence fault simulator based on ROOFS is 9.16 on average for pseudo random vectors. The parallel sequence algorithm of PSF is especially adaptable to parallel and distributed simulation which exploits sequence partition.     

Physical design of testable VLSI: techniques and experiments

It is shown that the layout of VLSI circuits can affect testability and in some cases reduce the number of faults likely in a design, easing test generation. A method for analyzing circuits at the symbolic layout level and enhancing testability using local transformations is presented. To demonstrate the application of the technique a set of CMOS standard cells was redesigned. The standard cells are used in the MIS synthesis system, allowing the designer to modify interactively designs to perform tradeoff analysis on testable designs. To show the usefulness of the technique, an experiment was performed: example circuits were synthesized, and test vectors were generated and then used in a transistor-level fault simulator. It was found that the modified designs have significantly higher fault coverage than unmodified designs. A strategy for the synthesis of easily testable combinational random logic circuits is presented     

A switch-level test generation system for synchronous and asynchronous circuits

A switch-level test generation system for synchronous and asynchronous circuits has been developed in which a new algorithm for fully automatic switch-level test generation and an existing fault simulator have been integrated. For test generation, a switch-level circuit is modeled as a logic network that correctly models the behavior of the switch-level including bidirectionality, dynamic charge storage, and ratioed logic. The algorithm is able to generate tests for combinational and sequential circuits. BothnMOS and CMOS circuits can be modeled. In addition to the classical line stuck-at faults, the algorithm is able to handle stuck-open and stuck-closed faults on the transistors of the circuit.In synchronous circuits, the time-frame based algorithm uses asynchronous processing within each clock phase to achieve stability in the circuit and synchronous processing between clock phases to model the passage of time. In asynchronous circuits, the algorithm uses asynchronous processing to reach stability within and between modules. Unlike earlier time-frame based test generators for general sequential circuits, the test generator presented uses the monotonicity of the logic network to speed up the search for a solution. Results on benchmark circuits show that the test generator outperforms an existing switch-level test generator both in time and space requirements. The algorithm is adaptable to mixed-level test generation.     

Autoscan: a scan design without external scan inputs or outputs

We propose a design-for-testability technique for synchronous sequential circuits called autoscan. Autoscan uses scan chains similar to conventional scan. However, it gives up the external scan inputs and outputs in order to eliminate the test data volume associated with them. Scan operations under autoscan improve the circuit testability by allowing the circuit state to be modified through shifting. Due to the removal of the scan inputs and outputs, synthesis of scan chains under autoscan does not have to satisfy all the constraints imposed on conventional scan chains. We describe a synthesis procedure for autoscan chains, and demonstrate that autoscan allows us to detect almost all the faults that are detectable using conventional scan. We use random sequences in order to show that sequential test generation is not necessary under autoscan. We also describe a test generation procedure, and discuss the effect of autoscan on fault diagnosis.     

A hierarchical test generation methodology for digital circuits

A new hierarchical modeling and test generation technique for digital circuits is presented. First, a high-level circuit model and a bus fault model are introduced—these generalize the classical gate-level circuit model and the single-stuck-line (SSL) fault model. Faults are represented by vectors allowing many faults to be implicitly tested in parallel. This is illustrated in detail for the special case of array circuits using a new high-level representation, called the modified pseudo-sequential model, which allows simultaneous test generation for faults on individual lines of a multiline bus. A test generation algorithm called VPODEM is then developed to generate tests for bus faults in high-level models of arbitrary combinational circuits. VPODEM reduces to standard PODEM if gate-level circuit and fault models are used. This method can be used to generate tests for general circuits in a hierarchical fashion, with both high- and low-level fault types, yielding 100 percent SSL fault coverage with significantly fewer test patterns and less test generation effort than conventional one-level approaches. Experimental results are presented for representative circuits to compare VPODEM to standard PODEM and to random test generation techniques, demonstrating the advantages of the proposed hierarchical approach.