Bounding fault detection probabilities in combinational circuits

This paper focuses on the problem of bounding fault detection probabilities in combinational circuits. Two algorithms, the complete cutting algorithm and the gate blocking algorithm, are presented that always produce true lower bounds on the detection probability of a fault. Both algorithms can be used to identify difficult-to-test faults and to quickly construct test sets for specific faults. Both algorithms have qualitative versions which provide insight into a circuit while avoiding arithmetic calculation. Both algorithms resulted from research in trying to determine the accuracy of the safety factor heuristic of Jacob Savir.This research was supported by a grant from the IBM Corporation.     

A partitioning technique for reducing the computational complexity of probabilistic fault detection in general combinational circuits

This paper examines the impacts of different types of circuit partitioning on reducing the computational complexity for computing the fault detection probability, which usually grows exponentially with the number of input lines in the given circuit. Partitioning a large combinational circuit into arbitrary subcircuits does not, in general, reduce the computational time complexity of the fault detection probability. In fact, partitioning a given circuit into general subcircuits is expected to increase the time complexity by the amount of time spent in the partition process itself. Nevertheless, it will be shown that decomposing a general combinational circuit into its modules (supergates) such that these modules constitute the basic elements of a tree circuit (network) considerably reduces the computational complexity of the fault detection probability problem. Toward this goal, two algorithms are developed. The first partitions a given circuit into maximal supergates whenever this is possible. Its computational complexity depends linearly on the number of edges (or lines) and nodes (or gates) of the circuit. The second computes the exact detection probabilities of single faults in the tree network and its computational complexity grows exponentially with the largest number of input lines in any of the network maximal supergates rather than the total number of inputs. The case of multi-output circuits is also discussed.     

Fault detection in combinational circuits using a compressed fault table

A method is developed for obtaining a highly compressed fault table for two-level combinational circuits. A set of operations is defined through which the minimal test set for detecting stuck-at faults is obtained from the compressed fault table. The method is equally suitable for sum of products form or product of sums form realization of logic functions and generates the test set directly from the algebraic expression of the logic function.     

A stuck fault model for dynamic CMOS combinational circuits

This paper utilizes the logic transistor function (LTF), that was devised to model the static CMOS combinational circuits at the transistor and logic level, to model the dynamic CMOS combinational circuits. The LTF is a Boolean representation of the circuit output in terms of its input variables and its transistor topology. The LTF is automatically generated using the path algebra technique. The faulty behavior of the circuit can be obtained from the fault-free LTF using a systematic procedure. The model assumes the following logic values (0, 1, I, M), where I, and M imply an indeterminate logical value, and a memory element, respectively. The model is found to be efficient in describing a cluster of dynamic CMOS circuits at both the fault-free and faulty modes of operation. Both single and multiple transistor stuck faults are precisely described using this model. The classical stuck-at and non classical stuck open and short faults are analyzed. A systematic procedure to produce the fault-free and faulty LTFs for different implementations of the dynamic CMOS combinational circuits is presented.     

A new fault independent test generation algorithm for combinational logic circuits

In order to improve the performance of fault independent test generation algorithms, two strategies are proposed: a critical lines maximization strategy (CLM) and a critical primary inputs flipping strategy (CPF). CLM is used to maximize the number of detected faults while generating a test pattern. CPF is used to derive new test pattern(s) from a generated test pattern with little additional effort. A new fault independent test generation algorithm (MAX) based on these strategies is introduced and illustrated.     

An integrated fault tolerance technique for combinational circuits based on implications and transistor sizing

With fabrication technology reaching nano levels, systems are exposed to higher susceptibility to soft errors. Thus, development of effective techniques for designing soft error tolerant systems is of high importance. In this work, an integrated soft error tolerance technique based on logical implications and transistor sizing is proposed. In order to reduce implication learning time, a set of source and target nodes with predefined thresholds are selected and implications between these nodes are extracted. Then, the impact of adding a functionally redundant wire (FRW) due to each implication is evaluated. This is done based on identifying an implication path and the gates along the implication path whose detection probabilities will be reduced due to adding the implication FRW. Then, the gain of an implication is estimated in terms of reduction in fault detection probabilities of gates along an implication path. The implication with the highest gain is selected. The process is repeated until the gain is less than a predetermined threshold. The proposed implication-based fault tolerance technique enhances the circuit reliability with minimal area overhead based on enhancing logical masking. However, its effectiveness depends on the existence of such relations in a circuit and can enhance circuit reliability upto a certain level. To enhance circuit reliability to any required level, selective-transistor redundancy (STR) based technique is then applied. This technique is based on providing fault tolerance for individual transistors with high detection probability based on transistor duplication and sizing. Experimental results show that the proposed integrated fault tolerance technique achieves similar reliability in comparison to applying STR alone with lower area overhead.     

