Advanced fault collapsing [logic circuits testing]

The partitioning of faults into equivalence classes so that only one representative fault per class must be explicitly considered in fault simulation and test generation, called fault collapsing, is addressed. Two types of equivalence, which are relevant to the work reported, are summarized. New theorems on fault equivalence and dominance, forming the basis of an algorithm that collapses all the structurally equivalent faults in a circuit, plus many of the functionally equivalent faults, are presented. Application of the algorithm to a set of benchmark circuits establishes that identification of functionally equivalent faults is feasible, and that, in some cases, they are a large fraction of the faults in a circuit. The collapsing algorithm applies not only to combinational designs but to synchronous sequential circuits as well     

A New Classification of Path-Delay Fault Testability in Terms of Stuck-at Faults

A new classification of path-delay fault testability in a combinational circuit is presented in terms of testability of stuck-at faults in an equivalent circuit. Earlier results describing correlation of path-delay and stuck-at faults are either incomplete, or use a complex model of equivalent circuit based on timing parameters. It is shown here that a path-delay fault (rising or falling) is testable if and only if certain single or multiple stuck-at fault in the equivalent circuit is testable. Thus, all aspects of path-delay faults related to testability under various classification schemes can be interpreted using the stuck-at fault model alone. The results unify most of the existing concepts and provide a better understanding of path-delay faults in logic circuits.     

一种组合电路内建自测试的改进方法

对组合电路的测试提出了一种将确定性测试生成方法与内建自测试相结合的设计方案;设计实现了利用D算法生成的测试矢量和伪随机测试序列生成电路共同构成测试矢量生成模块,利用内建自测试方法完成可测性设计,并将两者结合得出组合电路内建自测试的改进方法;分析与实验结果表明,该方法能减少系统硬件占用,同时具有测试向量少、故障覆盖率高的特点。     

基于电路拓扑结构分析的等价性验证方法

随着集成电路设计规模的日益增大,结合多种推理引擎已成为组合电路形式化等价性验证的重要手段.提出一种基于电路拓扑结构分析的组合等价性验证方法,将电路的拓扑结构与验证算法的复杂性关联起来.在验证过程开始之前,利用min-cut方法计算表征电路复杂性的"电路宽度",以确定最佳的推理引擎,避免了传统的引擎切换过程,提高了算法的效率.针对ISCAS85电路的实验结果表明了该方法的效率和可行性.     

Near-minimal test sets for the detection of single gate faults

A new algorithm is presented for the detection of single gate faults in combinational networks. A gate fault is any unknown transformation of the Boolean function realized by a particular gate or single-output subnetwork. Detection of such faults is accomplished by verifying the truth table of the correct gate function.The concept of real transform of a Boolean function is utilized to obtain in each iteration an optimal test, namely, a test that performs as much of the fault detection task as possible. The resulting test set is near-minimal and complete.The algorithm can handle multi-output networks, integrated network components and mixed (gate, stuck-at) fault models.     

A generalized fault simulator for combinational logic circuits

A generalized approach to the design of fault simulator using a library of simulation primitives is presented in this paper. A comprehensive set of simulation primitives has been developed using C programming language on the IBM PC. This library of simulation primitives has been used in realizing a fault simulator for automatic test pattern generation in combinational logic circuits. The fault simulator employs a combination of random pattern generation, concurrent fault simulation and the FAN algorithm for generating the complete set of test vectors to cover all the faults in the fault dictionary of the circuit under test. The library of simulation primitives is general enough to facilitate the development of fault simulators using any other test algorithms such as DALG or PODEM.     

基于混沌搜索的数字电路多故障测试生成

针对数字电路中多故障测试生成较难的问题,本文提出了基于混沌搜索的数字电路多故障测试生成算法。该算法先把多故障转换成为单故障,再用神经网络的方法对单故障电路构造故障的约束网络,最后用混沌搜索方法求解故障约束网络能量函数的最小值点获得原电路中多故障的测试矢量。在一些国际标准电路上的实验结果表明了本算法的可行性。     

Built-in self-test of a CMOS ALU

A technique is proposed for implementing BIST (built-in self-test) in a CMOS arithmetic and logic unit (ALU). The approach covers single stuck-open faults and all functional faults that do not induce memory effects. The specific fault set covered by the test includes: (1) all single stuck-open faults on n and p transistors anywhere in the ALU (F1 faults); and (2) all functional faults that affect any single-bit slice of the (F2 faults), a functional fault being any fault that changes one combinational function into another. Functional faults in multiple slices are also detectable, as long as they do not generate identical responses in all even-numbered or odd-numbered ALU slices. With common techniques for test vector generation and response-verification, this BIST implementation provides higher fault coverage with only a small increase in surface area     

组合电路测试生成的任意路径敏化法

本文阐述了基于布尔函数的组合电路测试生成方法,给出了测试生成的基本运算规则及测试生成的算法－任意路径敏化法,该算法适用于布尔函数的任何表示形式,与基于布尔函数的其它算法相比,该算法不用复杂的布尔运算。只须按给出的规则作简单的判断和计算就可以生成给定邦联伯测试码,因而计算工作要小得多,该算法用于大型组合电路的测试生成,可以增加扇出分支处的一敏化条件。减少信号冲突和回溯次数。大大加快了大规模组合电路以及印制电路板的测试生成速度。     

