Statistical Delay Fault Coverage Estimation for Synchronous Sequential Circuits

We present a technique to statistically estimate path-delay fault coverage for synchronous sequential circuits. We perform fault-free simulation using a multivalue algebra and accumulate signal transition statistics, from which we calculate controllabilities of all signals and sensitization probabilities for all gates and flip-flops. We use a rated clock testing model where all time frames operate at the rated clock. We obtain path observabilities either by enumerating paths in the all-paths method, or by a nonenumerative method considering only the longest paths. The path-delay fault detectability is the product of observabilities of signals on paths from primary inputs (PIs) or pseudo-primary inputs (PPIs) to primary outputs (POs) or pseudo-primary outputs (PPOs), and the controllability on the corresponding PI or PPI. We use the optimistic update rule of Bose et al. for updating latches during logic simulation. When compared with exact fault simulation, the average absolute deviation in our statistical fault coverage estimation technique is 1.23% and the very worst absolute deviation was 6.59%. On average, our method accelerates delay fault coverage computation four times over an exact path delay fault simulator.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

Cell delay fault testing for iterative logic arrays

C-testable iterative logic arrays for cell-delay faults are proposed. A cell delay fault occurs if and only if an input transition can not be propagated to the cell's output through a path in the cell in a specified clock period. The set of single-path propagation, hazard-free robust tests that completely check all the paths in a cell is first derived, and then necessary conditions for sending this test set to each cell in the array and simultaneously propagating the fault effects to the primary outputs are given. Test set minimization can be solved in a similar way as for the fault cover problem. We use the pipelined array multiplier as an example, and show that it is C-testable with 214 two-pattern tests. With a small number of additional patterns, all the combinational faults can be detected pseudoexhaustive.     

Selection of Voltage Thresholds for Delay Measurement

Since all physical devices have a finite non-zero responsetime, the notion of delay between the input and output logicsignals arises naturally once digital abstraction is done. Thisdelay should be positive and non-zero, since a physical devicetakes a finite amount of time to respond to the input. Defininga strictly positive delay is not a problem in the abstract domainof logic signals, since input and output events are preciselydefined. However, when the signal non-idealities are accountedfor, the notion of events is blurred and it is not obvious howto define delay such that it reflects the causal relationshipbetween the input and the output. By necessity, we define thestart and end points of these events by determining the timeinstants when the signals cross some appropriate voltage thresholds.The selection of these voltage thresholds for logic gates aswell as simple interconnect wires, is the subject of this paper.We begin by a discussion of what we mean by signal delay andhow it arises in a logic gate. With this background, startingfrom ideal inputs to ideal inverters and concluding with physicalinputs to physical inverters, we examine the problem of thresholdselection for inverters through a logical sequence of model refinement,using a combination of analytical and experimental techniques.Based on the insight gained through this analysis, we examinethe problem for multi-input (both static and dynamic) gates aswell as point-to-point interconnect wires. We show that thresholdsderived from the gates DC voltage transfer characteristic removesthe anomalies, such as negative delay and large sensitivity toinput waveshape effects, that can arise with the widely used50% and 10%–90% thresholds. Despite its fundamentalnature, however, we note that the problem of threshold selectionhas received scant attention in the literature. To the best ofour knowledge, this is the first detailed study of this problem.     

Using a WLFSR to Embed Test Pattern Pairs in Minimum Time

We propose a methodology for reducing the number of test cycles needed by a Weighted LFSR (WLFSR) to reproduce a 2P × W test matrix T of P pattern pairs. The methodology introduces a very small number of extra cells into the WLFSR and uses appropriate combinational mapping logic in order to make the time be equal to that required by a (W + )-bit WLFSR to generate vectors containing the W bits of the first pattern for each pair plus the extra bits. We present an algorithm that makes the value of be less than or equal to log₂, where is the size of the maximum subset of pairs in T with identical first patterns. This is a significant improvement over the time E _P,W · P required by a trivial approach that uses a WLFSR with W cells to generate the first patterns of the pairs and a P × W ROM to store the second patterns of the pairs. Experimental results on the application of the methodology to the embedding of test matrices for path delay faults are particularly encouraging, even for very large numbers of test pattern pairs that are necessary for provably high fault coverage.     

