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.     

Test generation for technology-specific multi-faults based on detectable perturbations

In this paper, we introduce the concept of detectable perturbations as a method to generate tests that cover any technology-specific faults such as multiple bridging, open and stuck-at faults. Rather than devising a customized test pattern generation system for each class of technology-specific faults, we implemented a generic system to generate tests for single and multiple perturbations. We demonstrate the versatility of this approach by generating tests for a set of large benchmark circuits that have been mapped into single- and multi-output modules. These tests cover single stuck-at, multi-output bridging, stuck-at, as well as any mutation faults in the functionality of the technology-mapped cells. Experimental results provide useful insights about the quality of single stuck-at test patterns versus coverages for the additional classes of faults.     

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.     

Robust tests for parity trees

Linear logic circuits are used extensively in digital computing and signal processing systems. They are constructed as regular arrays (for example as cascade or tree circuits), employing linear gates such as Exclusive OR (EOR) and Exclusive NOR (ENOR) gates. Earlier studies on fault diagnosis in linear logic circuits were based on the classical fault model of line stuck-at faults. Transistor stuck-open (SOP) and stuck-on (SON) faults in linear circuits were studied recently, but the effect of signal transients due to circuit delays and time skews in input changes were not considered in the derivation of test sequences. These latter factors are known to cause invalidation of two pattern tests for stuck-open faults. In this article we consider the problem of generating robust tests for linear logic circuits. These tests are not affected by circuit transients caused by delays. A major finding in this paper is that, if the test invalidation problem is redressed by introducing robust tests, the test length becomes a linear function of the depth of the circuit as opposed to the constant number of tests derived in previous studies, by neglecting circuit transients. A lower bound on minimum number of distinct test patterns needed for a tree of EOR gates of depthd is derived. This number depends on the specific implementation of the gate. Robust test-generation procedures are proposed for both single and multiple fault models and their optimalities are argued. Given that every gate in a parity tree is robustly testable, a test sequence that can test for all faults in the circuit, regardless of the nature of gate implementation, is calleduniversal robust test sequence for a parity tree. Finally we propose an optimal universal robust test sequence.     

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.     

On the generation of test patterns for multiple faults

This article presents a new method to generate test patterns for multiple stuck-at faults in combinational circuits. We assume the presence of all multiple faults of all multiplicities and we do not resort to their explicit enumeration: the target fault is a single component of possibly several multiple faults. New line and gate models are introduced to handle multiple fault effect propagation through the circuits. The method tries to generate test conditions that propagate the effect of the target fault to primary outputs. When these conditions are fulfilled, the input vector is a test for the target fault and it is guaranteed that all multiple faults of all multiplicities containing the target fault as component are also detected. The method uses similar techniques to those in FAN and SOCRATES algorithms to guide the search part of the algorithm, and includes several new heuristics to enhance the performance and fault detection capability. Experiments performed on the ISCAS'85 benchmark circuits show that test sets for multiple faults can be generated with high fault coverage and a reasonable increase in cost over test generation for single stuck-at faults.     

通用Toffoli可逆门的固定故障测试

可逆电路技术在低功耗芯片和量子通信中广泛使用。目前,大部分学者着重研究可逆电路的合成,对电路的故障测试却很少问津,但是可逆电路的测试在应用中却十分重要。文中构造了一种四输入通用Toffoli门（universal toffoli gate,UTG）用来检测电路故障,这个门可以实现所有基本的布尔逻辑。UTG门可以检测到所...     

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     

Design error diagnosis in digital circuits with stuck-at fault model

In this paper we describe in detail a new method for the single gate-level design error diagnosis in combinational circuits. Distinctive features of the method are hierarchical approach (the localizing procedure starts at the macro level and finishes at the gate level), use of stuck-at fault model (it is mapped into design error domain only in the end), and design error diagnostic procedure that uses only test patterns generated by conventional gate-level stuck-at fault test pattern generators (ATPG). No special diagnostic tests are used because they are much more time consuming. Binary decision diagrams (BDD) are exploited for representing and localizing stuck-at faults on the higher signal path level. On the basis of detected faulty signal paths, suspected stuck-at faults at gate inputs are calculated, and then mapped into suspected design error(s). This method is enhanced compared to our previous work. It is applicable to redundant circuits and allows using incomplete tests for error diagnosis. Experimental data on ISCAS benchmark circuits shows the advantage of the proposed method compared to the known algorithms of design error diagnosis.     

