A Binary Decision Diagram based on-line testing of digital VLSI circuits for feedback bridging faults

Classical manufacturing test verifies that a circuit is fault free during fabrication, however, cannot detect any fault that occurs after deployment or during operation. As complexity of integration rises, frequency of such failures is increasing for which on-line testing (OLT) is becoming an essential part in design for testability. In majority of the works on OLT, single stuck at fault model is considered. However in modern integration technology, single stuck at fault model can capture only a small fraction of real defects and as a remedy, advanced fault models such as bridging faults, transition faults, delay faults, etc. are now being considered. In this paper we concentrate on bridging faults for OLT. The reported works on OLT using bridging fault model have considered non-feedback faults only. The basic idea is, as feedback bridging faults may cause oscillations, detecting them on-line using logic testing is difficult. However, not all feedback bridging faults create oscillations and even if some does, there are test patterns for which the fault effect is manifested logically. In this paper it is shown that the number of such cases is not insignificant and discarding them impacts OLT in terms of fault coverage and detection latency. The present work aims at developing an OLT scheme for bridging faults including the feedback bridging faults also, that can be detected using logic test patterns. The proposed scheme is based on Binary Decision Diagrams, which enables it to handle fairly large circuits. Results on ISCAS 89 benchmarks illustrate that consideration of feedback bridging faults along with non-feedback ones improves fault coverage, however, increase in area overhead is marginal, compared to schemes only involving non-feedback faults.     

Design error diagnosis in digital circuits with stuck-at fault model

In this paper we describe in detail a new method for the single gate-level design error diagnosis in combinational circuits. Distinctive features of the method are hierarchical approach (the localizing procedure starts at the macro level and finishes at the gate level), use of stuck-at fault model (it is mapped into design error domain only in the end), and design error diagnostic procedure that uses only test patterns generated by conventional gate-level stuck-at fault test pattern generators (ATPG). No special diagnostic tests are used because they are much more time consuming. Binary decision diagrams (BDD) are exploited for representing and localizing stuck-at faults on the higher signal path level. On the basis of detected faulty signal paths, suspected stuck-at faults at gate inputs are calculated, and then mapped into suspected design error(s). This method is enhanced compared to our previous work. It is applicable to redundant circuits and allows using incomplete tests for error diagnosis. Experimental data on ISCAS benchmark circuits shows the advantage of the proposed method compared to the known algorithms of design error diagnosis.     

A Classical Parameter Identification Method and?a?Modern Test Generation Algorithm

Many methods have been presented for the testing and diagnosis of analog circuits. Each of these methods has its advantages and disadvantages. In this paper we propose a novel sensitivity analysis algorithm for the classical parameter identification method and a continuous fault model for the modern test generation algorithm, and we compare the characteristics of these methods. At present, parameter identification based on the component connection model (CCM) cannot ensure that the diagnostic equation is optimal. The sensitivity analysis algorithm proposed in this paper can choose the optimal set of trees to construct an optimal CCM diagnostic equation, and enhance the diagnostic precision. But nowadays increasing attention is being paid to test generation algorithms. Most test generation algorithms use a single value in the fault model. But the single values cannot substitute for the actual faults that may occur, because the possible faulty values vary over a continuous range. To solve this problem, this paper presents a continuous fault model for the test generation algorithm which has a continuous range of parameters. The test generation algorithm with this model can improve the treatment of the tolerance problem, including the tolerances of both normal and faulty parameters, and enhance the fault coverage rate. The two methods can be applied in different situations.     

Performance analysis and fault tolerance of randomized routing on Clos networks

Beside universality and very low latency, Youssef's randomized self-routing algorithms [25] have high tolerance for multiple faults and more strikingly have the potential for fault tolerance without diagnosis. In this paper we study the performance of Youssef's routing algorithms for faulty Clos networks in the presence of multiple faults in multiple columns with and without fault detection. We show that with fault detection and diagnosis, randomized routing algorithms provide scalable, very efficient and fault tolerant routing mechanisms. Without fault detection and diagnosis, randomized routing provides good fault tolerance for faulty switches in either the first or the second column. The delays become large for faults in the third column or for faults in more than one column. In conclusion, randomized routing enables the system to run without periodic fault detection/diagnosis, and if and when the performance degrades beyond a certain threshold, diagnosis can be performed to improve the routing performance. This revised version was published online in June 2006 with corrections to the Cover Date.     

Functional fault models for non-scan sequential circuits

