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.     

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.     

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.     

组合电路桥接故障诊断的测试生成及优化

在利用划分等价类的方法来诊断组合电路中桥接故障的基础上,本文提出了一种基于门特性的IDDQ测试集生成算法及对测试集排序筛选的优化方法.实验结果表明,将此方法应用于组合电路桥接故障的诊断可缩减测试集的大小,提高诊断的故障覆盖率.     

Optimization-based multifrequency test generation for analog circuits

A robust test set for analog circuits has to detect faults under maximal masking effects due to variations of circuit parameters in their tolerance box. In this paper we propose an optimization based multifrequency test generation method for detecting parametric faults in linear analog circuits. Given a set of performances and a frequency range, our approach selects the test frequencies that maximize the observability on a circuit performance of a parameter deviation under the worst masking effects of normal variations of the other parameters. Experimental results are provided and validated by HSpice simulations to illustrate the proposed approach.     

A test generation program for sequential circuits

This article presents an automatic test pattern generation system based on both algebraic and topological techniques. Circuit partitioning, testability measures, 9-valued functions, pruning heuristics, and interactive fault simulation are employed to increase the performance of a modified version of the sequential D-Algorithm. Test generation results for someIscas'89 circuits are presented.Enrico Macii is also with Politecnico di Torino, Dip. di Automatica e Informatica, Torino, Italy 10129.     

An algebra of multiple faults in RAMs

Cell array faults in random-access memories (RAMs) are usually represented by Mealy automata. In such a model, multiple faults should also be representable by automata; in fact, it should be possible to compute the automaton representing a multiple fault from the automata representing the single faults that make up the multiple fault. In this paper we study properties of binary composition operations on automata that are appropriate for the representation of multiple faults in RAMs. First, we derive a set of generic conditions that every composition operation must satisfy. Second, we develop a set of physical conditions that the composition must satisfy in order to apply to stuck-at, transition and coupling faults in RAMs. Third, we represent the transition table rules used by van de Goor and Smit by a composition operation and prove that this operation satisfies both the generic and physical conditions. Fourth, we point out that in some circumstances, it is appropriate to use a different composition operation (defined by us in a previous paper) to permit a different handling of coupling faults in the presence of stuck-at or transition faults. We compare and relate the properties of the two algebras. This work was supported by the Natural Sciences and Engineering Research Council of Canada, Grants OGP0000871 and OGP0000243, and by a grant from the Information Technology Research Centre of Ontario. An extended summary of this paper appears in [1].     

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.     

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.     

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.     

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.     

神经网络在组合电路故障模拟测试生成算法中的应用

本文在基于故障模拟的测试生成算法基础上,提出了一种初始测试矢量的生成方法,即采用神经元网络模型来生成初始矢量,既避免了随机生成初始矢量的盲目性,又避免了确定性算法使用回溯所带来的大运算量。试验结果证明这种方法是有效的。     

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.     

On minimal set of test nodes for fault dictionary of analog circuit fault diagnosis

A method is proposed to obtain a minimal set of test nodes of an analog circuit for isolating all faulty conditions in the fault dictionary approach. Relevant theorem along with the proof is also given. Proposed method is extremely fast. This method is illustrated with an active filter circuit example.     

Efficient multiple path propagating tests for delay faults

This paper presents a test generation procedure for obtainingmaximal multiple-path-propagating robust tests, which detect the largest possible number of path faults simultaneously. Specialized heuristics are used to facilitate the generation of such tests in two-level circuits, and methods are given for extensions to multi-level circuits. Experimental results are presented to demonstrate the efficacy of this approach, which is seen to significantly reduce test-set lengths for path delay faults by generating highlyefficient robust tests. Limitations of the method are discussed, together with suggestions for future research.     

Dynamic effects in the detection of bridging faults in CMOS ICs

Dynamic effects in the detection of bridging faults in CMOS circuits are taken into account showing that a test vector designed to detect a bridging may be invalidated because of the increased propagation delay of the faulty signal. To overcome this problem, it is shown that a sequence of two test vectors < T ₀, T ₁ >, in which the second can detect a bridging fault as a steady error, can detect the fault independently of additional propagation delays if T₀ initializes the faulty signal to a logic value different from the fault-free one produced by T ₁. This technique can be conveniently used both in test generation and fault simulation. In addition, it is shown how any fault simulator able to deal with FCMOS circuits can be modified to evaluate the impact of test invalidation on the fault coverage of bridging faults. For any test vector, this can be done by checking the state of the circuit produced by the previous test vector.     

Extended selection of switching target faults in CONT algorithm for test generation

