Circuit testable design and universal test sets for multiple-valued logic functions

The circuit testable realizations of multiple-valued functions are studied in this letter. First of all, it is shown that one vector detects all skew faults in multiplication modulo circuits or in addition modulo circuits, and n＋1 vectors detect all skew faults in the circuit realization of multiplevalued functions with n inputs. Secondly, min（max） bridging fault test sets with n＋2 vectors are presented for the circuit realizations of multiple-valued logic functions. Finally, a tree structure is used instead of cascade structure to reduce the delay in the circuit realization, it is shown that three vectors are sufficient to detect all single stuck-at faults in the tree structure realization of multiplevalued logic functions.     

FAULT DETECTION TEST SET FOR TESTABLE REALIZATIONS OF LOGIC FUNCTIONS WITH ESOP EXPRESSIONS

The circuit testable realization and its fault detection for logic functions with ESOP （EXOR-Sum-Of-Products） expressions are studied. First of all, for the testable realization by using XOR gate cascade, a test set with 2n ＋ m ＋ 1 vectors for the detections of AND bridging faults and a test set with 2n ＋ m vectors for the detections of OR bridging faults are presented. Secondly, for the testable realization by using ）（OR gate tree, a test set with 2n ＋ m vectors for the detections of AND bridging faults and a test set with 3n ＋ m ＋ 1 vectors for the detections of OR bridging faults are presented. Finally, a single fault test set with n ＋ 5 vectors for the XOR gate tree realization is presented. Where n is the number of input variables and m is the number of product terms in a logic function.     

Robust tests for parity trees

Linear logic circuits are used extensively in digital computing and signal processing systems. They are constructed as regular arrays (for example as cascade or tree circuits), employing linear gates such as Exclusive OR (EOR) and Exclusive NOR (ENOR) gates. Earlier studies on fault diagnosis in linear logic circuits were based on the classical fault model of line stuck-at faults. Transistor stuck-open (SOP) and stuck-on (SON) faults in linear circuits were studied recently, but the effect of signal transients due to circuit delays and time skews in input changes were not considered in the derivation of test sequences. These latter factors are known to cause invalidation of two pattern tests for stuck-open faults. In this article we consider the problem of generating robust tests for linear logic circuits. These tests are not affected by circuit transients caused by delays. A major finding in this paper is that, if the test invalidation problem is redressed by introducing robust tests, the test length becomes a linear function of the depth of the circuit as opposed to the constant number of tests derived in previous studies, by neglecting circuit transients. A lower bound on minimum number of distinct test patterns needed for a tree of EOR gates of depthd is derived. This number depends on the specific implementation of the gate. Robust test-generation procedures are proposed for both single and multiple fault models and their optimalities are argued. Given that every gate in a parity tree is robustly testable, a test sequence that can test for all faults in the circuit, regardless of the nature of gate implementation, is calleduniversal robust test sequence for a parity tree. Finally we propose an optimal universal robust test sequence.     

Line coverage of path delay faults

We propose a new coverage metric for delay fault tests. The coverage is measured for each line with a rising and a falling transition, but the test criterion differs from that of the slow-to-rise and slow-to-fall transition faults. A line is tested by a line delay test, which is a robust path delay test for the longest sensitizable path producing a given transition on the target line. Thus, the test criterion resembles path delay test and not the gate or transition delay test. Yet, the maximum number of tests (or faults) is limited to twice the number of lines. In a two-pass test-generation procedure, we first attempt delay tests for a minimal set of longest paths for all lines. Fault simulation is used to determine the coverage metric. For uncovered lines, in the second pass, several paths of decreasing lengths are targeted. We give results for several benchmark circuits     

Robust Coupling Delay Test Sets

One of the most challenging problems in high-level testing is to reduce the size of a high-level test set while ensuring an adequate fault coverage for various implementations of a function under test. A small and high-coverage test set called a robust coupling delay test set (RCDTS) is derived from the coupling delay test set proposed previously. A partial ordering relationship among delay tests in certain implementations called ??restricted?? gate networks is used to reduce the size of test sets. The RCDTS still detects all robust path delay faults. This result is extended further to the more general balanced inversion parity networks. A test generation program RTGEN for RCDTSs is then developed, and experiments with it show that significant test set reduction can be achieved.     

