Search

An oscillator-based true random number generator (TRNG) is experimentally demonstrated by exploiting inherently stochastic threshold switching in the insulator-to-metal transition (IMT) in vanadium dioxide. Through experimentation and modeling, we show that the origin of stochasticity arises from small perturbations in the nanoscale domain structure, which are then subsequently amplified through a positive feedback process. Within a 1T1R oscillator, the stochastic cycle-to-cycle variations in the IMT trigger voltage result in random timing jitter, which is harnessed for a TRNG. The randomness of the IMT TRNG output is validated using the NIST SP800-22 statistical test.

Constrained random simulation is becoming the mainstream methodology to verify system-wide properties in functional verification. It is a must to develop a high-throughput constrained random pattern generator, which is able to support arbitrary distribution. In this paper, we propose a novel range-splitting heuristic and a solution-density estimation technique to conquer the challenges of random pattern generators proposed in the recent literature. The solution densities can significantly increase by pruning infeasible subspaces. On the other hand, the estimated solution densities stored on a range-splitting tree statistically predict the distribution of solutions. Therefore, the generated patterns are ensured to meet the desired distribution with high throughput. Experimental results show that our framework achieves more than 10X speedup on average when compared to a commercial generator.

A novel, simple and efficient method for the generation of Tikhonov (a.k.a. von Mises) random variates is proposed. In the proposed method, circular variates of a prescribed Tikhonov distribution pT(x;alpha,xi) are generated via the transformation of variates selected randomly, on a one-for-one basis, from a bank of K distinct Cauchy and Gaussian generators. The mutually exclusive probabilities of sampling from each of the Cauchy or Gaussian generators, as well as the variance and half-width parameters that specify the latter, are derived directly from the Cauchy, Gaussian and Tikhonov characteristic functions, all of which are either known or given in closed form. The proposed random mixture technique is extremely efficient in that a single pair of uniform random numbers is consumed in the generation of each Tikhonov (or von Mises) sample, regardless of the prescribed concentration and centrality parameters (alpha, xi), all requiring neither the rejection of samples, nor the repetitive evaluation of computationally demanding functions. Additional attractive features of the method are as follows. By construction, the first (dominant) N circular moments of Tikhonov variates generated with the proposed random mixture technique are the ones that best approximate their corresponding theoretical values, with errors measured exactly. The exact distribution of generated Tikhonov variates is determined analytically, and its (Kullback-Leibler) divergence to the exact Tikhonov PDF is shown also analytically to be negligible. Finally, the technique establishes a connection between Tikhonov and Gaussian variates which can be exploited, e.g., in the generation of piecewise-continuous pseudo-random functions with Tikhonov-distributed outcomes.

The lack of a well-defined and meaningful measure of the quality of computer-generated correlated random variates complicates the design and comparison of generation algorithms for communications system simulation applications. This paper presents quantitative quality measures for computer-generated random variates having a multivariate Gaussian distribution or having a distribution that derives from the multivariate Gaussian distribution. These measures are, in particular, useful for digital communication system simulation applications. A theoretical basis for the definition of the measures is given and it is shown that the measures also possess useful intuitive interpretations. Examples of the use of these quality measures are provided.

We show that an optimal source code with a cost function for code symbols can be regarded as a random number generator generating a random sequence (not necessarily a sequence of fair coin bits) as the target distribution in the sense that the normalized conditional divergence between the distribution of the generated codeword distribution and the target distribution vanishes as the block length tends to infinity.

We study the signal-to-interference (SIR) performance of linear multiuser receivers in random environments, where signals from the users arrive in "random directions." Such a random environment may arise in a DS-CDMA system with random signature sequences, or in a system with antenna diversity where the randomness is due to channel fading. Assuming that such random directions can be tracked by the receiver, the resulting SIR performance is a function of the directions and therefore also random. We study the asymptotic distribution of this random performance in the regime where both the number of users K and the number of degrees of freedom N in the system are large, but keeping their ratio fixed. Our results show that for both the decorrelator and the minimum mean-square error (MMSE) receiver, the variance of the SIR distribution decreases like 1/N, and the SIR distribution is asymptotically Gaussian. We compute closed-form expressions for the asymptotic means and variances for both receivers. Simulation results are presented to verify the accuracy of the asymptotic results for finite-sized systems.

