A synthesis-based test generation and compaction algorithm for multifaults

Because of its inherent complexity, the problem of automatic test pattern generation for multiple stuck-at faults (multifaults) has been largely ignored. Recently, the observation that multifault testability is retained by algebraic factorization demonstrated that single fault (and therefore multifault) vector sets for two-level circuits could give complete multifault coverage for multilevel circuits constructed by algebraic factorization. Unfortunately, in using this method the vector set size can be much larger than what is really required to achieve multifault coverage, and the approach has some limitations in its applicability.In this article we first present a multifault test generation and compaction strategy for algebraically factored multilevel circuits, synthesized from two-level representations. We give a basic sufficiency condition for multifault testability of such networks.We next focus on the relationship between hazard-free robust path-delay-fault testability and multifault testability. We show that the former implies the latter for arbitrary multilevel circuits. This allows the use of previously developed composition rules that maintain path-delay-fault testability for the synthesis of multifault testable circuits.We identify a class of multiplexor-based networks and prove an interesting property of such networks—if the networks are fully single stuck-at fault testable, or made fully single stuck-at fault testable, they are completely multifault testable. We give a multifault test generation and compaction algorithm for such networks.We provide experimental results which indicate that a compacted multifault test set derived using the above strategies can be significantly smaller than the test set derived using previously proposed procedures. These results also indicate the substantially wider applicability of our procedures, as compared to previous techniques.     

Multiple Stuck-at Fault Testability Analysis of ROBDD Based Combinational Circuit Design

Automatic test pattern generation (ATPG) is the next step after synthesis in the process of chip manufacturing. The ATPG may not be successful in generating tests for all multiple stuck-at faults since the number of fault combinations is large. Hence a need arises for highly testable designs which have 100% fault efficiency under the multiple stuck-at fault(MSAF) model. In this paper we investigate the testability of ROBDD based 2×1 mux implemented combinational circuit design. We show that the ROBDD based 2×1 mux implemented circuit is fully testable under multiple stuck-at fault model. Principles of pseudoexhaustive testing and multiple stuck-at fault testing of two level AND-OR gates are applied to one sub-circuit(2×1 mux). We show that the composite test vector set derived for all 2×1 muxes is capable of detecting multiple stuck-at faults of the circuit as a whole. Algorithms to derive test set for multiple stuck-at faults are demonstrated. The multiple stuck-at fault test set is larger than the single stuck-at fault test set. We show that the multiple stuck-at fault test set can be derived from the Disjoint Sum of Product expression which allows test pattern generation at design time, eliminating the need of an ATPG after the synthesis stage.     

Test Generation and Fault Simulation for Cell Fault Model using Stuck-at Fault Model based Test Tools

Cell Fault Model (CFM) is a well-adopted functional fault model used for cell-based circuits. Despite of the wide adoption of CFM, no test tool is available for the estimation of CFM testability. The vast majority of test tools are based on the single stuck-at fault model.In this paper we introduce a method to calculate the CFM testability of a cell-based circuit using any single stuck-at fault based test tool. Cells are substituted by equivalent cells and Test Generation and Fault Simulation for CFM are emulated by Test Generation and Fault Simulation for a set of single stuck-at faults of the equivalent cells. The equivalent cell is constructed from the original cell with a simple procedure, with no need of knowledge of gate-level implementation, or its function. With the proposed methodology, the maturity and effectiveness of stuck-at fault based tools is used in testing of digital circuits, with respect to Cell Fault Model, without developing new tools.     

Reliability of majority voting based VLSI fault-tolerant circuits

The effect of compensating module faults on the reliability of majority voting based VLSI fault-tolerant circuits is investigated using a fault injection simulation method. This simulation method facilitates consideration of multiple faults in the replicated circuit modules as well as the majority voting circuits to account for the fact that, in VLSI implementations, the majority voting circuits are constructed from components of the same reliability as those used to construct the circuit modules. From the fault injection simulation, a survivability distribution is obtained which, when combined with an area overhead expression, leads to a more accurate reliability model for majority voting based VLSI fault-tolerant circuits. The new model is extended to facilitate the calculation of reliability of fault-tolerant circuits which have sustained faults but continue to operate properly. Analysis of the reliability model indicates that, for some circuits, the reliability obtained with majority voting techniques is significantly greater than predicted by any previous model     