Symbolic fault modelling of MOS combinational circuits

This paper presents a new method for fault modelling of MOS combinational circuits at the transistor level. Every transistor is replaced with a conductance controlled by the gate logic value. The specific advantage of the method is use of a symbolic simulator for circuit function extraction. This function is referred as Transistor Logic Conductance Function (TLCF). Starting from a known TLCF, a simple set of rules is used for output state determination. The method is suitable for multiple fault model generation thanks to the fact that only one symbolic analysis of a circuit is sufficient for modelling different stuck-open, stuck-short and stuck-at faults of a logic gate. Moreover, the method can deal also with bridging and cut faults. Finally, the application of the TLCF for test pattern generation is considered.     

A generalized modular redundancy scheme for enhancing fault tolerance of combinational circuits

Nano-scale devices are continuously shrinking, operating at lower voltages and higher frequencies. This makes them more susceptible to environmental perturbations and distinguished by their high dynamic fault rates. Redundancy techniques are widely used to increase the reliability of combinational logic circuits. In this work, soft error reliability is improved by using such techniques, and based on probability of occurrence for combinations at the outputs of circuits. A generalized modular redundancy scheme to enhance the reliability of combinational circuits is proposed. Additionally, several aspects regarding the application of this scheme are explored. This comprises types of redundant modules, complexity of voters and single versus multiple outputs protection. Also, a methodology for applying the generalized modular redundancy scheme is developed. Reliability analysis for various benchmarks from the LGSynth91 suite shows that the proposed methodology can achieve reliability figures higher than that of triple modular redundancy. In general, significant overhead savings are accomplished in addition to that superior reliability.     

Design of self-testing and on-line fault detection combinational circuits with weakly independent outputs

In this article we propose a structure dependent method for the systematic design of combinational selftesting fault detection circuits that is well adapted to the arbitrarily chosen technical fault model. According to the fault model considered the outputs of the circuit are partitioned into different generally nondisjoint groups of weakly independent outputs. The parities of these groups of weakly independent outputs are compared in test mode as well as in normal operation mode with the corresponding predicted parities by use of a self-checking checker. For on-line detection, the hardware is in normal operation mode, and for testing, it is in test mode. In the test mode, these fault detection circuits guarantee a 100% fault coverage for single stuck-at-0/1 faults and a high fault coverage for arbitrary faults. In normal operation mode all technical faults considered will be detected possibly, with some degree of latency.Partially presented at the VLSI Test Symposium, Atlantic City, 1992.     

Multiple fault detection in fanout-free combinational networks

In this letter we show that an algorithm developed by Berger and Kohavi for generating minimal length fault-detection test sets for single permanent faults in fanout-free combinational logic networks also detects all possible multiple faults in the network.     

Transitional gate delay detection for combinational circuits usinga genetic algorithm

The authors present a new technique for the generation of test vector-pairs that detect both delay and single stuck-at-fault conditions in digital logic circuits. A genetic algorithm (GA), is used to pursue and extract efficient tests from a complex search space. Results obtained for the ISCAS 1985 benchmark circuits compare favourably with the results of other researchers, even when the genetic system considers both delay and single stuck-at-fault models     

Reconvergent fanout analysis and fault simulation complexity of combinational circuits

The detectability of reconvergent fanout stem faults in a combinational logic circuit can be determined by explicitly simulating the faults within limited regions of the circuit. These regions are defined, and an estimate of the fault simulation complexity of the circuit is obtained. Results are presented for ten benchmark circuits.     

Fault detection in combinational circuits using Gunn effect logic devices

It is shown that certain realisations of combinational switching functions using Gunn effect logic gates can be tested for single or multiple stuck-type faults by using two tests only. This result is achieved by exploiting the fact that the function of Gunn effect logic gates is sensitive to bias voltage     

A novel design of a combinational network to facilitate fault detection