We show that the random number generator of Marsaglia and Zaman (1991) produces the successive digits of a rational b-adic number. (The b-adic number system generalizes p-adic numbers to an arbitrary integer base b.) Using continued fractions, we derive an efficient prediction algorithm for this generator.

A random number generator generates fair coin flips by processing deterministically an arbitrary source of nonideal randomness. An optimal random number generator generates asymptotically fair coin flips from a stationary ergodic source at a rate of bits per source symbol equal to the entropy rate of the source. Since optimal noiseless data compression codes produce incompressible outputs, it is natural to investigate their capabilities as optimal random number generators. We show under general conditions that optimal variable-length source codes asymptotically achieve optimal variable-length random bit generation in a rather strong sense. In particular, we show in what sense the Lempel-Ziv (1978) algorithm can be considered an optimal universal random bit generator from arbitrary stationary ergodic random sources with unknown distributions.

A routine procedure is presented to generate random number series with specified power spectral density and composite Gaussian probability distribution functions. This can be used to simulate airplane sensor outputs in the synthesis and evaluation of failure detection schemes for redundant sensor sets. An example is given comparing some statistics of simulated sensor outputs to their observed counterparts.

Upper bounds on the height of the peak sidelobe of the random array are derived using the theory of level crossings of a random process. Statistical properties of the random array beam pattern are presented and are used to calculate the expected number of up-crossings of a given level by the power pattern. Upper bounds on the peak sidelobe height are obtained using the expected number of up-crossings. The bounds are compared with computer simulation results.

In this paper, the convolution theorem is used as a fundamental tool to solve problems associated with frequency translation, amplitude modulation, sampling, and transformation of random variables. The four basic steps involved in the convolution of two functions are explained in detail using graphic techniques. It is concluded that the approach used makes possible the covering of a class of important problems at high level and in a short period of time.

Few mathematical operations are more important to the engineer than convolution and transform analysis. In this article, the operation of convolution is explored?starting with discrete rather than continuous convolution because of the relative ease of comprehension involved. With this foundation, the study is extended to continuous convolution. A proof of the convolution theorem will show that convolution and transform analysis are closely related. Of much more interest, however, is an intuitive explanation of why convolution and transform analysis techniques lead to exactly the same solution of a given problem. Perhaps the two most important applications of convolution deal with the analysis of linear systems and the sums of independent random variables?the latter problem being used to introduce discrete convolution.

Extremely fast table-lookup procedures are described for generating random numbers from an arbitrary distribution on a digital computer. The procedures sacrifice some accuracy in order to achieve this speed, but the accuracy is sufficient for most types of Monte-Carlo simulations. A method is given to eliminate the error associated with truncation for distribution functions with an infinite domain. The performance of the table-lookup methods is examined for a few common distribution functions.

Three methods are discussed to generate continuous non-negative random variates from a given hazard rate function: a) inverse Cdf, b) acceptance/rejection, and c) thinning.

The generation of "accurate" random bits is the key problem of the techniques which use random numbers. First the author establishes the accuracy requirements of a random bit generator for serial and parallel number generation. Then known methods are shown to be unsatisfactory for accurate applications. An accurate bit generator is proposed which provides a binary variable with equiprobable values within a 10-4to 10-5accuracy range.

Whereas random number generating methods are numerous, uniformly distributed analog random voltages are difficult to obtain directly. A method based upon the use of a point process is proposed, which leads to a practical noise generator with accurate uniform amplitude distribution, which is very easy to implement.

There are sampled-data systems of interest in which the sampling intervals are random variables. An example is a track-while-scan radar with a non-ideal blip scan ratio. In the statistical design of such systems it may be necessary to compute the spectral density of a random signal at the output of a random sampler. If the sampling intervals are independent, this spectral density may be determined from a complex convolution integral which, in many cases of practical interest, is easily evaluated in closed form by the method of residues. Consider a sampler which ideally operates periodically but actually misses samples with some probability. For this case the following result is obtained: the spectral density at the output of the non-ideal sampler is unchanged by replacing the non-ideal sampler by an ideal (periodic) sampler and adding to its output uncorrelated white noise of specified spectral density. When this result is used in the statistical design of a track-while-scan extrapolator it is found that the miss probability profoundly affects the system design. Neglect of this factor may, in fact, result in systems which are unstable in the mean square. This paper is to be published in the Proceedings of the First IFAC Moscow Congress by Butterworth Scientific Publications in 1960.