The paper presents two functional fault models that are applied for functional delay test generation for non-scan synchronous sequential circuits: the pin pair state (PPS) fault model and the pin pair full state (PPFS) fault model. The PPS fault model deals with the pairs of stuck-at faults on the primary inputs and the primary outputs, as well as, with the pairs of stuck-at faults on the previous state bits and the primary outputs. The PPFS fault model encompasses the PPS model, and additionally deals with the pairs of stuck-at faults on the primary inputs and the next state bits, as well as, with the pairs of stuck-at faults on the previous state bits and the next state bits. The main factor in assessing the quality of obtained test sequences was the transition fault coverage at the gate level of the selected according to the appropriate fault model test sequences from the generated randomly ones. The experimental results demonstrate that the implementation using presented functional fault models allow selecting the test sequences from the initial test set without the loss of transition fault coverage in many cases, and the number of the selected test sequences is much lesser than that of the initial test set. This result demonstrates that the functional delay test can be generated using the presented functional delay fault models before structural synthesis of the circuit.     

Test Generation Algorithm for Linear Systems Based on Genetic Algorithm

This paper proposes a test generation algorithm combining genetic algorithm for fault diagnosis on linear systems. Most test generation algorithms just used a single value fault model. This test generation algorithm is based on a continuous fault model. This algorithm can improve the treatment of the tolerance problem, including the tolerances of both normal and fault parameters, and enhance the fault coverage rate. The genetic algorithm can be used to choose the characteristic values. The genetic algorithm can enhance precision of test generation algorithm especially for complex fitness functions derived from complex systems under test. The genetic algorithm can also further improve the fault coverage rate by reducing the loop number of divisions of the initial fault range. The experiments are carried out to show this test generation algorithm with a linear system and an integrated circuit.     

Robust diagnosis to measurement uncertainties using bond graph approach: Application to intelligent autonomous vehicle

This paper deals with robust bond graph model-based fault detection and isolation to improve the robustness of the diagnosis system in presence of measurements and parameters uncertainties. We develop a procedure of measurement uncertainties modeling directly on the graph. By using the structural and causal properties of the bond graph, the robust diagnosis is performed. The interest of the developed methodology consists in using the graphical tool not only for measurement uncertainties modeling, but also for designing robust fault detection and isolation algorithms. Moreover, this method can be easily automated. The developed approach is validated by an application to an electromechanical traction system of intelligent autonomous vehicle.     

Delay fault testing using partial multiple scan chains

Delay test patterns can be generated at the functional level of the circuit using a software prototype model, when the primary inputs, the primary outputs and the state variables are available only. Functional delay test can be constructed for scan and non-scan sequential circuits. Functional delay test constructed using software prototype model can detect transition faults at the structural level quite well. Therefore, we propose a new iterative functional test generation approach. The proposed approach involves a partial multiple scan chain construction using the results of functional delay test generation at a high level of abstraction. The iterativeness of the method allows finding the compromise between the test coverage, hardware overhead and test length. Furthermore, using the partial multiple scan chains requires less hardware overhead resulting in shorter test application times. The experimental results are provided for the ITC’99 benchmark circuits. Experiments showed that the obtained transition fault coverage is on average 2% higher than using full scan and commercial automatic test pattern generator for transition faults.     

Bridging Faults in Pipelined Circuits

This paper analyzes the detectability of resistive bridging faults in CMOS (micro)-pipelined circuits. Logic and electrical level detection conditions are provided for functional and I _ddq testing techniques. The kind of operations and the sensitivity to dynamic fault effects of pipelined circuits make such conditions more complex than in the combinational case. In particular, it is shown that the kind of used latches has a relevant impact on fault coverage, and should be carefully accounted in test generation and fault simulation. Finally, guidelines are drawn for the extension of combinational test generation and fault simulation algorithms to the considered case.     

The effects of transistor source-to-gate bridging faults in complexCMOS gates

A study of the effect of gate-to-source bridging faults in the pull-up section of a complex CMOS gate is presented. The manifestation of these faults depends on the resistance value of the connection causing the bridging. It is shown that such faults manifest themselves either as stuck-at or stuck-open faults and can be detected by tests for stuck-at and stuck-open faults generated for the equivalent logic current. It is observed that for transistor channel lengths larger than 1 μm there exists a range of values of the bridging resistance for which the fault behaves as a pseudo-stuck-open fault     

Fault detection in programmable logic arrays