Fault diagnosis in reversible circuits under missing-gate fault model

This article presents a novel technique for fault detection as well as fault location in a reversible combinational circuit under the missing gate fault model. It is shown that in an (n × n) reversible circuit implemented with k-CNOT gates, addition of only one extra control line along with duplication each k-CNOT gate, yields an easily testable design, which admits a universal test set (UTS) of size (n + 1) that detects all single missing-gate faults (SMGFs), repeated-gate faults (RGFs), and partial missing-gate faults (PMGFs) in the circuit. Furthermore, storage of only one vector (seed) of the UTS is required; the rest can be generated by n successive cyclic bit-shifts from the seed. For fault location under the SMGF model, a technique for identifying the faulty gate is also presented that needs application of a single test vector, provided the circuit is augmented with some additional observable outputs.     

电气设备故障的类型及产生原因

分析了电气设备及线路故障的类型和产生原因等,包括短路及断路故障,漏电故障,变质故障。电气设备的发热、电动力、电弧、电接触以及环境因素等均能导致电气故障的产生,从而影响电气设备的正常运行。     

Retiming synchronous circuitry

This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦V∥E¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.     

Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method

Using the semi-tensor product method, this paper investigates the Boolean derivative calculation with application to fault detection of combinational circuits, and presents a number of new results. First, a new set of formulas is obtained to calculate the Boolean derivative by the semi-tensor product method. Then, the obtained new results are applied to detecting the multiple faults of combinational circuits, and a new detection method is proposed. Finally, two illustrative examples are studied by using the results obtained in this paper. The study of illustrative examples shows that the new detection method can be used for detection of more than two faults effectively.     

Iterative Learning Fault Diagnosis Algorithm for Non-uniform Sampling Hybrid System

For a class of non-uniform output sampling hybrid system with actuator faults and bounded disturbances, an iterative learning fault diagnosis algorithm is proposed. Firstly, in order to measure the impact of fault on system between every consecutive output sampling instants, the actual fault function is transformed to obtain an equivalent fault model by using the integral mean value theorem, then the non-uniform sampling hybrid system is converted to continuous systems with timevarying delay based on the output delay method. Afterwards, an observer-based fault diagnosis filter with virtual fault is designed to estimate the equivalent fault, and the iterative learning regulation algorithm is chosen to update the virtual fault repeatedly to make it approximate the actual equivalent fault after some iterative learning trials, so the algorithm can detect and estimate the system faults adaptively. Simulation results of an electro-mechanical control system model with different types of faults illustrate the feasibility and effectiveness of this algorithm.      

Detection of all single and multiple stuck-at faults in combinational digital circuits using index vector testing

A new method for the testing of combinational digital circuits is presented. The method is based on the concept of the ‘index vector’ of a switching function (Gupta 1987), and represents an extension of syndrome testing. A large percentage of syndrome untestable faults are found to be index vector testable. An approach to testing index vector untestable circuits that relies only on the function realized by the circuit and is independent of the circuit topology is presented. The method can be used for the detection of both single and multiple stuck-at faults in a combinational circuit.     

Designing CMOS Circuits for Switch-Level Testability

Conventional testing techniques often fail to be effective for CMOS combinational circuits, since most of their switch-level faults cannot be detected by stuck-at-fault testing. The alternative is to design for testability. The design techniques presented here for fully testable CMOS combinational circuits use a three-pattern test scheme to detect both stuck-open and stuck-on switch-level faults. The circuit is implemented with specially designed gates that have no undetectable stuck-on faults. An inverting buffer is inserted between logic gates, and two FETs are added to each logic gate to make it testable for stuck-on faults.     

一个实用化的测试产生系统COMPA—ATPG

本文介绍了一个在康发工作站实现的测试产生系统COMPA-ATPGS。该系统以FAN算法为基础,通过对电路结构分析来产生组合电路的测试码,进而帮助设计者产生整个电路的测试码。实验证明,该系统对组合电路的故障覆盖率可达90％以上。     

Graph-based evolutionary design of arithmetic circuits

We present an efficient graph-based evolutionary optimization technique, called evolutionary graph generation (EGG), and the proposed approach is applied to the design of combinational and sequential arithmetic circuits based on parallel counter-tree architecture. The fundamental idea of EGG is to employ general circuit graphs as individuals and manipulate the circuit graphs directly using new evolutionary graph operations without encoding the graphs into other indirect representations, such as the bit strings used in genetic algorithm (GA) proposed by Holland (1992) and trees used in genetic programming (GP) proposed by Koza et al. (1997). In this paper, the EGG system is applied to the design of constant-coefficient multipliers and the design of bit-serial data-parallel adders. The results demonstrate the potential capability of EGG to solve the practical design problems for arithmetic circuits with limited knowledge of computer arithmetic algorithms. The proposed EGG system can help to simplify and speed up the process of designing arithmetic circuits and can produce better solutions to the given problem     

利用FAN算法进行组合电路的等价性检验*

讨论了组合电路的等价性检验方法,分析了FAN算法的关键技术。利用该算法进行了组合电路的等价性检验,实验结果表明了该方法的有效性。