An efficient Monte Carlo (MC) method for the calculation of failure probability degradation of an SRAM cell due to negative bias temperature instability (NBTI) is proposed. In the proposed method, a particle filter is utilized to incrementally track temporal performance changes in an SRAM cell. The number of simulations required to obtain stable particle distribution is greatly reduced, by reusing the final distribution of the particles in the last time step as the initial distribution. Combining with the use of a binary classifier, with which an MC sample is quickly judged whether it causes a malfunction of the cell or not, the total number of simulations to capture the temporal change of failure probability is significantly reduced. The proposed method achieves 13.4× speed-up over the state-of-the-art method.

This paper proposes a novel and an efficient method termed hypersphere sampling to estimate the circuit yield of low-failure probability with a large number of variable sources. Importance sampling using a mean-shift Gaussian mixture distribution as an alternative distribution is used for yield estimation. Further, the proposed method is used to determine the shift locations of the Gaussian distributions. This method involves the bisection of cones whose bases are part of the hyperspheres, in order to locate probabilistically important regions of failure; the determination of these regions accelerates the convergence speed of importance sampling. Clustering of the failure samples determines the required number of Gaussian distributions. Successful static random access memory (SRAM) yield estimations of 6- to 24-dimensional problems are presented. The number of Monte Carlo trials has been reduced by 2-5 orders of magnitude as compared to conventional Monte Carlo simulation methods.

This study shows a fast simulation method of turbo codes over slow Rayleigh fading channels. The reduction of the simulation time is achieved by applying importance sampling (IS). The conventional IS method of turbo codes over Rayleigh fading channels focuses only on modification of additive white Gaussian noise (AWGN) sequences. The proposed IS method biases not only AWGNs but also channel gains of the Rayleigh fading channels. The computer runtime of the proposed method is about 1/5 of that of the conventional IS method on the evaluation of a frame error rate of 10-6. When we compare with the Monte Carlo simulation method, the proposed method needs only 1/100 simulation runtime under the condition of the same accuracy of the estimator.

This paper shows a fast estimation method of very low error rate of low-density parity-check (LDPC) codes. No analytical tool is available to evaluate performance of LDPC codes, and the traditional Monte Carlo simulation methods can not estimate the low error rate of LDPC codes due to the limitation of time. To conquer this problem, we propose another simulation method which is based on the optimal simulation probability density function (PDF). The proposed simulation PDF can also avoid the dependency between the simulation time and the number of dominant trapping sets, which is the problem of some fast simulation methods based on the error event simulation method. Additionally, we show some numerical examples to demonstrate the effectiveness of the proposed method. The simulation time of the proposed method is reduced to almost less than 1/10 of that of Cole et al.'s method under the condition of the same accuracy of the estimator.

This study shows a fast simulation method for turbo codes over an additive white class A noise (AWAN) channel. The reduction of the estimation time is achieved by applying importance sampling (IS) which is one of the variance reduction simulation methods. In order to adapt the AWAN channel, we propose a design method of a simulation probability density function (PDF) utilized in IS. The proposed simulation PDF is related to the Bhattacharyya bound to evaluate wider area of the signal space than the conventional method. Since the mean translation method, which is a conventional design method of the simulation PDF used in IS, is optimized for an additive white Gaussian noise channel, the evaluation time of the error performance of turbo codes over the AWAN channel can not be reduced. To evaluate BER of 10-8, the simulation time of the proposed method can be reduced to 1/104 under the condition of the same accuracy of the traditional Monte Carlo simulation method.

We research on an importance sampling (IS) simulation to estimate a low error probability of turbo codes. The simulation time reduction in IS depends on another probability density function (p.d.f.) called simulation p.d.f. The previous IS simulation method can not evaluate the error probability on the low SNR and waterfall region. We derive the optimal simulation p.d.f. which gives the perfect estimator. A new simulation p.d.f. design, which is related to the optimal one, is proposed to overcome the problem of the previous IS method. The proposed IS simulation can evaluate all possible error patterns. Finally, some computer simulations show that the proposed method can evaluate the error probability on the low SNR, waterfall, and error floor regions. At the evaluation of the BER of 10-7, the simulation time of the proposed method is about 1/350 times as short as that of the Monte-Carlo simulation. When the BER is less than 710-8, the proposed method requires shorter simulation time than the conventional IS method.

This paper deals with the decomposition of surface data into several fractal signal based on the parameter estimation by the Mean Likelihood and Importance Sampling (IS) based on the Monte Carlo simulations. The method is applied to the feature extraction of surface data. Assuming the stochastic models for generating the surface, the likelihood function is defined by using wavelet coefficients and the parameter are estimated based on the mean likelihood by using the IS. The approximation of the wavelet coefficients is used for estimation as well as the statistics defined for the variances of wavelet coefficients, and the likelihood function is modified by the approximation. After completing the decomposition of underlying surface data into several fractal surface, the prediction method for the fractal signal is employed based on the scale expansion based on the self-similarity of fractal geometry. After discussing the effect of additive noise, the method is applied to the feature extraction of real distribution of surface data such as the cloud and earthquakes.

