STATISTICAL FAULT SIMULATION. JINS DAVIS ALEXANDER , GRADUATE STUDENT , AUBURN UNIVERSITY. ABSTRACT: Fault simulation is used for the development or evaluation of manufacturing tests. However with the increase in the number of gates in the circuit, the number of faults increases proportionally resulting in high computational time for a complete fault simulation. The complexity is found to increase at least as the square of the number of gates and thus is exponential in nature. To overcome the high computational requirements, statistical sampling methods have been proposed. In fault sampling, a subset of the total faults known as fault sample is used for simulation. The fault coverage obtained in this simulation is then used to estimate the fault coverage of the complete fault list within a small error range. Since the fault sample is small compared to the actual fault set, the reduction in computation is great. The sample size is independent of the total number of faults covered and is determined by the accuracy in which the fault coverage is to be estimated. In this paper, we conduct a study on statistical fault simulation looking at the various sampling schemes proposed and its applications. We also look briefly into the statistical theories behind the sampling techniques and do a comparative study of the results from different sampling algorithms. 1. INTRODUCTION. Fault simulation is an essential method of determining the fault coverage provided by a given test set for a given VLSI circuit. However with the increase in complexity of modern day VLSI chips, the number of faults also increases proportionately and thus the time taken to conduct a exhaustive fault simulation has increased exponentially. The complexity of fault simulators is known to grow at least as the square of the number of gates in the circuit as experimentally shown in [1]. Despite methods like fault dropping, parallel, concurrent, deductive, differential fault simulation or the use of specialized fault simulation accelerators[2] , the simulation time is still quite high which is a serious limitation in the field of VLSI testing Fault sampling was introduced to estimated the fault coverage of a given test vector at a fraction of the time taken by an exhaustive fault simulation. In this technique a subset of faults is randomly selected from the total number of faults to be simulated. This subset known as a fault sample is then used fault simulated to give an estimated fault coverage known as sample coverage [3]. From this sample coverage the actual fault coverage of the test vectors is estimated within a small error range. Since the fault sample is much smaller compared to the actual fault set, the simulation time taken is greatly reduced. The accuracy of the estimated fault coverage will depend of the size of the sample taken. A larger sample would give a more precise estimate. Thus the size of the sample is independent of the actual total number of faults, but is based on the accuracy by which the sample coverage is desired to be estimated. The rest of this paper is organized as follows: Section 2. looks into the statistical theories behind sampling and how it is used in fault sampling. Section 3. involves a discussion of the various sampling techniques proposed in literature and its applications in fault simulation. Section 4. is a brief look into the results from some of the above mentioned sampling techniques. Section 5. concludes this paper. 2. THEORECTICAL BACKGROUND. To understand the various the fault sampling applications, a brief look into the basics of statistical theory and how the sample coverage is an estimate for the true value coverage and the resulting coverage estimate. Consider an event involving the flipping of a fair coin. If getting a head is asuccess and tails a failure, then the probability of getting a success is 0.5 and failure is 0.5 for one flip of a coin. For n such trials if we want k success the probability is given by P (k success in n trials) = knpk qn-k Here k is referred to as binomial random variable and the distribution of probabilities of possible outcomes is known as binomial distribution [9]. This applies any system in which each trial described by the probability distribution is independent of each other. Events of this kind is also known as sampling with replacement. If the trials are dependent on each other then probability of success or failure is changed with each trial. This also known as sampling with replacement and fault sampling is an experiment of this type. The probability of success is described by: P (k success in n trials) = +−nwrknwkr where r is the number of possible successes and w the number of possible failures. Such kind of a distribution is known as hyper geometric distribution. In fault sampling a success is defined as a fault detected and a failure is an undetected fault. Being a hyper geometric distribution, one can estimate the probability of the sample fault coverage i.e. the number of detected faults from the total number of sampled faults using notation adopted from [3]: Np - actual total number of faults. C - actual fault coverage (un known and to be estimated). C Np - actual number of detected faults. Ns - number of randomly sampled faults. x - sample coverage determined from sample fault simulation x Ns - number of sampled faults detected. Thus from the above hyper geometric distribution we get: P (sample coverage) = −−NsNpNsxNpCxNsCNs)1()1( If the probability density function is approximated to a Gaussian probability distribution then the true value coverage can be represented as the mean of the sample fault coverage, showing that the sample coverage is an unbiased estimate of the true coverage [3]. From [14], the three sigma range or the