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     

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.     

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.     

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

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

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.     

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.     

Multifault and delay-fault testability of multilevel circuits

This paper investigates the relationship between test sets for multiple stuck-at faults and robust path-delay-fault tests in multilevel combinational circuits. It is shown that, in multilevel circuits, a complete robust path-delay-fault test set may not detect all multiple stuck-at faults. We also show that the detectability of the former does not imply the detectability of the latter, as suggested in a recent paper. The presence of undetectable or untested multiple stuck-at faults may invalidate some path delay tests.Supported in part by NSF Grant MIP-9320886.     

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.     

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.     

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.     

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.     

Multiple fault detection in two-level multi-output circuits

It is often stated that in irredundant two-level logic circuits, a test set for all single stuck faults will also detect all multiple stuck faults. We show by a simple example that this result does not hold for multi-output circuits even when each output function is prime and irredundant. Using a result from the programmable logic array technology, we give an output ordering constraint that, if satisfied during test generation, will make a single stuck fault test set a valid multiple stuck fault test set for irredundant two-level multi-output circuits.     

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.     

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.     

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 Test Generation Framework for Quantum Cellular Automata Circuits

In this paper, we present a test generation framework for quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted recent significant attention and shows promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC and ISCAS'85 benchmarks that use majority gates as primitives     

Test Generation for Mixed-Signal Devices Using Signal Flow Graphs

We describe a new reverse simulation approach to analog and mixed-signal circuit test generation that parallels digital test generation. We invert the analog circuit signal flow graph, reverse simulate it with good and bad machine outputs, and obtain test waveforms and component tolerances, given circuit output tolerances specified by the functional test needs of the designer. The inverted graph allows backtracing to justify analog outputs with analog input sinusoids. Mixed-signal circuits can be tested using this approach, and we present test generation results for two mixed-signal circuits and four analog circuits, one being a multiple-input, multiple-output circuit. This analog backtrace method can generate tests for second-order analog circuits and certain non-linear circuits. These cannot be handled by existing methods, which lack a fault model and a backtrace method. Our proposed method also defines the necessary tolerances on circuit structural components, in order to keep the output circuit signal within the envelope specified by the designer. This avoids the problem of overspecifying analog circuit component tolerances, and reduces cost. We prove that our parametric fault tests also detect all catastrophic faults. Unlike prior methods, ours is a structural, rather than functional, analog test generation method.     

Theorems for Fault Collapsing in Combinational Circuits

This paper gives a mathematical approach to fault collapsing based on the stuck-at fault model for combinational circuits. The mathematical structure we work within is a Boolean ring of Boolean functions of several variables. The goal of fault collapsing for a given circuit is to reduce the number of stuck-at faults to be considered in test generation and fault diagnosis. For this purpose we need rules that let us eliminate faults from the considered fault set. In this paper some earlier known rules are proved in the new context, and several new rules are presented and proved. The most important of the new theorems deal with the relationship between stuck-at faults on a fanout stem and the branches. The concept of monotony of Boolean functions appears to be important in most of these new rules. Editor: M. Hsiao Audhild Vaaje received the M.S. degree and the Ph.D. degree in mathematics from University of Oslo in 1971 and 1992, respectively. She is an associate professor of mathematics at Agder University College in Norway, where she has been employed since 1972. She has research interests in mathematics applied to fault detection in digital circuits.     

Shorts in self-checking circuits

It has been noted by several authors that the classical stuck-at logical fault model might not be an appropriate representation of certain real failures occurring in integrated circuits. Shorts are an important class of such faults. This article gives a detailed analysis of the effects of shorts in self-checking circuits and proposes techniques for dealing with them. More precisely, we show that, unlike other faults such as stuck-at, stuck-on, and stuck-open—which produce only single errors in the place they occur—shorts can produce double errors on the two shorted lines. In particular, feedback shorts can produce double errors on the two shorted lines. The double error is unidirectional for some feedback shorts and non-unidirectional for some others. Furthermore, in some technologies (e.g., CMOS), non-feedback shorts can also produce double non-unidirectional errors. We also show that unlike stuck-at, stuck-on, and stuck-open faults, redundant shorts can destroy the SFS property. Then we propose several techniques for coping with these problems and we illustrate the results by circuit implementation examples.The present study is given for NMOS and CMOS circuits but we show that it is valid for any other technology.