Defect-Oriented Fault Simulation and Test Generation in Digital Circuits
W.Kuzmicz, W.Pleskacz J.Raik, R.Ubar
Warsaw University of Technology Tallinn Technical University
Abstract
A generalized approach is presented to fault simulation and test generation based on a uniform functional fault model for different system representation levels. The fault model allows to represent the defects in components and defects in the communication network of components by the same technique. Physical defects are modeled as parameters in generalized differential equations. Solutions of these equations give the conditions at which defects are locally activated. The defect activation conditions are used as functional fault models for the higher level fault simulation purposes. In such a way, the functional fault model can be regarded as interface for mapping faults from one system level to another, helping to carry out hierarchical fault simulation and test generation in digital systems. A methodology is proposed which allows to find the types of faults that may occur in a real circuit, to determine their probabilities, and to find the input test patterns that detect these faults. Experimental data of the hierarchical defect-oriented simulation for ISCAS’85 benchmarks are presented, which show that classical stuck-at fault based simulation and the test coverage calculation based on counting defects without considering defect probabilities may lead to considerable overestimation of results.
1. Introduction
Testing and diagnosis of VLSI circuits and digital systems have faced a lot of problems produced by continuous emerging of new technologies and.by growing complexity of circuits and systems.
The efficiency of test generation (test quality, generation speed) is highly depending on the system description and fault models. Since traditional low-level test generation methods and tools for complex VLSI systems have lost their importance, other approaches based mainly on functional, behavioral, or hierarchical methods are gaining more and more popularity [1-2]. The advantage of hierarchical test generation approaches compared to the functional ones lies in the possibility of constructing test plans at higher functional levels, and modeling faults at lower levels.
Traditionally used very popular stuck-at fault (SAF) model has not withstood the test of time. It has been shown that high SAF coverage cannot quarantee high quality of testing, for example, for CMOS integrated circuits [3-5]. The reason is that the SAF model ignores the actual behaviour of digital circuits implemented as CMOS integrated circuits, and does not adequately represent the majority of real IC defects and failure mechanisms which often do not manifest themselves as stuck-at faults. The types of faults that can be observed in a real gate depend not only on the logic function of the gate, but also on its physical design. These facts are well known [4-7] but usually ignored in engineering practice. In earlier works on layout-based test generation techniques [6,7] the whole circuits having hundreds of gates were analysed as single blocks. Such an approach is computationally expensive and thus highly impractical as a method of generation of tests for real VLSI designs.
In this work we characterise faults in library cells, determine kinds of faults and their probabilities and then use this information for defect oriented fault simulation and test generation at higher levels of abstraction. This approach is based on the assumption that the majority of defects occur inside the cells and not in the routing between them. Such assumption would not be realistic in the case of older CMOS technologies with two levels of metal and very dense routing. However, in state-of-the-art deep submicron technologies still only one or two levels are used inside cells but 6 or more levels of metal are available for routing. More routing levels means lower sensitivity to defects. Routing between the cells is less dense and various nodes are routed at various metal levels. As a result, probability of shorts outside cells is significantly reduced.
In this work we verify functionality of analysed gates for all possible defects and find the actual functions performed, using transistor-level simulation. This characterisation process may be computationally expensive, but it is performed only once for every library cell. In other words, we replace abstract fault models like SAF with realistic defect models.
In [8] a new approach was introduced for hierarchical defect simulation based on defect preanalysis for components, and using the results of preanalysis in higher level fault simulation. Here, we generalize this approach by introducing a functional fault model as a method for mapping faults from one hierarchical level to another. Based on this approach, hierarchical algorithms for dafect-oriented fault simulation and test generation are developed and implemented. The functional fault model in a form of a set of logical conditions allows to represent the defects in components and in the communication networks by the same technique.
Then we propose a methodology which allows to find the types of logic faults that may occur in a real circuit, to determine their probabilities of occurrence, and to find the input test patterns that detect these faults. We compare the results obtained in this way with the results of testing of the same circuits by the sequences of test patterns based on the conventional fault model. Experiments were carried out for the ISCAS’85 benchmark circuits.
The paper is organized as follows. In Section 2 we present a new method of parametric fault modeling for carrying out defect analysis in digital circuits. In Section 3 we define the functional fault model which will be used as a interface for mapping faults from one hierarchical level to another. In Section 4 we propose a uniform hierarchical approach to test based on the functional fault model. Section 5 presents the results of a probabilistic analysis of defects and relates the defects to the functional fault model. In Section 6 we propose a new hierarchical defect oriented fault simulator and a random test generator. Section 7 presents experimental results, and finally, in Section 8 we draw the conclusions of this research.
2. Parametric defect modeling
In this Section we present a new general fault model for describing and modeling arbitrary physical defects in components of digital circuits that result in a violation of the logical function of a component.
Consider a Boolean function y = f (x1, x2, …, xn) implemented by an embedded component in a digital circuit. Introduce a Boolean variable d for representing a given defect in the component or in the neighbourhood layout of the component, which may affect the value y by converting the Boolean function f into another function
y = f d (x1, x2, …, xn, xn+1, … xp).
Here, the variables xn+1, … xp belong to the neighbourhood layout of the component which will influence the function y in the presence of defect d.
Figure 1. A short between two signal leads
For example, assume there is a short between leeds x1 and x5 in the circuit in Fig. 1. The faulty function y = f(x1,x2) = Ø(x1 Ù x2) in the case of the defect d can be represented as
y = fd(x1,x2,x3,x4)= Ø(x1 x5)Úx2=Ø(x1Ø (x3Ù x4))Úx2).
Introduce now a generalized parametric function
y* = f*( x1, x2, …, xn, xn+1, … xp, d) = Ød & f Ú d & f d
as a function of a defect variable d, which describes the behavior of the component simultaneously for both possible cases. For the erroneous case the value of the defect variable d as a parameter is equal to 1, and for the nonerroneous case d = 0. In other words, y* = f d if d = 1, and y* = f if d = 0. The solution of the Boolean differential equation
Wd = ¶y* / ¶d = 1 (1)
describes now the conditions (constraints) which activate the fault d on a line y (Fig.2).
For example for the short in Fig.1 we have
y* = ØdfÚdf d =ØdØ(x1 Ù x2) Ú d(Øx1Ø(x3 Ù x4)ÚØx2).
Wd = ¶y* / ¶d = x1 x2 x3 x4.
The parametric modeling of a given physical defect d by equation (1) allows us to use the solutions Wd, either
- in defect-oriented fault simulation, for checking if the condition (1) for a given defect d is fulfilled (if the defect d is activated), or
- in defect-oriented test generation, to solve the differential equation (1) with the goal to activate the given defect d.
To find the parametric fault model for a given defect d we have to create the corresponding logical expression for the faulty functions fd either by logical reasoning or by carrying out directly defect simulation.
Some examples of the conditions Wd for different type of defects (where stuck-at-fault (SAF) is a particular case) are given in Table 1 (here xk is the observable variable, and x’k is the variable at the previous time moment).
Table 1. Activating conditions for different defects
No / Defect / Conditions Wr1 / SAF xk º 0 / xk = 1
2 / SAF xk º 1 / xk = 0
3 / Short between xk and xl / xk = 1, xl = 0
4 / Exchange of lines xk and xl / xk = 1, xl = 0, or xk = 0, xl = 1
5 / Delay fault on the line xk / xk = 1, x’k = 0, or
xk = 0, x’k = 1
The conditions Wd for activating defects d can be used at the higher (logical or register transfer) level either for fault simulation or for test pattern generation without paying attention to the physical reasons of defects.
3. Concept of the functional fault model
The method of defect modeling by logical conditions (see Fig. 2) can be generalized for the purpose of hierarchical fault simulation.
Fig. 2. Functional fault model for a physical defect
A module (e.g. a library component) in a circuit can be preprocessed by lower level fault simulation with the goal to generate a set of logical conditions W = {Wr } for all possible lower level faults r of the component. Each condition Wr can be regarded as a higher level functional fault model for a given lower level fault r, since in the presence of the fault r the functional behavior of the component at the input stimuli Wr = 1 will be faulty.
Definition 1: We call a failed input pattern ti of a given module M (complex gate or component) a functional fault if it detects at the output of M at least one lower level fault rj in the module M.
The functional fault model can be regarded as a uniform way of mapping faults between two hierarchical levels. For example, we can map by the same way both, the gate level stuck-at faults or the physical defects of a component in a circuit to the higher behaviour level of the same component. The input patterns ti for a given fault rj can be found either by traditional gate level test generation (e.g. for stuck-at faults) or by parametric fault modeling and solving corresponding differential equations (1) for physical level defects.
Definition 2: We call a set of functional faults which cover all the lower level faults of the component a functional fault model of the component.
Using the conception of the functional fault model allows to reduce the complexity of fault modeling if the number of higher level faults is less than the number of lower level faults. For example, for the ISCAS’85 benchmark circuit c17, it was possible to replace 78 lower level physical defects by only 4 functional faults (see Section 6). The complexity reduction in this particular case is 20 times. On the other hand, the functional fault model allows to process all the lower level faults by means of higher level language. No disclosure of the internal stucture of the component for modeling lower level faults is needed.
In general, the functional fault model is not unique. The given set of low level faults can be covered by different high level functional faults (sets of input patterns of the module). This fact should be considered both, in hierarchical fault simulation and test generation.
4. Uniform hierarchical approach to test
The method of modeling faults by logic conditions Wr allows to unify the functional level fault simulation for components of a circuit without going into structural details of components and for structural defects in the communication network of components. In both cases, a condition Wr describes how a lower level fault r (either in a component or in a network) should be activated at a higher level to a given node in a circuit. The conditions Wr can be used both in fault simulation and in test generation.
Consider a node k in a circuit as the output of a module Mk. and represented by a variable xk.. Associate with the node k a set of faults
Rk = RFk È RSk
where RFk is the subset of faults in the module Mk, and RSk is a subset of structural faults (defects) in the “neighborhood” of Mk. Denote by Wr the condition when the fault r Î Rk will change the value of xk.
An arbitrary erroneous change of the value of xk (denoted by dxk = 1) can be represented formally by implication
dxk ® Ú (r Ù Wr), r Î Rk. (2)
All the suspected faults can now be determined by solving the equation
Ú (r Ù Wr) = 1, r Î Rk. (3)
In such a way we should construct for each module Mk of the circuit a list of faults Rk with logical conditions Wr for each fault r Î Rk. The conditions for functional faults r Î RFk of the module can be found, for example, by low level (gate level) test generation for the stuck-at faults in the module. When defect-oriented test method is chosen, then the activisation conditions for defects can be found by parametric defect modeling and solving the equation (1). The conditions for structural faults (or defects) in the network (in the neighbourhood of the module) can be calculated also by parametric fault modeling and solving the corresponding equations (1).