Delay Fault Coverage Enhancement Using Variable Observation Times

Detection of system timing failures has become a very importantproblem whenever high speed system operation is required. It has beendemonstrated that delay fault coverage loss could be significant if improperpropagation paths are used. This occurs when the delay test pair of a targetpropagation path cannot be effectively generated by an ATPG tool, or whenstuck-at test patterns are used as transition (or gate) delay test patterns.In this work, an efficient method is proposed to reduce the amount of faultcoverage loss by using variable observation times. The basic idea is tooffset the shorter propagation paths (really used) by tightening theobservation times. Given a probability distribution of defect sizes and aset of slack differences, this method is able to locate several observationtimes that result in small fault coverage loss.     

Fault diagnosis in reconfigurable VLSI and WSI processor arrays

A systematic efficient fault diagnosis method for reconfigurable VLSI/WSI array architectures is presented. The basic idea is to utilize the output data path independence among a subset of processing elements (PEs) based on the topology of the array under test. The divide and conquer technique is applied to reduce the complexity of test application and enhance the controllability and observability of a processor array. The array under test is divided into nonoverlapping diagnosis blocks. Those PEs in the same diagnosis block can be diagnosed concurrently. The problem of finding diagnosis blocks is shown equivalent to a generalizedEight Queens problem. Three types of PEs and one type of switches, which are designed to be easily testable and reconfigurable, are used to show how to apply this approach. The main contribution of this paper is an efficient switch and link testing procedure, and a novel PE fault diagnosis approach which can speed up the testing by at leastO(V^1/2) for the processor arrays considered in this paper, where V is the number of PEs. The significance of our approach is the ability to detect as well as to locate multiple PE, switch, and link faults with little or no hardware overhead.     

Classification and Test Generation for Path-Delay Faults Using Single Struck-at Fault Tests

We classify all path-delay faults of a combinational circuit intothree categories: singly-testable (ST), multiply-testable (MT), and singly-testable dependent} (ST-dependent). The classification uses anyunaltered single stuck-at fault test generation tool. Only two runsof this tool on a model network derived from the original network areperformed. As a by-product of this process, we generate single andmultiple input change delay tests for all testable faults. With thesetests, we expect that most defective circuits are identified. All STfaults are guaranteed detection in the case of a single fault, andsome may be guaranteed detection through robust and validatablenon-robust tests even in the case of multiple faults. An ST-dependentfault can affect the circuit speed only if certain ST faults arepresent. Thus, if all ST faults are tested, the ST-dependent faultsneed not be tested. MT faults cannot be guaranteed detection, butaffect the speed only if delay faults simultaneously exist on a setof paths, none of which is ST. Examples and results on several ISCAS89 benchmarks are presented. The method of classification throughtest generation using a model network is complex and can be appliedto circuits of moderate size. For larger circuits, alternativemethods will have to be explored in the future.     

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.     

阵列乘法器通路时延故障的内建自测试

阵列乘法器因高度集成和高速运行,容易受到时延故障的困扰.该文对阵列乘法器的通路时延故障提出了一种用累加器实现的以单跳变序列作为测试序列的内建自测试方案.已有的理论和实践表明采用单跳变测试序列比多跳变序列具有更高的测试鲁棒性.同时,该文的测试方案在测试通路覆盖率和测试向量数之间做到了兼顾.仿真结果表明这种单跳变测试序列具有高测试通路覆盖率.此外,测试生成通过系统已有累加器的复用可节省硬件成本开销.     

一种新的故障测试率的概率估计方法

本文提出了一种新的估计故障测试率的方法。它使用了无故障模拟的概念,观察率和控制率被定义成观察和控制电路节点的概率;分析了电路中节点的随机信号的概率分布;证明了控制率是服从正态分布的;依此获得了故障测试率的无偏估计。按照观察率的定义,我们处理了扇出节点。对一些实际的电路,利用此法所获得的故障覆盖与故障模拟结果非常吻合。     

