EDN Access--12.05.96 Efficient algorithm generates random signal
|Design IdeasDecember 5, 1996|
Efficient algorithm generates random signal
Ove Johansson, CelsiusTech Systems, Stockholm, SwedenA common way to simulate a sequence of bandwidth-limited-noise samples is to start with a sequence of uncorrelated random numbers that have a suitable distribution and then pass that sequence through a filter. Unfortunately, filtering affects the signal level, and the complexity of the filter makes computations inefficient. Alternatively, the VHDL algorithm in Listing 1 requires very little computation, and the bandwidth parameter that controls the algorithm does not affect the mean or the standard deviation of the random signal. Thus, the algorithm generates a bandwidth-limited random signal with a normal distribution.
The algorithm is based on the central limit theorem, which states that if U is a stochastic variable with a uniform distribution over the interval [0..A] with a mean of
and a variance of
and if S is a sum of N independent samples of U, then S has a normal distribution with
With a simple, linear transformation, you can obtain a N(0, 1) distribution (a normal distribution with a mean of 0 and a standard deviation of 1) as follows:
The code in Listing 1 initiates the C function when the bandwidth parameter is greater than 0. This initiation includes the calculation of a few constants, the generation of a set of random numbers and their sum, and it returns the first number with N(0, 1) distribution. Repeating the initiation process produces a sequence of uncorrelated numbers, which correspond to wideband Gaussian noise.
If, however, the program doesn't replace all elements of the sum but only replaces M of the N elements, the numbers correlate and the noise is narrowband (but still Gaussian) and normalized, as with the variable SS in the above equation. The next task is to obtain a relation that expresses M and N in terms of bandwidth and sampling frequency.
If the program replaces one element each time, N iterations are necessary before all reminiscences of the first value are completely gone. The autocorrelation function linearly decreases to zero over this interval. In other words, the autocorrelation function is an isosceles triangle that drops to zero after N/M iterations. Thus, the spectral density function is of the form sin(x)/x, which is 3-dB down at x=1.39.
The listingsets M to 1 to obtain the fastest execution and then calculates N. On subsequent calls with the parameter "=0.0'', the program returns new random numbers but replaces only one of the uniformly distributed numbers in the sum. Click here to download DI-SIG, #1964. (DI #1964)
|/* Constants: MAXLENGTH, must be large enough for the */
/* highest possible value of N. */
/* A is the range of U. */
/* SAMPLINGFREQ in the same units as Bw. */
/* M_PI = 3.14159... */
double Normal( float Bw )
static int N, ptr, SumOfRandom, Uniform[MAXLENGTH];
static double c0, c1, c2;
if ( Bw > 0.0 ) /* Initiate */
c0 = 1.39*SAMPLINGFREQ/M_PI;
N = (int)(0.5 + c0/Bw);
c1 = sqrt(12/(double)N)/(double)A;
c2 = 0.5 * sqrt(12 * (double)N);
SumOfRandom = 0.0;
for (ptr=0; ptr
Uniform[ptr] = random(A);
SumOfRandom += Uniform[ptr];
ptr = 0;
else /* Calculate random number */
SumOfRandom -= Uniform[ptr];
Uniform[ptr] = random(A);
SumOfRandom += Uniform[ptr++];
ptr %= N;
return ( c1 * SumOfRandom - c2 );
} /* Normal */
Copyright c 1996 EDN Magazine. EDN is a registered trademark of Reed Properties Inc, used under license.