Parallel concatenated convolutional codes, turbo codes, are very attractive scheme at a point of view of an error probability performance. An bit error rate (BER) evaluation for turbo codes is done by a uniform interleaver bound calculation and/or a computer simulation. The former is calculated under the assumption of uniform interleaver, and is only effective for an BER evaluation with a pseudo random interleaver. The latter dose not have any interleaver restrictions. However, for a very low BER evaluation, it takes enormous simulation time. In this paper, a new error probability evaluation method for turbo codes is proposed. It is based on the error event simulation method. For each evaluation for the predetermined error sequence, importance sampling, which is one of the fast simulation methods, is applied. To prove the effectiveness of the proposed method, numerical examples are shown. The proposed method well approximates the BER at the error floor region. Under the same accuracy, the IS estimation time at BER = 10-7 is reduced to 1/6358 of the ordinary Monte-Carlo simulation time.

We propose bit error rate (BER) evaluation methods for a trellis coded modulation (TCM) scheme over a Rayleigh fading channel by using importance sampling (IS). The simulation probability density function for AWGN and Rayleigh fading is separately designed. For efficient simulation of a system model with finite interleaver, frequency of the generation of fading sequences is reduced. The proposed method gives a good BER estimates over a Rayleigh fading channel.

We present a design method of the simulation probability density function for a trellis-coded modulation (TCM) in an impulsive noise environment. The upper bound evaluation method for the TCM scheme cannot be applied to the lognormally distributed impulsive noise, since the Chernoff bound cannot be defined. Thus the error probability can only be estimated by a computer simulation. For an evaluation of a low error probability, importance sampling (IS) is an efficient technique. A design method of the simulation probability density function, which plays an important role in IS, is proposed for the noise. The effectivity is shown by a numerical example.

This study shows the effectiveness of the simulation probability density function (p. d. f. ) based on the Bhattacharyya bound from the point of view of the twisted distribution. As a result, the simulation p. d. f. related to the Bhattacharyya bound is asymptotically optimal for the trellis coded modulation scheme under some practical conditions. And the optimality is also confirmed by a numerical example.

We investigate an importance sampling (IS) simulation of MMPP/D/1 queueing to obtain an estimate for the survivor function P(Q > q) of the queue length Q in the steady state. In Ref.[11], we studied the IS simulation of 2-state MMPP/D/1 queueing and obtained the optimal simulation distribution, but the mathematical fundation of the theory was not enough. In this paper, we construct a discrete time Markov chain model of the n-state MMPP/D/1 queueing and extend the results of Ref.[11] to the n-state MMPP/D/1. Based on the Markov chain model, we determine the optimal IS simulation distribution fo the n-state MMPP/D/1 queueing by applying the large deviations theory, especially, the sample path large deviations theory. Then, we carry out IS simulation with the obtained optimal simulation distribution. Finally, we compare the simulation results of the IS simulation with the ordinary Monte Carlo (MC) simulation. We show that, in a typical case, the ratio of the computation time of the IS simulation to that of the MC simulation is about 10-7, and the 95% confidence interval of the IS is slightly improved compared with the MC.

The importance sampling simulation technique has been exploited to obtain an accurate estimate for a very small probability which is not tractable by the ordinary Monte Carlo simulation. In this paper, we will investigate the simulation for a sample average of an output sequence from a Markov chain. The optimal simulation distribution will be characterized by the Kullback-Leibler divergence of Markov chains and geometric properties of the importance sampling simulation will be presented. As a result, an effective computation method for the optimal simulation distribution will be obtained.

The evaluation of a error probability of a trellis-coded modulation scheme by an ordinary Monte-Carlo simulation method is almost impossible since the excessive simulation time is required to evaluate it. The reduction of the number of simulation runs required is achieved by an importance sampling method, which is one of the variance reduction simulation methods. The reduction of it is attained by the modification of the probability density function, which makes errors more frequent. The error event simulation method, which evaluates the error probability of finite important error events, cannot avoid a truncation error. It is the fatal problem to evaluate the precision of the simulation result. The reason of it is how to design the simulation probability density function. We propose a evaluation method and the design methods of the simulation conditional probability density function. The proposed method simulates any error event starting at the fixed time, and the estimator of it has not the truncation error. The proposed design method approximate the optimum simulation conditional probability density function. By using the proposed method for an additive non-Gaussian noise case, the simulation time of the most effective case of the proposed method is less than 1/5600 of the ordinary Monte-Carlo method at the bit error rate of 10-6 under the condition of the same accuracy if the overhead of the selection of the error events is excluded. The simulation time of the same bit error rate is about 1/96 even if we take the overhead for the importance sampling method into account.

When bit error probability of a trellis-coded modulation (TCM) scheme becomes very small, it is almost impossible to evaluate it by an ordinary Monte-Carlo simulation method. Importance sampling is a technique of reducing the number of simulation samples required. The reduction is attained by modifying the noise to produce more errors. The low error rate can be effectively estimated by applying importance sampling. Each simulation run simulates a single error event, and importance sampling is used to make the error events more frequent. The previous design method of the probability density function in importance sampling is not suitable for the TCM scheme on an additive non-Gaussian noise channel. The main problem is how to design the probability density function of the noise used in the simulation. We propose a new design method of the simulation probability density function related to the Bhattacharyya bound. It is reduced to the same simulation probability density function of the old method when the noise is additive white Gaussian. By using the proposed method for an additive non-Gaussian noise, the reduction of simulation time is about 1/170 at bit error rate of 106 if the overhead of the calculation of the Bhattacharyya bound is ignored. Under the same condition, the reduction of the simulation time by the proposed method is 1/65 of the ordinary Monte-Carlo method even if we take the overhead for importance sampling into account.