Classification and Test Generation for Path-Delay Faults Using Single Struck-at Fault Tests

We classify all path-delay faults of a combinational circuit intothree categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent} (ST-dependent). The classification uses anyunaltered single stuck-at fault test generation tool. Only two runsof this tool on a model network derived from the original network areperformed. As a by-product of this process, we generate single andmultiple input change delay tests for all testable faults. With thesetests, we expect that most defective circuits are identified. All STfaults are guaranteed detection in the case of a single fault, andsome may be guaranteed detection through robust and validatablenon-robust tests even in the case of multiple faults. An ST-dependentfault can affect the circuit speed only if certain ST faults arepresent. Thus, if all ST faults are tested, the ST-dependent faultsneed not be tested. MT faults cannot be guaranteed detection, butaffect the speed only if delay faults simultaneously exist on a setof paths, none of which is ST. Examples and results on several ISCAS89 benchmarks are presented. The method of classification throughtest generation using a model network is complex and can be appliedto circuits of moderate size. For larger circuits, alternativemethods will have to be explored in the future.     

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.     

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 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.     

A characterization of robust test-pairs for stuck-open faults

Tests for stuck-open faults in static CMOS circuits consist of a sequence of two input vectors. Such test-pairs may be invalidated by delays in the circuit. Test-pairs that are not invalidated by delays in the circuit are known as robust test-pairs. We present a six-valued logic system Ω = {0, 1, r, f, 0h, 1h}. We show how Ω differs from a number of other logic systems that have been proposed for test generation. This logic system abstracts the important aspects of the transition behavior of the circuit, on application of an input pair, that is necessary to characterize robust test-pairs for stuck-open faults. This characterization of robust test-pairs is used to derive:

1. an algorithm for determining if a given test-pair is a robust test-pair for a given stuck-open fault or not; and
2. a simplified algorithm for computing a robust test-pair for a stuck-open fault. The resulting algorithm for computing robust tests for stuck-open faults can be implemented by minor modifications to test generation algorithms for stuck-at faults.

     

Testing of multiple-output domino logic (MODL) CMOS circuits

Techniques for testing MODL circuits are presented. It is shown that, due to the greater observability of MODL circuits, their test sets can be considerably small than those derived for the conventional domino CMOS circuits. Tests for faults are derived from a comprehensive fault model which includes stuck-at, stuck-open, and stuck-on faults. Test sets for MODL circuits are inherently robust in the presence of circuit delays and timing skews at the inputs. They are also well-protected against the charge distribution problem. It is thus concluded that MODL is an attractive CMOS logic technique     

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.     

Generation and evaluation of current and logic tests for switch-level sequential circuits

This article presents an approach to developing high quality tests for switch-level circuits using both current and logic test generation algorithms. Faults that are aborted or undetectable by logic tests may be detected by current tests, or vice versa. An efficient switch level test generation algorithm for generating current and logic tests is introduced. Clear definitions for analyzing the effectiveness of the joint test generation approach are derived. Experimental results are presented for demonstrating high coverage of stuck-at, stuck-on, and stuck-open faults for switch level circuits when both current and logic tests are used.This is expanded version of the work originally presented at the 1991 International Test Conference.     

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.     

Data-feedthrough faults in circuits using unclocked storageelements

Some faults in storage elements (SEs) do not manifest as stuck-at-0/1 faults. These include data-feedthrough faults that cause the SE cell to exhibit combinational behaviour. The authors investigate the implications of such faults on the behaviour of circuits using unclocked SEs. It is shown that effects of data-feedthrough faults at the behavioural level are different from those due to stuck-at faults, and therefore tests generated for the latter may be inadequate     

BiCMOS logic testing

With the anticipated growth of BiCMOS technology for high-performance ASIC design, the issue of testing takes on great significance. This paper addresses the testing of BiCMOS logic circuits. Since many different implementations of BiCMOS gates have been proposed, four representative ones are studied. The adequacy of stuck-at, quiescent current, and delay testing are examined based on circuit level faults. It is demonstrated that a large portion of the defects cannot be detected by common stuck-at or quiescent current tests since they manifest themselves as delay faults. By using the results presented, the test methodologies and the logic families can be ranked based on fault coverage. This ranking can then be used to help decide which BiCMOS solution is proper for a given application