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     

Path delay fault simulation of sequential circuits

A differential algorithm for concurrent simulation of path delay faults in sequential circuits is presented. The simulator analyzes all three conditions, namely, initialization, signal transition propagation through the path, and fault effect observation at a primary output for vector pairs and considers the hazard states occurring between vectors. The main contribution is in methods of propagating signals between time frames. An optimistic method assumes that all nondestination flip-flops are not affected by delays. The pessimistic method converts all nondestination flip-flops with nonsteady values to the unknown state before these values are propagated beyond the time frame in which a path is activated. A 13-valued algebra is shown to improve the efficiency of fault simulation     

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.     

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.     

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.     

Accurate delay models for digital BiCMOS

A detailed transient analysis of the MOSFET-BJT combination prevalent in digital BiCMOS gates is presented. The analysis accounts for high-level injection leading to BJT β roll-off, base pushout leading to BJT f_T roll-off, short-channel behavior of the MOS drain current, and parasitic capacitances at the base and output. Based on the transient analysis, a piecewise delay expression is derived that shows excellent agreement with measured gate delay and with SPICE simulated delay. The comparisons are made for a wide range of circuit parameters in the gate, namely, MOSFET/BJT size, load capacitance, and supply voltage for both 1- and 0.6-μm BiCMOS technologies. The model is used to optimally size gates, and to determine circuit and device design guidelines to minimize the delay degradation at reduced supply     

Group delay functions for complex signals

This paper presents a method for finding the Magnitude Group Delay (MGD) and Phase Group Delay (PGD) functions for complex-valued signals. Algorithms are discussed for reconstructing the complex signals from the partial information of either the phase or magnitude of the Fourier transform of the signals under certain conditions. The high resolution property and the ability to manipulate regions of the spectrum of the MGD are brought out. The utility of the MGD function in identifying the wider bandwidth spectral peak in the vicinity of a narrow bandwidth peak is examined.     

Statistical estimation of delay fault detectabilities and fault grading

In this paper we present a technique to statistically estimate transition delay and path delay fault coverage. The basic method is an extension of STAFAN to include delay faults. By partitioning a combinational circuit into non-overlapping fanout free logic cones, we accurately calculate the transition sensitization controllabilities of 0 1 and 1 0 transitions of the lines within a fanout free logic cone to the output of the fanout free logic cone for each fanout free logic cone. A strategy to calculate the transition observabilities of fanout stems is proposed. The detectability of a path delay fault is evaluated as the product of the observabilities of the input line to its head gate within each fanout free logic cone on the path multiplied by the transition controllability of the path. When compared with the fault simulations, the estimations of transition delay fault coverage are within 2.3%. Also, the technique gives reasonably good path delay fault coverage estimation for large fault set of the ISCAS85 benchmark circuits.     

Incorporating fault debugging activities into software reliability models: a simulation approach

A large number of software reliability growth models have been proposed to analyse the reliability of a software application based on the failure data collected during the testing phase of the application. To ensure analytical tractability, most of these models are based on simplifying assumptions of instantaneous & perfect debugging. As a result, the estimates of the residual number of faults, failure rate, reliability, and optimal software release time obtained from these models tend to be optimistic. To obtain realistic estimates, it is desirable that the assumptions of instantaneous & perfect debugging be amended. In this paper we discuss the various policies according to which debugging may be conducted. We then describe a rate-based simulation framework to incorporate explicit debugging activities, which may be conducted according to the different debugging policies, into software reliability growth models. The simulation framework can also consider the possibility of imperfect debugging in conjunction with any of the debugging policies. Further, we also present a technique to compute the failure rate, and the reliability of the software, taking into consideration explicit debugging. An economic cost model to determine the optimal software release time in the presence of debugging activities is also described. We illustrate the potential of the simulation framework using two case studies.     

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.     

Parallel-concurrent fault simulation

A new parallel-concurrent fault simulation algorithm based on the partitioning of faults into groups, with the group size equal to the number of bits in the host computer word, is presented. The fault effects of a particular group are evaluated using parallel fault simulation techniques and propagated using concurrent fault simulation techniques. The speed of the algorithm depends on the circuit and on the fault-grouping criterion. An automatic grouping criterion is devised to group faults that are “close” or nearly equivalent. Comparisons to the concurrent, to the deductive, and to the PROOFS fault simulation techniques are performed on a SPARC SLC with 16 MB of memory running UNIX. ISCAS89 benchmark circuits are used for this comparison     

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.     

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.     