When designing fault-tolerant systems including programmable logic arrays (PLAs), the various aspects of these circuits concerning fault diagnosis have to be taken into account. The peculiarity of these aspects, ranging from fault models to test generation algorithms and to self-checking structures, is due to the regularity of PLAs. The fault model generally accepted for PLAs is the crosspoint defect; it is employed by dedicated test generation algorithms, based on the fact that PLAs implement a two-level combinational function. The problem of accessing inputs and outputs of the PLA can be alleviated by augmenting the PLA itself so as to simplify the test vectors to be applied, making them function independent in the limit. A further step consists in the addition of the circuitry required to generate test vectors and to evaluate the answer, thus obtaining a built-in self-test (BIST) architecture. Finally, high reliability can be achieved with PLAs featuring concurrent error detection.     

Guaranteed fault detection sequences for single transition faults in finite state machine models using concurrent fault simulation

This paper presents a new algorithm for the generation of test sequences for finite state machines. Test sequence generation is based on the transition fault model, and the generation of state-pair distinguishing sequences. We show that the use of state-pair distinguishing sequences generated from a fault-free finite state machine will remain a distinguishing sequence even in the presence of a single transition fault, thus guaranteeing complete single transition fault coverage. Analysis and experimental results show that the complexity of the test sequence generation algorithm is less than those of the previous algorithms. The utility of the transition fault model, and the generated test sequences is shown by their application to sequential logic circuits. These results show more than a factor of 10 improvement in the test generation time and some reduction in test length while maintaining 100% transition fault coverage.Now with Intel Corporation, FM5-161, 1900 Prairie City Road, Folsom, CA 95630.Now with Chrysalis Symbolic Design, 101 Billerica Ave., North Billerica, MA 01862.     

Defect Simulation Methodology for iDDT Testing

The International Technology Roadmap for Semiconductors (ITRS) identifies two main challenges associated with the testing of manufactured ICs. First, the increase in complexity of semiconductor manufacturing process, physical properties of new materials, and the constraints imposed by resolution of lithography techniques etc., give rise to more complex failure mechanisms and hard-to-model defects that can no longer be abstracted using traditional fault models. Majority of defects, in today's technology, include resistive bridging and open defects with diverse electrical characteristics. Consequently, conventional fault models, and tools based on these models are becoming inadequate in addressing defects resulting from new failure mechanisms. Second, the defect detection resolution of main-stream I_DDQ testing is challenged by significant elevation in off-state quiescent current and process variability in newer technologies. Overcoming these challenges demands innovative test solutions that are based on realistic fault models capable of targeting real defects and thus, providing high defect coverage. In prior works power supply transient current or i_DDT testing has been shown to detect resistive bridging and open defects. The ability of transient currents to detect resistive opens and their insensitivity (virtually) to increase in static leakage current make i_DDT testing all the more attractive. However, in order to integrate i_DDT based methods into production test flows, it is necessary to develop a fault simulation strategy to assess the defect detection capability of test patterns and facilitate the ATPG process. The analog nature of the test observable, i.e., i_DDT signals, entail compute intensive transient simulations that are prohibitive. In this work, we propose a practical fault simulation model that partitions the task of simulating the DUT (device under test) into linear and non-linear components, comprising of power/ground-grid and core-logic, respectively. Using divide-and-conquer strategy, this model replaces the transient simulations of power/ground-grid with simple convolution operations utilizing its impulse response characteristics. We propose a path isolation strategy for core-logic as a means of reducing the computational complexity involved in deriving i_DDT signals in the non-linear portion. The methodology based on impulse response functions and isolated path simulation, can enable i_DDT fault simulation without having to simulate the entire DUT. To our knowledge, no practical technique exists to perform fault simulation for i_DDT based methods. The proposed fault simulation model offers two main advantages, first, it allows fault induction at geometric or layout level, thus providing a realistic representation of physical defects, and second, the current/voltage profile of power/ground-grid, derived for i_DDT fault simulation, can be used to perform accurate timing verification of logic circuit, thus facilitating design verification. In summary, the proposed fault simulation framework not only enables the assessment of defect detection capabilities of i_DDT test methodologies, but also establishes a platform for performing defect-based testing on practical designs.     

Defect-oriented testability for asynchronous ICs