This letter describes a novel design of a combinational network to facilitate the single stuck-at fault detection problem. The design makes use of EXCLUSIVE-OR modules as control elements and the observability has been increased by providing an additional observable output which is the output of an additional AND gate in the network. Such a design of a combinational network with n primary input variables will require only (n + 1) predefined test input patterns belonging to the set T = {11...11,011...11,101 ...11, ........., 11 ... 110} for the detection of stuck-at single s-a-0 and s-a-1 fault on a line of the network. As a result, the extremely difficult task of test generation can be easily dispensed with.     

Enhanced architectures for soft error detection and correction in combinational and sequential circuits

In this paper two new methods for the design of fault-tolerant pipelined sequential and combinational circuits, called Error Detection and Partial Error Correction (EDPEC) and Full Error Detection and Correction (FEDC), are described. The proposed methods are based on an Error Detection Logic (EDC) in the combinational circuit part combined with fault tolerant memory elements implemented using fault tolerant master–slave flip-flops. If a transient error, due to a transient fault in the combinational circuit part is detected by the EDC, the error signal controls the latching stage of the flip-flops such that the previous correct state of the register stage is retained until the transient error disappears. The system can continue to work in its previous correct state and no additional recovery procedure (with typically reduced clock frequency) is necessary. The target applications are dataflow processing blocks, for which software-based recovery methods cannot be easily applied. The presented architectures address both single events as well as timing faults of arbitrarily long duration. An example of this architecture is developed and described, based on the carry look-ahead adder. The timing conditions are carefully investigated and simulated up to the layout level. The enhancement of the baseline architecture is demonstrated with respect to the achieved fault tolerance for the single event and timing faults. It is observed that the number of uncorrected single events is reduced by the EDPEC architecture by 2.36 times compared with previous solution. The FEDC architecture further reduces the number of uncorrected events to zero and outperforms the Triple Modular Redundancy (TMR) with respect to correction of timing faults. The power overhead of both new architectures is about 26–28% lower than the TMR.     

A finite state machine based fault tolerance technique for sequential circuits

With technology advancement at the nanometer scale, systems became more subjected to higher manufacturing defects and higher susceptibility to soft errors. Currently, soft errors induced by ion particles are no longer limited to a specific field such as aerospace applications. This raises the challenge to come up with techniques to tackle soft errors in both combinational and sequential circuits. In this work, we propose a finite state machine (FSM) based fault tolerance technique for sequential circuits. The proposed technique is based on adding redundant equivalent states to protect few states with high probability of occurrence. The added states guarantee that all single faults occurring in the state variables of highly occurring states or in their combinational logic are tolerated. The proposed technique has minimal area overhead as only few states need protection.     

The detection probability computation of single stuck-at-faults in general combinational circuits

The detection probability problem of single faults at specified signal lines of a general combinational circuit C merits special interest. In this paper, a method is developed for such a purpose. The method has a computational complexity of O(2^N), with N being the number of the non-fanout primary inputs plus the specified signal lines at the highest level of C. The applicability of the simple chain rule in the probability domain, whenever possible, is shown to reduce the computational time complexity. Moreover, all signal lines and gates within any subcircuit C_i of C with redundant output lines are shown to be redundant as well, excluding those subcircuits C_js of C_i having fanout stems as output lines, provided that such stems do not converge in C_i     

Optimal fault detection for analogue circuits under manufacturingtolerances

An optimal method for analogue fault detection is presented. Instead of using arbitrary decision windows, the method fully considers the VLSI manufacturing tolerances and mismatches to minimise the probability of erroneous test decision. A-priori simulated probability information is combined with the actual measurement data to decide whether the circuit is fault-free or faulty. Experimental results show the effectiveness of the proposed technique     

A simple packet aggregation technique for fault detection

Packet monitoring has become a standard technique in network management and when applied to a large‐scale transit network yields a high volume of packets. To overcome this problem, we discuss the behavior of packets and present a symptom‐based packet aggregation technique which is useful for fault detection. Copyright © 2000 John Wiley & Sons, Ltd.     

Multiple fault detection in two-level multi-output circuits

It is often stated that in irredundant two-level logic circuits, a test set for all single stuck faults will also detect all multiple stuck faults. We show by a simple example that this result does not hold for multi-output circuits even when each output function is prime and irredundant. Using a result from the programmable logic array technology, we give an output ordering constraint that, if satisfied during test generation, will make a single stuck fault test set a valid multiple stuck fault test set for irredundant two-level multi-output circuits.