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.     

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.     

Sequential circuit test generation using dynamic justification equivalence

Automatic test pattern generation (ATPG) for sequential circuits involves making decisions in the search decision spaces bounded by a sequential circuit. The flip-flops in the sequential circuit determine the circuit state search decision space. The inputs of the circuit define the combinational search decision space. Much work on sequential circuit ATPG acceleration focused on how to make ATPG search decisions. We propose a new technique to improve sequential circuit ATPG efficiency by focusing on not repeating previous searches. This new method is orthogonal to existing deterministic sequential circuit ATPG algorithms.A common search operation in sequential circuit ATPG is justification, which is to find an input assignment to justify a desired output assignment of a component. We have observed that implications in a circuit resulting from prior justification decisions form an unique justification decomposition. Since the connectivity of a circuit does not change during ATPG, test generation for different target faults may share identical justification decision sequences represented by identical decision spaces. Because justification decomposition represents the collective effects of prior justification decisions, it is used to identify previously-explored justification decisions. Preliminary results on the ISCAS 1989 circuits show that our test generator (SEST) using justification decompositions, on average, runs 2.4 and 4.5 times faster than Gentest and Hitec, respectively. We describe the details of justification equivalence and its application in ATPG accompanied with step-by-step examples.     

ATPG for combinational circuits on configurable hardware

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, and loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of hardware cost and speed and how it compares with software-based techniques     

A Functional Decomposition Method for Redundancy Identification and Test Generation

We present a new combinational circuit automatic test-pattern generation (ATPG)acceleration method called EST that detects equivalent search states, which are saved for later use. The search space is learned and characterized using E-frontiers, which are circuit cut-sets induced by theimplication stack contents. The search space is reduced by matchingthe current search state against previously-encountered search states(possibly from prior faults), and this reduces the length of thesearch. A second contribution is a calculus of redundant faults, which enables EST to make many more mandatoryassignments before search than is possible by prior algorithms, byeffectively using its knowledge of prior faults proven to beredundant. This accelerates ATPG for subsequent faults. Thesemethods accelerate the TOPS algorithm 33.3 times for thehard-to-test faults in the ISCAS 85 benchmarks, and the SOCRATES algorithm 5.6 times for the same hard-to-test faults, with little memory overhead.     

Evaluating the Effectiveness of D-chains in SAT-based ATPG and Diagnostic TPG

The ever increasing size and complexity of today’s Very-Large-Scale-Integration (VLSI) designs requires a thorough investigation of new approaches for the generation of test patterns for both test and diagnosis of faults. SAT-based automatic test pattern generation (ATPG) is one of the most popular methods, where, in contrast to classical structural ATPG methods, first a mathematical representation of the problem in form of a Boolean formula is generated, which is then evaluated by a specialized solver. If the considered fault is testable, the solver will return a satisfying assignment, from which a test pattern can be extracted; otherwise no such assignment can exist. In order to speed up test pattern generation, the concept of D-chains was introduced by several researchers. Thereby supplementary clauses are added to the Boolean formula, reducing the search space and guiding the solver toward the solution. In the past, different variants of D-chains have been developed, such as the backward D-chain or the indirect D-chain. In this work we perform a thorough analysis and evaluation of the D-chain variants for test pattern generation and also analyze the impact of different D-chain encodings on diagnostic test pattern generation. Our experimental results show that depending on the incorporated D-chain the runtime can be reduced tremendously.     

Too Few or Too Many Properties? Measure it by ATPG!

Verification of a design, based on model checking, requires the identification of a set of formal properties manually derived from the specification of the design under verification (DUV). Such a set can include too few or too many properties. This paper proposes to use a functional ATPG to identify missing properties and to remove unnecessary ones. In particular, the paper refines, extends, and compares, with other symbolic approaches, a methodology to estimate the completeness of formal properties, which exploits a functional fault model and a functional ATPG. Moreover, the same fault model and ATPG are used to face the opposite problem of identifying useless properties, that is, properties which are in logical consequence. Logical consequence between properties is generally examined by using theorem proving, which may require a large amount of time and space resources. On the contrary, the paper proposes a faster approach which analyzes logical consequence by observing the property capability of revealing functional faults. The joint use of the methodologies allows to optimize the set of properties used for several verification sessions needed to check all design phases of an incremental design flow.     

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.     

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.     

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.     

Test Set and Fault Partitioning Techniques for Static Test Sequence Compaction for Sequential Circuits

We propose a new static test set compaction method based on a careful examination of attributes of fault coverage curves. Our method is based on two key ideas: (1) fault-list and test-set partitioning, and (2) vector re-ordering. Typically, the first few vectors of a test set detect a large number of faults. The remaining vectors usually constitute a large fraction of the test set, but these vectors are included to detect relatively few hard faults. We show that significant compaction can still be achieved by partitioning faults into hard and easy faults, and compaction is performed only for the hard faults. This significantly reduces the computational cost for static test set compaction without affecting quality of compaction. The second key idea re-orders vectors in a test set by moving sequences that detect hard faults to the beginning of the test set. Fault simulation of the newly concatenated re-ordered test set results in the omission of several vectors so that the compact test set is smaller than the original test set. Experiments on several ISCAS 89 sequential benchmark circuits and large production circuits show that our compaction procedure yields significant test set reductions in low execution times.     

Efficient Transition Fault ATPG Algorithms Based on Stuck-At Test Vectors

