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

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

On the generation of test patterns for multiple faults

This article presents a new method to generate test patterns for multiple stuck-at faults in combinational circuits. We assume the presence of all multiple faults of all multiplicities and we do not resort to their explicit enumeration: the target fault is a single component of possibly several multiple faults. New line and gate models are introduced to handle multiple fault effect propagation through the circuits. The method tries to generate test conditions that propagate the effect of the target fault to primary outputs. When these conditions are fulfilled, the input vector is a test for the target fault and it is guaranteed that all multiple faults of all multiplicities containing the target fault as component are also detected. The method uses similar techniques to those in FAN and SOCRATES algorithms to guide the search part of the algorithm, and includes several new heuristics to enhance the performance and fault detection capability. Experiments performed on the ISCAS'85 benchmark circuits show that test sets for multiple faults can be generated with high fault coverage and a reasonable increase in cost over test generation for single stuck-at faults.     

采用基本门单元完全测试矢量的测试生成算法

文章介绍了一种采用基本逻辑门单元的安全测试矢量集生成测试矢量的方法，该方法可以将搜索空间限制在2(n 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.     

Partial scan design and test sequence generation based on reduced scan shift method

This paper presents a partial scan algorithm, calledPARES (PartialscanAlgorithm based onREduced Scan shift), for designing partial scan circuits. PARES is based on the reduced scan shift that has been previously proposed for generating short test sequences for full scan circuits. In the reduced scan shift method, one determines proch FFs must be controlled and observed for each test vector. According to the results of similar analysis, PARES selects these FFs that must be controlled or observed for a large number of test vectors, as scanned FFs. Short test sequences are generated by reducing scan shift operations using a static test compaction method. To minimize the loss of fault coverage, the order of test vectors is so determined that the unscanned FFs are in the state required by the next test vector. If there are any faults undetected yet by a test sequence derived from the test vectors, then PARES uses a sequential circuit test generator to detect the faults. Experimental results for ISCAS'89 benchmark circuits are given to demonstrate the effectiveness of PARES.     

An analytical approach to the partial scan problem

The scan design is the most widely used technique used to ensure the testability of sequential circuits. In this article it is shown that testability is still guaranteed, even if only a small part of the flipflops is integrated into a scan path. An algorithm is presented for selecting a minimal number of flipflops, which must be directly accessible. The direct accessibility ensures that, for each fault, the necessary test sequence is bounded linearly in the circuit size. Since the underlying problem is NP-complete, efficient heuristics are implemented to compute suboptimal solutions. Moreover, a new algorithm is presented to map a sequential circuit into a minimal combinational one, such that test pattern generation for both circuit representations is equivalent and the fast combinational ATPG methods can be applied. For all benchmark circuits investigated, this approach results in a significant reduction of the hardware overhead, and additionally a complete fault coverage is still obtained. Amazingly the overall test application time decreases in comparison with a complete scan path, since the width of the shifted patterns is shorter, and the number of patterns increase only to a small extent.     

A test set embedding approach based on twisted-ring counter with few seeds

Test data storage, test application time and test power dissipation increase dramatically for single stuck-at faults while tens of million gates are integrated in a System-on-a-Chip (SoC), which makes implementing fault testing for embedded cores based SoC become a challenging task. To further reduce test data storage, test application time and test power dissipation, this paper presents a new test set embedding approach based on twisted-ring counter (TRC) with few seeds. This approach includes two improvements. The first is that an efficient seed-selection algorithm is employed to exploit the high-density unspecified bits in the deterministic test set and so the test data storage for complete coverage of single stuck-at faults is minimized. The second is that a novel test-sequence-reduction scheme based on shifting seeds is proposed to reduce test application time that in turn reduces test power dissipation. Compared with the conventional approach, experiments on ISCAS’89 benchmark circuits show that the proposed approach requires 65% less test data storage, 68% shorter test application time and 67% less test power dissipation. Moreover, its hardware overhead is very small.     

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.     

一种基于故障特征分析的总线测试自适应算法

针对现有数字总线测试算法故障覆盖率低、效率不高、过程复杂等不足,建立了以区分主、从驱动器网络为特点的总线结构模型;在分析总线结构故障特征的基础上,定义了故障等价的概念,通过对故障模式的等价变换,得到了故障模式最简集合;最后提出了一种基于故障特征分析的自适应测试算法.结果表明,与同类算法相比,该算法在保证故障诊断最大化的前提下,简化了测试流程,降低了测试复杂性,缩减了测试序列长度;且设计简单,易于工程实现.     

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

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

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.     

A Heuristic Measure to Maximize Detected Faults per Test

In this paper we introduce a new measure for target fault selection and backtrace during test generation. The measure incorporates information on undetected faults and hence attempts to maximize the number of additional faults that may be detected by each test vector. Experimental results show the usefulness of this heuristic and demonstrate its superiority over the use of the SCOAP measure.     

State and Fault Information for Compaction-Based Test Generation

We present a new test generation procedure for sequential circuits using newly traversed state and newly detected fault information obtained between successive iterations of vector compaction. Two types of techniques are considered. One is based on the new states a sequential circuit is driven into, and the other is based on the new faults that are detected between consecutive iterations of vector compaction. These data modify an otherwise random selection of vectors, to bias vector sequences that cause the circuit to reach new states, and cause previously undetected faults to be detected. The biased vectors, when used to extend the compacted test set, provide a more intelligent selection of vectors. The extended test set is then compacted. Repeated applications of state and fault analysis, vector generation and compaction produce significantly high fault coverage using relatively small computing resources. We obtained improvements in terms of higher fault coverage, fewer vectors for the same coverage, or smaller number of iterations and time required, consistently for several benchmark circuits.     

Finite state machine synthesis with fault tolerant test function

According to a recent synthesis for testability proposal, a test function specified as a finite state machine with the same number of state variables as the given object machine, is incorporated into the state diagram prior to synthesis. Since a complete verification of the test machine is not practical, an often used heuristic sets and observes each state variable. The two machines share logic and a fault can result in partial or total loss of the test function. We show that the tests generated under the assumption that the entire test function is intact can become invalid. We propose a new method of synthesizing PLA-based finite state machines with fault tolerant test machines. Our approach eliminates testing of the test function. A constrained logic minimization phase insures that faults have predictable effect on the state diagram of the composite machine (object machine embedded with the test function). This allows effective use of the test function during test generation even in the presence of faults that effect both object and test machines. Only a combinational test generator is required for test generation. Each combinational vector is augmented by appropriate initialization and propagation sequences. Unlike prior approaches, ourO(log₂ n) length test sequence isguaranteed to detect any targeted crosspoint fault. Experimental results on the MCNC Logic Synthesis Workshop finite state machine benchmark set are given as evidence of practicality of the proposed approach.Supported by C&C Research Laboratories, NEC USA, during summer 1991.     

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.     

An Effective Test and Diagnosis Algorithm for Dual‐Port Memories

This paper proposes a test algorithm that can detect and diagnose all the faults occurring in dual‐port memories that can be accessed simultaneously through two ports. In this paper, we develop a new diagnosis algorithm that classifies faults in detail when they are detected while the test process is being developed. The algorithm is particularly efficient because it uses information that can be obtained by test results as well as results using an additional diagnosis pattern. The algorithm can also diagnose various fault models for dual‐port memories.     

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.     

Testing VLSI regular arrays

In recent years the concept of Design for Test—whereby the designer is forced to comply with a specific test style—has become very popular. However, the most effective custom VLSI architectures available all have their own very strongly defined structure. Therefore, test strategies are required which exploit the typical hierarchy in the design. Exploiting this hierarchy implies a test philosophy which requires the minimum addition of extra test logic and utilizes the hierarchy of the design. A popular VLSI architecture is a systolic array which consists of a regular array of small processing elements with timing latches on the communication lines. In this case we can exploit the regularity for test purposes; in this paper we show how to do this by adopting a divide and conquor method. This can be done by generating test vectors for a single processing element, using the most appropriate fault model. The regularity of the array facilitates the propagation of these vectors to every other processing element in the array. The propagation method must also allow for the propagation of the fault effects from the output of each processing element to the boundary of the array where the fault can be observed. The proposed test method presented in this paper takes the vectors required to test a single processing element, and determines test vectors for the whole array. This method is applicable to all types of regular arrays, but in particular, systolic arrays, where we have the added problem of circuit timing. Each separate signal direction is first analyzed for its test vector and fault effect propagation properties. Then, using the array Data Dependence Graph, which represents the propagation of data through the array, the combined effect of all signals on test vector and fault effect propagation can be considered. This reduces the task of determining the array inputs to a pattern matching problem suitable for computer implementation. The test method is applied to three different arrays to illustrate how different array types can be tested.