Data parallel fault simulation

Fault simulation is a computer-intensive problem. Parallel processing is one method to reduce simulation time. In this paper, we discuss a technique to partition the fault set for fault-parallel simulation on multiple processors. When applied statically, the technique can scale well for up to 32 processors. The fault-set partitioning technique is simple and can itself be parallelized. Existing uniprocessor algorithms, based on parallel-pattern simulation, can be used for multiprocessor simulation without modification. Therefore, the techniques can be used effectively on a low-cost parallel resource such as a network of workstations     

Generation of component level fault models for MEMS

Component level (nodal) simulations have been proposed to both implement closed loop simulation of complete microsystems to support the migration to shorter design cycles and implement fault models of micromechanical components. Within such a simulation environment, library cells in the form of behavioural models are used for the basic components of microelectromechanical (MEM) transducers, such as beams, plates, comb-drives and membranes. This paper presents both methodologies to generate the model parameters required for the implementation of accurate component fault models and simulation results from representative defective structures in a MEMS product.     

Parallel sequence fault simulation for synchronous sequential circuits

A novel parallel sequence fault simulation (PSF) algorithm for synchronous sequential circuits is presented. The algorithm successfully extend the parallel pattern method for combinational circuits to sequential circuits by proposing a multiple-pass mechanism to overcome the state dependency in sequential circuits. The fault simulation is performed in parallel by partitioning the entire sequence into subsequences of equal length. Furthermore, techniques are developed to minimize the number of simulation passes. Notably, two compact counters, C _x and C _d , are proposed to faciliate the early stabilization detection of faulty circuit simulation with minimum space overhead. The experimental results on the benchmark circuits show that the speedup ratio over a serial sequence fault simulator based on ROOFS is 9.16 on average for pseudo random vectors. The parallel sequence algorithm of PSF is especially adaptable to parallel and distributed simulation which exploits sequence partition.     

FPGA-based Monte Carlo simulation for fault tree analysis

The reliability analysis of critical systems is often performed using fault-tree analysis. Fault trees are analyzed using analytic approaches or Monte Carlo simulation. The usage of the analytic approaches is limited in few models and certain kinds of distributions. In contrast to the analytic approaches, Monte Carlo simulation can be broadly used. However, Monte Carlo simulation is time-consuming because of the intensive computations. This is because an extremely large number of simulated samples may be needed to estimate the reliability parameters at a high level of confidence.In this paper, a tree model, called Time-to-Failure tree, has been presented, which can be used to accelerate the Monte Carlo simulation of fault trees. The time-to-failure tree of a system shows the relationship between the time to failure of the system and the times to failures of its components. Static and dynamic fault trees can be easily transformed into time-to-failure trees. Each time-to-failure tree can be implemented as a pipelined digital circuit, which can be synthesized to a field programmable gate array (FPGA). In this way, Monte Carlo simulation can be significantly accelerated. The performance analysis of the method shows that the speed-up grows with the size of the fault trees. Experimental results for some benchmark fault trees show that this method can be about 471 times faster than software-based Monte Carlo simulation.     

Direct tunnelling models for circuit simulation

This paper presents a review of models for direct tunnelling with a view to identifying suitable models for inclusion in a circuit simulator. For thin oxides, the critical quantities required for the derivation of tunnel current are the transparency of the barrier, the oxide field and the supply of carriers for tunnelling. This paper reviews different approaches to the incorporation of these quantities in analytical models. A new model for direct tunnelling, which includes quantum effects in a format suitable for circuit simulation, is outlined. Recent developments in MOSFET models, which include gate current, are briefly discussed.     

Standardizing compact models for IC simulation

The idea of standard compact (SPICE-like) model equations has gained support recently throughout the semiconductor industry. In the past, compact models have been developed independently either by a single company or by a university or research group. These models have lacked diverse technology coverage and normally were not fully tested or productized. The concept of standardization is embraced by the semiconductor industry in several other areas, yet simulation has lagged behind due to the difficult notion of standardizing software. In this article, the idea of a standard compact model will be described as well as the industry consortium supporting the standardization effort