This paper proposes novel algorithms for computing test patterns for transition faults in combinational circuits and fully scanned sequential circuits. The algorithms are based on the principle that s@ vectors can be effectively used to construct good quality transition test sets. Several algorithms are discussed. Experimental results obtained using the new algorithms show that there is a 20% reduction in test set size, test data volume and test application time compared to a state-of-the-art native transition test ATPG tool, without any reduction in fault coverage. Other benefits of our approach, viz. productivity improvement, constraint handling and design data compression are highlighted.     

Fault-based ATPG for linear analog circuits with minimal size multifrequency test sets

An automatic test pattern generation (ATPG) procedure for linear analog circuits is presented in this work. A fault-based multifrequency test approach is considered. The procedure selects a minimal set of test measures and generates the minimal set of frequency tests which guarantee maximum fault coverage and, if required, maximal fault diagnosis, of circuit AC hard/soft faults. The procedure is most suitable for linear time-invariant circuits which present significant frequency-dependent fault effects.For test generation, the approach is applicable once parametric tests have determined DC behaviour. The advantage of this procedure with respect to previous works is that it guarantees a minimal size test set. For fault diagnosis, a fault dictionary containing a signature of the effects of each fault in the frequency domain is used. Fault location and fault identification can be achieved without the need of analog test points, and just in-circuit checkers with an observable go/no-go digital output are required for diagnosis.The procedure is exemplified for the case of an analog biquadratic filter. Three different self-test approaches for this circuit are considered. For each self-test strategy, a set of several test measures is possible. The procedure selects, in each case, the minimal set of test measures and the minimal set of frequency tests which guarantee maximum fault coverage and maximal diagnosis. With this, the self-test approaches are compared in terms of the fault coverage and the fault diagnosability achieved.This work is part of AMATIST ESPRIT-III Basic Research Project, funded by CEC under contract #8820.     

Identifying Untestable Faults in Sequential Circuits Using Test Path Constraints

The paper proposes a hierarchical untestable stuck-at fault identification method for non-scan synchronous sequential circuits. The method is based on deriving, minimizing and solving test path constraints for modules embedded into Register-Transfer Level (RTL) designs. First, an RTL test pattern generator is applied in order to extract the set of all possible test path constraints for a module under test. Then, the constraints are minimized using an SMT solver Z3 and a logic minimization tool ESPRESSO. Finally, a constraint-driven deterministic test pattern generator is run providing hierarchical test generation and untestability proof in sequential circuits. We show by experiments that the method is capable of quickly proving a large number of untestable faults obtaining higher fault efficiency than achievable by a state-of-the-art commercial ATPG. As a side effect, our study shows that traditional bottom-up test generation based on symbolic test environment generation at RTL is too optimistic due to the fact that propagation constraints are ignored.     

片上集成电路系统测试的新电路设计

It is very important to detect transition-delay faults and stuck-at faults in system on chip （SoC） under 90 nm processing technology, and the transition-delay faults can only be detected by using an at-speed testing method. In this paper, an on-chip clock （OCC） controller with a bypass function based on an internal phase-locked loop is designed to test faults in SoC. Furthermore, a clock chain logic which can eliminate the metastable state is realized to generate an enable signal for the OCC controller, and then, the test pattern is generated by automatic test pattern generation （ATPG） tools. Next, the scan test pattern is simulated by using the Synopsys tool and the correctness of the design is verified. The result shows that the design of an at-speed scan test in this paper is highly efficient for detecting timing-related defects. Finally, the 89.29% transition-delay fault coverage and the 94.50% stuck-at fault coverage are achieved, and it is successfully applied to an integrated circuit design.     

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.     

Automatic Test Pattern Generation for Resistive Bridging Faults

An ATPG for resistive bridging faults in combinational or full-scan circuits is proposed. It combines the advantages of section-based generation and interval-based simulation. In contrast to the solutions introduced so far, it can handle static effects of arbitrary non-feedback bridges between two nodes, including ones detectable at higher bridge resistance and undetectable at lower resistance, and faults requiring more than one vector for detection. The developed tool is applied to ISCAS circuits, and a higher efficiency compared with other resistive bridging fault as well as stuck-at ATPG is reported. Information required for accurate resistive bridging fault simulation is obtained as a by-product.     

SOC中嵌入式存储器阴影逻辑的可测性设计

在使用ATPG工具对集成电路进行固定故障测试时,嵌入式存储器模块被视为简单的I/O模型,ATPG工具无法传递存储器周围组合逻辑的故障.通过研究SOC的可测性设计后,针对某数字信息安全芯片设计,利用扫描设计原理,改进了其存储器周围逻辑的设计,为阴影逻辑提供了可测试路径,提高了整个芯片的测试覆盖率和故障覆盖率.分析了设计的功耗、面积,确定了设计的有效性.     

Search strategy switching: A cost model and an analysis of backtracking

Test generation algorithms contain search strategies which are used to control decision making when the algorithm encounters a choice of signal value, or what action to perform next. Our study of traditional search strategies used in automatic test pattern generation has led us to the observation that no single strategy is superior for all faults in a circuit and all circuits. Further experimentation led to the conclusion that a combination of search strategies provides better fault coverage and/or faster ATPG for a given backtrack limit. Instead of using just one strategy up to the backtrack limit, a primary strategy is used for the first half of the backtrack limit, then a secondary strategy is used for the second half of the backtrack limit. This article presents a qualitative ATPG cost model based on the number of test generation events, uses this model to explain why search strategy switching is faster, and shows experimental evidence to verify both the cost model and search strategy switching theory. The experiments were performed with the ISCAS circuits and our implementation of the FAN algorithm.