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.     

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.     

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.     

Self-test of sequential circuits with deterministic test pattern sequences

This article describes a new approach for synthesizing a cost-efficient self-test hardware for a given set of deterministic test pattern sequences. To minimize the test hardware effort instead of all the test sequences, only a very small subset will be selected such that a simple generation of all necessary test sequences will be ensured. This procedure drastically decreases the storage requirements (about 80%) and therefore distinctly reduces the necessary test hardware overhead. Experimental results on the ISCAS-S-benchmarks emphasize the efficiency of our approach.This work is supported by the ESPRIT project 6855 (LINK).     

Differential fault simulation for sequential circuits

A new fast fault simulation algorithm called differential fault simulation, DSIM, for synchronous sequential circuits is described. Unlike concurrent fault simulation, for every test vector, DSIM simulates the good machine and each faulty machine separately, one after another, rather than simultaneously simulating all machines. Therefore, DSIM dramatically reduces the memory requirement and the overhead in the memory management in concurrent fault simulation. Also, unlike serial fault simulation, DSIM simulates each machine by reprocessing its differences from the previously simulated machine. In this manner, DSIM is more efficient than serial fault simulation. Experiments have shown that DSIM runs 3 to 12 times faster than an existing concurrent fault simulator. In addition, owing to the simplicity of this algorithm, DSIM is very easy to implement and maintain. An implementation consists of only about 300 lines of C language statements added to the event-driven true-value simulator in an existing sequential circuit test generator program, STG3. Currently DSIM uses the zero-delay timing model. The addition of alternative delay models is under development.     

FsmTest: Functional test generation for sequential circuits

This paper presents a new approach to test pattern generation for sequential circuits modeled as finite state machines. This approach is well suited for controller synthesis, because such devices are usually represented as explicit finite state machines. Based on a functional fault model, only a restricted set of transitions of the finite state machine (FSM) is considered for the purpose of testing. A new state discriminating sequence, referred to as EUIO is proposed. Overlapping is accomplished to reduce the test length. In most cases, test length and CPU time requirements are substantially lower compared with gate-level ATPGs. Techniques are also introduced to preserve a high fault coverage. Evaluation on MCNC benchmarks has shown the effectiveness of the test algorithm both at functional and gate levels, while achieving in most cases 100% coverage of single stuck-at faults.     

A UNIFIED THEORY FOR DESIGNING ANDANALYZING BOTH SYNCHRONOUS AND ASYNCHRONOUS SEQUENTIAL CIRCUITS

The paper discusses general expressions of the clock signal and the next state equations containing the clock signal for flip-flops, and based on it, a unified theory for designing and analyzing both synchronous and asynchronous sequential circuits is proposed. The theory is proved effective by practical examples.     

A novel test optimizing algorithm for sequential fault diagnosis

Once all available measurements are determined, the highest testability index of a complex system is determined. To achieve such highest index with the lowest test cost, AND/OR graph search algorithms were developed for years to determine an optimal or near-optimal test sequence. However, in most cases, achieving the highest testability index induces extremely high test cost. The purpose of this paper is to optimize test set and test sequence so as to cut down the test cost while keeping the required, not necessarily the highest, FIR (Fault Isolation Rate) satisfied. Traditionally, this is an NP-Complete problem, which makes the computation of optimal test set impractical for even the moderate-sized model. In this paper, a greedy method is proposed to get the optimized test set. Then, we combine the greedy method with discrete binary particle swarm optimization (DPSO) to construct a test sequential tree. With the specified FIR requirement satisfied, the lowest test cost is achieved. The proposed algorithms are illustrated and tested in a range of real-world systems. The effectiveness and accurateness of the proposed algorithm is verified by computational results.     

模拟集成电路模块版图的生成系统

介绍了模拟集成电路模块版图的开发系统.系统用高效的过程化版图描述语言构造模拟模块,编译产生与工艺及应用无关的模块版图生成器.系统的网络识别和模块内布线功能自动完成模块网络的完全连通,基于优选的电气特性驱动版图生成,提高设计可靠性.该系统已辅助设计出多个高性能集成运算放大器、模拟开关等芯片版图.     

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 new DFT methodology for sequential circuits

This paper introduce a new design for testability methodology for sequential circuits based on input/output pin utilization which exploits the possibility of applying test patterns in parallel. The goal is to reduce the test application time maintaining the same fault coverage as the one obtained using full scan. The proposed procedure includes necessary and sufficient conditions which are easily incorporated in a design system and produce the required implementation. Successful experimental results are presented on benchmark circuits:IC test length is reduced on an average by 44% of full scan.This work is partly supported by research grants from the Natural Sciences and Engineering Research Council of Canada and equipment grants from the Canadian Microelectronics Corporation.     

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

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

A structure and technique for pseudorandom-based testing of sequential circuits

Presented is a register structure and generator design which enables non-scan sequential testing using parallel pseudorandom-based patterns applied to the circuit's primary inputs. The proposed register structure and register control strategy uses the circuit under test's (CUT's) natural sequential activity to periodically alter a register's output bias to a value near 0.5 (i.e. alter the spread of 1's in the output stream). Thus, over time, it is possible to introduce a larger spread circuit states than that normally reachable when parallel pseudorandom-based test patterns are applied to the input lines of a CUT. Using the register modification, a simple hardware generation system can be designed and is suitable for both on-chip and external testing. Experiments indicate that high fault coverage is attainable in a relatively short test time.     

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

基于SAT的组合电路自动测试向量生成

实现了基于可满足性(SAT)求解的方法,以解决固定型和时延故障的自动测试向量生成问题.详细讨论了如何利用电路的拓扑结构以及从ATPG到合取范式(CNF)的编码方法.CNF被输入到一个高效的SAT求解器zchaff中求解.在ISCAS85测试实例中验证了该算法的有效性.