For a CMOS manufacturing process, asynchronous ICs are similar to synchronous ICs. The defect density distributions are similar, and hence, so are the fault models and fault-detection methods. So, what makes us think that asynchronous circuits are much harder to test than synchronous circuits? Because the effectiveness of best known test methods for synchronous circuits drops when applied to asynchronous circuits? They may very well be a temporal hurdle. Many test methods have already been reevaluated and successfully adapted from the synchronous to the asynchronous test domain. The paper addresses one of the final hurdles: I_DDQ testing. This type of test method, based on measuring the quiescent power supply current, is very effective for detecting (resistive) bridging faults in CMOS circuits. Detection of bridging faults is crucial, because they model the majority of today's manufacturing defects. I_DDQ fault effects are sensitized in a particular state or set of states and can only be detected if we stop the circuit operation right there. This is a problem for asynchronous circuits, because their operation is self-timed. In the paper, we quantify the impact of self timing on the effectiveness of I_DDQ -based test methods for bridging faults, and propose a Design-for-Test (DfT) approach to develop a low-cost DfT solution. For comparison, we do the same for logic voltage testing and stuck-at faults. The approach is illustrated on circuits from Tangram, the asynchronous design-style employed at Philips Research, but it is applicable to asynchronous circuits in general     

Real Time Fault Diagnosis with Tests of Uncertain Quality for Multimode Systems and its Application in a Satellite Power System

Dynamic fault diagnosis must consider complex fault situations such as fault evolution, coupling, unreliable tests and so on. Previous dynamic fault diagnostic models and inference algorithms are mainly designed for the steady state systems, which are not suitable for the multimode systems. In this paper, a time varying dynamic model to solve the multimode fault diagnosis problem is proposed. Its structure and formulation are presented. Fault diagnosis based on this model is realized by means of inference calculation given the test result, which is formulated as an optimization problem. A new algorithm to solve this problem is proposed. Simulation experiments on different scenarios are carried out to validate the model and the algorithm. As an example, the case of a satellite electrical power system is studied in detail. Both the simulation result and the application result show that the method proposed in this paper can be used to solve the dynamic fault diagnosis problem for multimode systems considering the complex circumstances such as uncertain tests and system delay.     

Efficient probe selection algorithms for fault diagnosis

Increase in the network usage for more and more performance critical applications has caused a demand for tools that can monitor network health with minimum management traffic. Adaptive probing has the potential to provide effective tools for end-to-end monitoring and fault diagnosis over a network. Adaptive probing based algorithms adapt the probe set to localize faults in the network by sending less probes in healthy areas and more probes in the suspected areas of failure. In this paper we present adaptive probing tools that meet the requirements to provide an effective and efficient solution for fault diagnosis for modern communication systems. We present a system architecture for adaptive probing based fault diagnosis tool and propose algorithms for probe selection to perform failure detection and fault localization. We compare the performance and efficiency of the proposed algorithms through simulation results.     

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.     

Diagnosis of Boards for Realistic Interconnect Shorts

Original algorithms and tools for generating diagnostic test setsfor board interconnect shorts, and assessing their diagnostic resolution areproposed. The test sets are derived from a representation of realisticshorts, extracted from the board layout. Diagnostic resolution isstatistically evaluated by simulating diagnosis of a sample of realisticshorts. The overall methodology is based on a new theoretical framework thataccounts for the probabilities of shorts, according to their multiplicityand possible logic behaviour. Results on real board layouts show that,compared to the traditional schemes, our test sets have higher diagnosticresolution, shorter test vectors, and can be produced efficiently.     

Probe generation for active probing

Active probing is a widely adopted approach for developing effective solutions for network monitoring and diagnosing. However, the use of probing techniques incurs costs in terms of additional network traffic. Furthermore, probing stations are required to be configured and maintained in the network for sending out probes. The set of probes used for fault detection and/or diagnosis (called the target probe set) is selected by a probe selection algorithm from a larger set called the candidate probe set. Most of the existing techniques for selecting the target probe set assume that the candidate probe set will preexist and the set is determined by the configured routing model in the network. In this paper, we address the problem of generating an expanded candidate probe set, which results in the selection of a more efficient target probe set. We propose the use of heuristics and network partitioning strategies for generating the candidate probe set. For evaluating our approach, we perform experiments to generate candidate probe sets for the networks of several types and sizes. The candidate probe sets are used by the existing probe selection algorithms for selecting target probe sets for fault detection and localization. Our results demonstrate that the target probe set selected from the candidate probe set generated using our approach has a reduced cost of monitoring the network.     

基于神经网络的电力变压器故障性质诊断研究

本文利用BP神经网络针对电力变压器故障性质诊断进行了研究,建立了5-12-3型神经网络模型,对比多种改进的BP算法选择最佳的训练函数。经实际数据仿真验证该模型能准确快速地得到诊断结果,达到预期效果。