Resynthesis of combinational logic circuits for improved path delayfault testability using comparison units

We propose a resynthesis method that modifies a given circuit to reduce the number of paths in the circuit and thus improve its path delay fault testability. The resynthesis procedure is based on replacing subcircuits of the given circuit by structures called comparison units. A subcircuit can be replaced by a comparison unit if it implements a function belonging to the class of comparison functions defined here. Comparison units are fully testable for stuck-at faults and for path delay faults. In addition, they have small numbers of paths and gates. These properties make them effective building blocks for resynthesis to improve the path delay fault testability of a circuit. Experimental results demonstrate considerable reductions in the number of paths and increased path delay fault testability. These are achieved without increasing the number of gates, or the number of gates along the longest path in the circuit. The random pattern testability for stuck-at faults remains unchanged     

Enabling testability of fault-tolerant circuits by means ofIDDQ-checkable voters

The reliability of a fault-tolerant circuit may be drastically impaired by the presence of maskable faults that never affect its functionality. Design for testability (DFT) techniques have to be applied to make maskable faults detectable. During the testing phase, traditional DFT schemes inhibit fault masking and/or activate additional observation/control paths through the circuit. Such schemes, however, do not enable on-line testing and cannot be applied to multilevel fault-tolerant circuits, where fault-masking is repeatedly performed inside the circuit. We propose a new approach to the design of testable fault-tolerant CMOS circuits that overcomes both limitations. Our approach is based on the use of I_DDQ-checkable voters (ICVs) that enable a complete test of maskable faults of any multiplicity during normal operations     

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.     

On methods to match a test pattern generator to acircuit-under-test

Autonomous circuits such as linear feedback shift registers (LFSRs) and cellular automats are used as low-cost test pattern generators for circuits testable by pseudo-random patterns. We demonstrate that different LFSRs of the same degree, started from different initial states, may yield significantly different fault coverages and test lengths when used as test pattern generators for a given circuit, especially when the circuit has faults which are hard to detect by a practical number of pseudo-random patterns. Methods to tailor an LFSR to a circuit-under-test are proposed, that attempt to select the most effective LFSR and initial state for the circuit. The first method is based on a learning process that can be applied directly to certain types of circuits. The learning process is also used to establish a collection of (primitive and nonprimitive) LFSRs and initial states, effective for arbitrary circuits. This collection can then be used as a starting point for a genetic optimization procedure aimed at improving the selected LFSR and initial state. The use of an LFSR that can apply complemented as well as uncomplemented test patterns is shown to significantly improve the fault coverage, at the cost of a small area overhead. Experimental results demonstrate the applicability of the proposed approaches to stuck-at faults and to transition faults     

A neural network algorithm for testing stuck-open faults in CMOS combinational circuits

In this article, an automatic test pattern generation technique using neural network models for stuck-open faults in CMOS combinational circuits is presented. For a gate level fault model of stuck-open faults in CMOS circuits, SR(slow-rise) and SF(slow-fall) gate transition faults we develop a neural network representation. A neural network computation technique for generating robust test patterns for stuck-open faults is given. The main result is extending previous efforts in stuck-at test pattern generation to stuck-open test pattern generation using neural network models. A second result is an extension of the technique to robust test pattern generation.     

Sequential Circuits with Combinational Test Generation Complexity under Single-Fault Assumption

We show that the test generation problem for all single stuck-at faults in sequential circuits with internally balanced structures can be reduced into the test generation problem for single stuck-at faults in combinational circuits. In our previous work, we introduced internally balanced structures as a class of sequential circuits with the combinational test generation complexity. However, single stuck-at faults on some primary inputs, called separable primary inputs, corresponded to multiple stuck-at faults in a transformed combinational circuit. In this paper, we resolve this problem. We show how to generate a test sequence and identify undetectability for single stuck-at faults on separable primary inputs.     

False-Path Removal Using Delay Fault Simulation

Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All segments of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a non-enumerative path delay fault simulator based on the path status graph (PSG) data-structure, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because the expanded circuit has some new interconnects with only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The reported results show that the quality of the result may depend on the coverage of testable paths by the vectors that are simulated. When non-enumerative path delay simulation and implication-based redundancy removal techniques are used, the present procedure of false-path elimination can be applied to very large circuits.     

