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

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

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.     

基于分布估计算法的组合电路测试生成

基于遗传算法生成的测试矢量集的故障覆盖率要低于确定性方法．本文分析指出造成这种现象的一个可能原因在于，组合电路测试生成过程中存在高阶、长距离模式，从而导致遗传算法容易陷人局部极值或早熟收敛．为此，本文首次提出使用分布估计算法生成测试矢量．该方法使用联合概率分布捕捉电路主输人之间的关联性。从而避免了高阶、长距离模式对算法的影响，缓解了算法早熟收敛问题．针对ISCAS-85国际标准组合电路集的实验结果表明，该方法能够获得较高的故障覆盖率．     

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.     

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.     

Design Error Diagnosis with Re-Synthesis in Combinational Circuits

A new approach is proposed for removing design errors from digital circuits, which does not use any error model. Based on a diagnostic pre-analysis of the circuit, a subcircuit suspected to be erroneous is extracted. Opposite to other known works, re-synthesis of the subcircuit need not be applied to the whole function of the erroneous internal signal in terms of primary inputs, it may stop at arbitrary nodes inside the circuit. As the subcircuits to be redesigned are kept as small as possible, the speed of the whole procedure of diagnosis and re-synthesis can be significantly increased. A formal algorithm is proposed for the whole procedure. Experimental data show the efficiency of the diagnostic pre-analysis.     

组合电路功能级测试生成的临界二元树方法

本文描述了电路基于呆滞型故障模型的功能级测试生成的概念及临界二元树用于功能级温度生成的方法，提出了一种新的临界输入动态识别方法，以求获得较小的ＣＢＴ规模，加速测试生成过程。     

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.     

Logic Design Validation via Simulation and Automatic Test Pattern Generation

We investigate an automated design validation scheme for gate-level combinational and sequential circuits that borrows methods from simulation and test generation for physical faults, and verifies a circuit with respect to a modeled set of design errors. The error models used in prior research are examined and reduced to five types: gate substitution errors (GSEs), gate count errors (GCEs), input count errors (ICEs), wrong input errors (WIEs), and latch count errors (LCEs). Conditions are derived for a gate to be testable for GSEs, which lead to small, complete test sets for GSEs; near-minimal test sets are also derived for GCEs. We analyze undetectability in design errors and relate it to single stuck-line (SSL) redundancy. We show how to map all the foregoing error types into SSL faults, and describe an extensive set of experiments to evaluate the proposed method. These experiments demonstrate that high coverage of the modeled errors can be achieved with small test sets obtained with standard test generation and simulation tools for physical faults.     

时序电路的模糊化测试生成算法

文章提出的模糊化的时序电路测试生成算法不明确指定故障点的故障值，它将故障值模糊化，并以符号表示。本算法第一阶段通过计算状态线和原始输出端的故障值来寻找测试矢量，通过计算故障点的正常值来 寻找测试矢量对应的故障类型；第二阶段用故障点的正常值作为约束条件计算故障点的另一个测试矢量。与传统的算法不同，它不需要回退和传播的过程。实验结果表明本算法具有较高的故障覆盖率和较少的测试时间。     

Fast Test Pattern Generation for Sequential Circuits Using Decision Diagram Representations

The paper presents a novel hierarchical approach to test pattern generation for sequential circuits based on an input model of mixed-level decision diagrams. A method that handles, both, data and control parts of the design in a uniform manner is proposed. The method combines deterministic and simulation-based techniques. On the register-transfer level, deterministic path activation is combined with simulation based-techniques used for constraints solving. The gate-level local test patterns for components are randomly generated driven by high-level constraints and partial path activation solutions. Experiments show that high fault coverages for circuits with complex sequential structures can be achieved in a very short time by using this approach.     

Resynthesis of Combinational Circuits for Path Count Reduction and for Path Delay Fault Testability

Path delay fault model is the most suitable model for detectingdistributed manufacturing defects which can cause delayfaults. However, the number of paths in a modern design can beextremely large and the path delay testability of many practicaldesigns is very low. In this paper we show how to resynthesize acombinational circuit in order to reduce the total number of paths inthe circuit. Our results show that it is possible to obtain circuitswith a significant reduction in the number of paths while notincreasing area and/or delay of the longest sensitizable path in thecircuit.Research on path delay testing shows that in many circuits a largeportion of paths does not have a test that can guarantee detection ofa delay fault. The path delay testability of a circuit would increaseif the number of such paths is reduced. We show that addition of asmall number of test points into the circuit can help reducing thenumber of such paths in the given design.     

Dynamic Fault Diagnosis of Combinational and Sequential Circuits on Reconfigurable Hardware

This article describes an emulation-based method for locating stuck-at faults in combinational and synchronous sequential circuits. The method is based on automatically designing a circuit which implements a closest-match fault location algorithm specialized for the circuit under diagnosis (CUD). This method allows designers to perform dynamic fault location of stuck-at faults in large circuits, and eliminates the need for large storage required by a software-based fault dictionary. In fact, the approach is a pure hardware solution to fault diagnosis. We demonstrate the feasibility of the method in terms of hardware resources and diagnosis time by experimenting with ISCAS85 and ISCAS89 circuits. The emulation-based diagnosis method speeds up the diagnosis process by an order of magnitude compared to the software-based fault diagnosis. This speed-up is important, especially, when the on-line diagnosis of safety–critical systems is of concern.

Test Generation for Crosstalk-Induced Faults: Framework and Computational Results

Due to technology scaling and increasing clock frequency, problems due to noise effects lead to an increase in design/debugging efforts and a decrease in circuit performance. This paper addresses the problem of efficiently and accurately generating two-vector tests for crosstalk induced effects, such as pulses, signal speedup and slowdown, in digital combinational circuits. These noise effects can propagate through a circuit and create a logic error in a latch or at a primary output. We have developed a mixed-signal test generator, called XGEN, that incorporates classical static values as well as dynamic signals such as transitions and pulses, and timing information such as signal arrival times, rise/fall times, and gate delay. In this paper we first discuss the general framework of the test generation algorithm followed by computational results. Comparison of results with SPICE simulations confirms the accuracy of this approach.     

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.     

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.     

"电路"试题库及试卷生成系统的研制

介绍了作者研制的“电路”试题库及试卷生成系统。该系统针对“电路”教学的特点,实现了由计算机辅助的、新的出卷方式,使“电路”教学有了更为客观的、考教分开的考核与评估方式。     

Generation and Verification of Tests for Analog Circuits Subject to Process Parameter Deviations

The paper presents a test stimulus generation and fault simulation methodology for the detection of catastrophic faults in analog circuits. The test methodology chosen for evaluation is RMS AC supply current monitoring. Tests are generated and evaluated taking account of the potential fault masking effects of process spread on the faulty circuit responses. A new test effectiveness metric of probability of detection is defined and the application of the technique to an analog multiplier circuit is presented. The fault coverage figures are therefore more meaningful than those obtained with a fixed threshold.     

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.