Improving path delay testability of sequential circuits

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible     

Resynthesis of combinational logic circuits for improved path delayfault testability using comparison units

We propose a resynthesis method that modifies a given circuit to reduce the number of paths in the circuit and thus improve its path delay fault testability. The resynthesis procedure is based on replacing subcircuits of the given circuit by structures called comparison units. A subcircuit can be replaced by a comparison unit if it implements a function belonging to the class of comparison functions defined here. Comparison units are fully testable for stuck-at faults and for path delay faults. In addition, they have small numbers of paths and gates. These properties make them effective building blocks for resynthesis to improve the path delay fault testability of a circuit. Experimental results demonstrate considerable reductions in the number of paths and increased path delay fault testability. These are achieved without increasing the number of gates, or the number of gates along the longest path in the circuit. The random pattern testability for stuck-at faults remains unchanged     

False-Path Removal Using Delay Fault Simulation

Some false paths are caused by redundant stuck-at faults. Removal of those stuck-at faults automatically eliminates such false paths from the circuit. However, there are other false paths that are not associated with any redundant stuck-at fault. All segments of such a false path are shared with other testable paths. We focus on the elimination of this type of false paths. We use a non-enumerative path delay fault simulator based on the path status graph (PSG) data-structure, which duplicates selected gates to separate the detected and undetected path delay faults. The expanded circuit may contain new redundant stuck-at faults, corresponding to those undetected paths that are false. This happens because the expanded circuit has some new interconnects with only false paths passing through them. Such links become the sites for redundant stuck-at faults. Removal of these redundant faults eliminates false paths. The reported results show that the quality of the result may depend on the coverage of testable paths by the vectors that are simulated. When non-enumerative path delay simulation and implication-based redundancy removal techniques are used, the present procedure of false-path elimination can be applied to very large 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.     

Transition Path Delay Faults: A New Path Delay Fault Model for Small and Large Delay Defects

We propose a new path delay fault model called the transition path delay fault model. This model addresses the following issue. The path delay fault model captures small extra delays, such that each one by itself will not cause the circuit to fail, but their cumulative effect along a path from inputs to outputs can result in faulty behavior. However, non-robust tests for path delay faults may not detect situations where the cumulative effect of small extra delays is sufficient to cause faulty behavior after any number of extra delays are accumulated along a subpath. Under the new path delay fault model, a path delay fault is detected when all the single transition faults along the path are detected by the same test. This ensures that if the accumulation of small extra delays along a subpath is sufficient to cause faulty behavior, the faulty behavior will be detected due to the detection of a transition fault at the end of the subpath. We discuss the new model and present experimental results to demonstrate its viability as an alternative to the standard path delay fault model. We describe an efficient fault simulation procedure for this model. We also describe test generation procedures. An efficient test generation procedure we discuss combines tests for transition faults along the target paths in order to obtain tests that satisfy the requirements of the new model.     

Path delay fault testing of multiplexer-based shifters

In this paper we present a method for path delay fault testing of multiplexer-based shifters. We show that many paths of the shifter are not single path propagating hazard free robustly testable (SPP-HFRT) and we present a path selection method such that all the selected paths are SPP-HFRT by (Olog₂ n) test-vector pairs, where n is the length of the shifter's operand. The propagation delay along all other paths is a function of the delays along the selected paths. This is the first work addressing the problem of shifter path delay fault testing.     

Oscillation Ring Delay Test for High Performance Microprocessors

This paper proposes a new test scheme, oscillation ring test, and its associated test circuit organization for delay fault testing for high performance microprocessors. For this test scheme, the outputs of the circuit under test are connected to its inputs to form oscillation rings and test vectors which sensitize circuit paths are sought to make the rings oscillate. High speed transition counters or oscillation detectors can then be used to detect whether the circuit is working normally or not. The sensitizable paths of oscillation rings cover all circuit lines, detecting all gate delay faults, a large part of hazard free robust path delay faults and all the stuck-at faults. It has the advantage of testing the circuit at the working speed of the circuit. Also, with some modification, the scheme can also be used to measure the maximum speed of the circuit. The scheme needs minimal simple added hardware, thus ideal for testing, embedded circuits and microprocessors.     

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.     

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.     

Built-in testable error detection and correction