We describe an extended selection of switching target faults in the CONT algorithm. The main difficulty in test generation is the conflict that arises in the process of determining the signal values due to reconvergent fanouts. Conventional approaches for test generation change a signal value, which causes conflicts to another possible choice for backtracking. In the CONT algorithm, a strategy of switching target fault was proposed as a new backtracking mechanism. In this method, the target fault is switched to a new target fault instead of making an alternative assignment on the primary input value when a conflict occurs. A disadvantage of the CONT algorithm is that unjustified lines exist in the process of test generation. These unjustified lines make the procedure of switching targets complicated and restrict the possible choice in selecting the new target fault. In the new version of CONT, called CONT-2, we have removed the unjustified lines in the process of test generation and have extended to two target-fault types for switching targets. Implementing CONT-2 by a Fortran program, ISCAS85 benchmark circuits are examined. Experiments on a combined system with fault simulation followed by CONT-2 are also presented.     

Refresh re-use based transparent test for detection of in-field permanent faults in DRAMs

In this paper, a transparent test technique for testing permanent faults developed during field operation of DRAMs has been proposed. A three pronged approach has been taken in this work. First, a word oriented transparent March test generation algorithm has been proposed that avoids signature based prediction phase; next the proposed transparent March test is structured in a way that facilitates its implementation during refresh cycles of the DRAM; finally the on-chip refresh circuit is modified to allow its re-use during implementation of the proposed transparent March test on DRAM. Re-use of refresh cycles for test purpose ensures periodic testing of DRAM without interruption. Thus, faults are not allowed to accumulate. Moreover, wait for idle cycles of the processor to perform the test are avoided and test finishes within a definite time. Re-using the refresh circuit for test purpose overcomes requirement of additional Design-For-Testability hardware and brings down the area overhead.Both analytic predictions and simulation results for the method proposed here indicate real estate benefits and test time savings in comparison to other reported techniques. The proposed refresh re-use based transparent test technique provides a cost effective solution by providing facility for periodic tests of DRAM without requiring additional test hardware.     

The Coupling Model for Function and Delay Faults

We propose a high-level fault model, the coupling fault (CF) model, that aims to cover both functional and timing faults in an integrated way. The basic properties of CFs and the corresponding tests are analyzed, focusing on their relationship with other fault models and their test requirements. A test generation program COTEGE for CFs is presented. Experiments with COTEGE are described which show that (reduced) coupling test sets can efficiently cover standard stuck-at-0/1 faults in a variety of different realizations. The corresponding coupling delay tests detect all robust path delay faults in any realization of a logic function. This research was sponsored in part by the U.S. National Science Foundation under Grants No. CCR-9872066 and CCR-0073406. Joonhwan Yi received the B.S degree in electronics engineering from Yonsei University, Seoul, Korea, in 1991, and the M.S. and Ph.D degrees in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 1998 and 2002, respectively. From 1991 to 1995, he was with Samsung Electronics, Semiconductor Business, Korea, where he was involved in developing application specific integrated circuit cell libraries. In 2000, he was a summer intern with Cisco, Santa Clara, CA, where he worked for path delay fault testing. Since 2003, he has been with Samsung Electronics, Telecommunication Network, Suwon, Korea, where he is working on system-on-a-chip design. His current research interests include C-level system modeling for fast hardware and software co-simulation, system-level power analysis and optimization, behavioral synthesis, and high-level testing. John P. Hayes received the B.E. degree from the National University of Ireland, Dublin, and the M.S. and Ph.D. degrees from the University of Illinois, Urbana-Champaign, all in electrical engineering. While at the University of Illinois, he participated in the design of the ILLIAC III computer. In 1970 he joined the Operations Research Group at the Shell Benelux Computing Center in The Hague, where he worked on mathematical programming and software development. From 1972 to 1982 he was a faculty member of the Departments of Electrical Engineering– Systems and Computer Science of the University of Southern California, Los Angeles. Since 1982 he has been with the Electrical Engineering and Computer Science Department of the University of Michigan, Ann Arbor, where he holds the Claude E. Shannon Chair in Engineering Science. Professor Hayes was the Founding Director of the University of Michigan's Advanced Computer Architecture Laboratory (ACAL). He has authored over 225 technical papers, several patents, and five books, including Introduction to Digital Logic Design (Addison-Wesley, 1993), and Computer Architecture and Organization, (3rd edition, McGraw-Hill, 1998). He has served as editor of various technical journals, including the Communications of the ACM, the IEEE Transactions on Parallel and Distributed Systems and the Journal of Electronic Testing. Professor Hayes is a fellow of both IEEE and ACM, and a member of Sigma Xi. He received the University of Michigan's Distinguished Faculty Achievement Award in 1999 and the Humboldt Foundation's Research Award in 2004. His current teaching and research interests are in the areas of computer-aided design, verification, and testing; VLSI circuits; fault-tolerant embedded systems; ad-hoc computer networks; and quantum computing.