Delay and Power Expressions for a CMOS Inverter Driving a Resistive-Capacitive Load

A delay and power model of a CMOS inverter driving aresistive-capacitive load is presented. The model is derivedfrom Sakurais alpha-power law and exhibits good accuracy. Themodel can be used to design and analyze those CMOS invertersthat drive a large RC load when considering bothspeed and power. Expressions are provided for estimating thepropagation delay and transition time which exhibit less than27% discrepancy from SPICE for a wide variety of RCloads. Expressions are also provided for modeling the short-circuitpower dissipation of a CMOS inverter driving a resistive-capacitiveinterconnect line which are accurate to within 15% of SPICEfor most practical loads.     

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.     

ITA: An algorithm for I DDQ testability analysis

This paper presents the I _DDQ Testability Analysis (ITA) algorithm for the estimation of a circuit design's leakage fault testability. The algorithm is based on the calculation of the probability of applying each of a set of essential vectors to each gate in the circuit. The essential vectors for each gate represent the minimal vector set that provides maximal leakage fault coverage.ITA assumes independence of circuit net values, except in the case of reconvergent fanout. Reconvergent fanout is identified by levelizing the circuit and propagating sets of labels from the primary inputs forward through the circuit, beginning with unique labels (integers) on each primary input. ITA evaluation of reconvergent fanout points then uses a backward implication procedure to calculate the essential vector probability values for the reconvergent gate, except in the case where backward implication is not deterministic.Results of an implementation of ITA are presented for a set of benchmark circuits, including a sample of the ISCAS '85 and '89 circuits.     

Delay fault simulation of sequential circuits

This article proposes a 7-valued logic appropriate for test generation and fault simulation, in the area of robust tests for gate delay faults, and a straightforward simulation strategy for sequential circuits. It is shown that a purely qualitative logic of robust testing is inadequate for circuits with edge-triggered flip-flops. The relation between the 7-valued logic and the similar logic proposed before by Smith, Schulz et al., and Lin and Reddy are discussed.     

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.     

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     

Fast algorithms for selection of test nodes of an analog circuit using a generalized fault dictionary approach

Selection of test nodes is an important phase of the fault dictionary approach. It is demonstrated in this paper that the techniques used for this purpose in other approaches of analog fault diagnosis like fault analysis and fault verification are not in general suitable for the fault dictionary approach. The ambiguity set is a simple and effective concept for choosing test nodes in the context of dictionaries. These sets are formed such that each faulty condition lies in only one ambiguity set. Deviating from this thinking, overlapping ambiguity sets are proposed in this paper, giving rise to a generalized fault dictionary. These sets use information more fully and hence reduce the number of test nodes. The concept of hashing is applied in this paper for selecting test nodes. This gives a linear time algorithm (linear in the number of fault voltage specificationsf) and it isf times faster than the existing methods. It is not possible to select test nodes faster than this. This technique can also be used to select test nodes by the process of elimination of nodes. This is also linear inf per node elimination. Even a group of nodes can be eliminated or selected within the same computation. This freedom is not possible with the existing methods.     

Path delay fault simulation of sequential circuits

To analyze path delay faults in synchronous sequential circuits, stimuli are simulated in a dual-vector mode. The signal states represent the logic and transition conditions for two consecutive vectors. After the simulation of each vector, only the activated paths are traced and the corresponding fault effect, if propagated to a flip-flop, is added to its fault list. A path numbering scheme avoids storage of path data which can be generated, if needed, from the path number. The simulation is independent of the specific delays of the combinational elements, and either robust or nonrobust detection can be simulated as options to the user. For robust simulation, an update rule for state variables is proposed whereby a flip-flop is updated with its correct value, provided it is a destination of at least one robustly activated path. This rule gives a higher and more realistic coverage of robustly detected faults. Experimental results verify the effectiveness of the simulator     

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.