A method for design of built-in testable (BIT) error detection and correction (EDAC) circuits is presented that uses up to 65% less test hardware than customary BIT implementations. A 1-μm CMOS, 16-bit EDAC designed and fabricated with this technique exhibits >99% fault coverage in 10 μs at 25 MHz. Built-in test impacts the speed performance by only one gate delay regardless of the size of the EDAC. Various faults are injected into the chip to verify the effectiveness of built-in test     

Transistor-level to gate-level comprehensive fault synthesis for n-input primitive gates

In order to have a high level of confidence in system testing, more accurate fault models are needed. An accurate fault model cannot be attained unless all faults in the transistor-level (low level) are considered. However, these transistor-level faults must be mapped onto gate-level (higher level) so that the efficiency of fault simulation, fault emulation and test pattern generation at the gate-level is not sacrificed. This paper covers the static and dynamic single physical failures at transistor-level for static CMOS primitive gates and shows their effects in the output behavior in terms of gate-level faults. A specific fault pattern is proposed and a general formula to calculate the total number of static faults is concluded from these patterns for each type of gate regardless of its number of inputs. The dynamic nature of the physical faults included in the static fault list is evaluated and their cumulative effect on the timing at the circuit output is examined. A general formula for calculating propagation delay at the output due to resistive shorts and opens is derived and a delay fault pattern with variable defect resistance is provided.     

A fuzzy model for path delay fault detection

A fuzzy model is proposed to analyze the effectiveness of test pairs targeting path delay faults. This model is accurate enough to rank nonrobust tests by accounting for conditions not considered in existing models. It remains fully consistent with the traditional test robustness analysis. Finally, it also provides a coverage metric to be used to rank whole test sets. The proposed model has been implemented in a logic level path delay fault simulator. Its accuracy has been validated, for a set of combinational benchmarks, by means of a Monte Carlo logic-level event-driven path delay fault simulator.     

Multifault and delay-fault testability of multilevel circuits

This paper investigates the relationship between test sets for multiple stuck-at faults and robust path-delay-fault tests in multilevel combinational circuits. It is shown that, in multilevel circuits, a complete robust path-delay-fault test set may not detect all multiple stuck-at faults. We also show that the detectability of the former does not imply the detectability of the latter, as suggested in a recent paper. The presence of undetectable or untested multiple stuck-at faults may invalidate some path delay tests.Supported in part by NSF Grant MIP-9320886.     

Fault Models for Quantum Mechanical Switching Networks

In classical test and verification one develops a test set separating a correct circuit from a circuit containing any considered fault. Classical faults are modelled at the logical level by fault models that act on classical states. The stuck fault model, thought of as a lead connected to a power rail or to a ground, is most typically considered. A classical test set complete for the stuck fault model propagates both binary basis states, 0 and 1, through all nodes in a network and is known to detect many physical faults. A classical test set complete for the stuck fault model allows all circuit nodes to be completely tested and verifies the function of many gates. It is natural to ask if one may adapt any of the known classical methods to test quantum circuits. Of course, classical fault models do not capture all the logical failures found in quantum circuits. The first obstacle faced when using methods from classical test is developing a set of realistic quantum-logical fault models (a question which we address, but will likely remain largely open until the advent of the first quantum computer). Developing fault models to abstract the test problem away from the device level motivated our study. Several results are established. First, we describe typical modes of failure present in the physical design of quantum circuits. From this we develop fault models for quantum binary quantum circuits that enable testing at the logical level. The application of these fault models is shown by adapting the classical test set generation technique known as constructing a fault table to generate quantum test sets. A test set developed using this method will detect each of the considered faults.     

Testable design of BiCMOS circuits for stuck-open fault detectionusing single patterns

Single BJT BiCMOS devices exhibit sequential behavior under transistor stuck-OPEN (s-OPEN) faults. In addition to the sequential behavior, delay faults are also present. Detection of s-OPEN faults exhibiting sequential behavior needs two-pattern or multipattern sequences, and delay faults are all the more difficult to detect. A new design for testability scheme is presented that uses only two extra transistors to improve the circuit testability regardless of timing skews/delays, glitches, or charge sharing among internal nodes. With this design, only a single vector is required to test for a fault instead of the two-pattern or multipattern sequences. The testable design scheme presented also avoids the requirement of generating tests for delay faults