Experimental Results for Self-Dual Multi-Output Combinational Circuits

In this short note, the possibilities and the limitations for the application of self-dual circuits with alternating inputs are experimentally investigated. The original circuit is assumed to be given as a netlist of gates. The necessary area overhead, the fault coverage for single stuck-at faults in test mode and the error detection probability in on-line mode due to internal stuck-at faults and stuck-at faults at the input lines are determined for MCNC benchmark circuits.     

A novel automatic test pattern generator for asynchronous sequential digital circuits

A novel automatic test pattern generator (ATPG) for stuck-at faults of asynchronous sequential digital circuits is presented. The developed ATPG does not require support by any design-for-testability method nor external software tool. The shortest test sequence generation is guaranteed by breadth-first search. The contribution is unique hazard identification before the test generation process, state justification on the gate level, sequential fault propagation based on breadth-first search and stepwise composition of state graphs for sequential test generation. A new six-valued logic together with a new algorithm was developed for hazardous transition identification. The internal combinational ATPG allows to generate test patterns one by one and only if it is required by sequential test generation. The developed and implemented ATPG was tested with speed-independent and quasi-delay-insensitive benchmark circuits.     

Bilateral Testing of Nano-scale Fault-Tolerant Circuits

As the technology enters the nano dimension, the inherent unreliability of nanoelectronics is making fault-tolerant architectures increasingly necessary in building nano systems. Because fault-tolerant hardwares help to mask the effects caused by increased levels of defects, testing the functionality of the chip together with the embedded fault-tolerance becomes a tremendous challenge. In this paper, a new bilateral testing framework for nano circuits is proposed, where multiple stuck-at faults across different modules in a triple module redundancy (TMR) architecture are considered. In addition, a new test generator is presented for the bilateral testing that takes into account the enormous number of bilateral stuck-at faults possible with new types of guidance in the search, and it can generate a set of vectors that can test the TMR-based nano circuit as a single entity. Experimental results reported for ISCAS’85 and ITC99 circuits demonstrate that the bilateral testing can help to capture many more defects which the single stuck-at fault misses.     

Testability of parity checkers

Checkers are used in digital circuits to detect both intermittent and stuck-at faults. The most common error detectors are parity checkers. Such circuits are themselves subject to failures. The use of parity trees is outlined, and techniques for testing them are surveyed. The effect of the checker's structure on its testability is discussed. Several fault models are considered: single stuck-at, multiple stuck-at, and bridging faults. The effectiveness of single stuck-at fault test sets in detecting multiple stuck-at and bridging faults is described. Upper bounds for the double fault coverage of the minimal single fault test are given for different tree structures. The testabilities of some selected checkers are examined to illustrate the concepts developed. A built-in self-test is proposed     

An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS’s indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.     

Circuit testable design and universal test sets for multiple-valued logic functions

The circuit testable realizations of multiple-valued functions are studied in this letter. First of all, it is shown that one vector detects all skew faults in multiplication modulo circuits or in addition modulo circuits, and n＋1 vectors detect all skew faults in the circuit realization of multiplevalued functions with n inputs. Secondly, min（max） bridging fault test sets with n＋2 vectors are presented for the circuit realizations of multiple-valued logic functions. Finally, a tree structure is used instead of cascade structure to reduce the delay in the circuit realization, it is shown that three vectors are sufficient to detect all single stuck-at faults in the tree structure realization of multiplevalued logic functions.     

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.     

Automatic Test Generation for Combinational Threshold Logic Networks

We propose an automatic test pattern generation (ATPG) framework for combinational threshold networks. The motivation behind this work lies in the fact that many emerging nanotechnologies, such as resonant tunneling diodes (RTDs), single electron transistor (SET), and quantum cellular automata (QCA), implement threshold logic. Consequently, there is a need to develop an ATPG methodology for this type of logic. We have built the first automatic test pattern generator and fault simulator for threshold logic which has been integrated on top of an existing computer-aided design (CAD) tool. These exploit new fault collapsing techniques we have developed for threshold networks. We perform fault modeling, backed by HSPICE simulations, to show that many cuts and shorts in RTD-based threshold gates are equivalent to stuck-at faults at the inputs and output of the gate. Experimental results with the MCNC benchmarks indicate that test vectors were found for all testable stuck-at faults in their threshold network implementations.