Research on Real-time Generation Method of Gaussian Random Noise

Abstract: A hardware-oriented Gaussian random noise generation method for mean and variance is proposed. The traditional Monte Carlo method is used to realize the rapid conversion of uniformly distributed noise to identically distributed noise. The mapping function method is used to achieve a transition to reduce the amount of calculations at random. Experiments prove that this method has the advantages of fast and high precision.

Gaussian random noise has important value in signal analysis and processing. This article specifically discusses a hardware-oriented algorithm for rapid generation of Gaussian noise. The principle of the algorithm is to transform the uniform noise into Gaussian random noise through the mapping table method. This method occupies small memory, fast calculation speed and high precision. Experiments show that this method can add Gaussian noise to video images in real time.

figure 1

The principle block diagram is shown in Figure 1. The left half of Figure 1 is the part of uniform noise generation, adopting the modulus remainder method, relying on the existing K random number seeds to continuously generate new random numbers and output them to the outside. The right half of Figure 1 uses the output value of the left half to generate the mapping table address, and outputs the result obtained after the table lookup, which is the required Gaussian noise value result.

1 Generate uniformly distributed noise

Let x (1), ..., x (k) be the given k random numbers, evenly distributed in (-X, X), and independent of each other. The k + 1th random number is obtained by adding x (1) and x (k) according to modulo X:

That is, x (k + 1) is still a random number between (-X, X). In the next operation, move x (k + 1) to the position of x (k), xk) to x (k-1), ..., x (2) to x {1}, and then do the modulo X operation, add to get x (k + 2), so loop, generate sequence {xn}.

First discuss the above modular X operation. For processors using complement operations, as long as X is taken as the processor word length, the usual addition is modulo addition without considering carry.

Then use the data structure to achieve the above cycle mechanism. Set two pointers: head pointer head and tail pointer tail. After calculating the noise value, both pointers must move down one position. When it reaches the end of the sequence, it refers to the head of the sequence again, that is, it is calculated by adding 1 modulo K:

For the convenience of calculation, choose K as 256. If head and lnil pointers are used as relative offset addresses, 1 byte can be used for storage. If the overflow is not considered after the addition operation, it is equivalent to the addition of modulo 256 operation.

2 Mapping Gaussian noise

In order to quickly generate Gaussian noise from uniform noise, the mapping function method is used. The algorithm principle is shown in Figure 2.

The independent variable y of the normal distribution function is reasonably discretized to obtain a series of function values ​​to form a sequence. Then map any number yi in this sequence to a certain inter-cell segment [xi0, xi1] on the number axis x, where ‖xi1－xi0‖ = yi. Take all the values ​​in the series to get a series of inter-cells. Connect all the cells in sequence, and place the midpoint at the zero point of the number axis to form the value interval [-x, x] of the variable x. By establishing a mapping relationship between the cells on the number axis x and the y sequence, it can be proved that if the sampling interval is small enough, the random distribution in the x domain will correspond to the Gaussian distribution in the y domain.

This mapping relationship can be expressed functionally as y = f (x).

Among them, x follows a uniform distribution in the interval (-X, X), while y follows a Gaussian distribution with mean u and variance σ. The f function curve is shown in Figure 3.

When the algorithm is implemented, the Gaussian distribution value corresponding to y is quantized, and a continuous memory area [0, 2X] is allocated to x. The value of (offset address-X) of each memory unit represents the size of x value, The content of the unit stores the D value corresponding to the unit. This memory area is the required mapping lookup table. This table is versatile and can be calculated in advance. It can be used directly when needed, without further calculation.

For the (0,1) normal distribution, zi in Figure 4 is less than 1, which has no practical significance, so it is enlarged by 200 times;

Then the original mapping table is described as:

The original mapping table is relatively large, and it is roughly sampled in actual use. The quantization of the Gaussian distribution value corresponding to y does not use the standard ladder form in Figure 4, but uses the following coarse sampling form:

Result mapping table [k] = original mapping table [k · d + d / 2] (2)

Among them: sampling interval d = ∑yi / M. The quantization curve is shown in Figure 5.

It can be found from Figure 5 that the smaller parts on both sides are not cut off to 0 as in the ladder diagram, but allow non-zero values ​​to occur with a small probability. Experiments prove that this method is better.

Considering the actual situation of the Gaussian distribution, and after experiments verifying that y only takes values ​​between [-4, 4], satisfactory accuracy can be achieved. Figure 6 shows the curve of the effect of X size on noise accuracy, and the vertical axis is the average error.

It can be seen that when 2X is greater than 5500, the error reaches a very small steady state. In order to facilitate calculation, choose 2X = 213 = 8192, that is X = 212 = 4096.

Figure 7 shows the experimental results (mean value 120, variance 40): the dotted line is the standard Gaussian distribution curve, and the solid line is the noise histogram, which verifies the effectiveness of this method.

3 Precision discussion

This method mainly uses two tables: one is a table that generates uniform noise cyclically; the other is a mapping table. The values ​​of these two tables can be calculated by the method introduced earlier, only the accuracy tradeoffs are discussed below.

The accuracy requirement of 256 seeds in the circular table is directly related to the size of the mapping table, and 8192 (8K) units are used for the mapping table. Therefore, the task of the circular table is to generate uniformly distributed random numbers in the interval [-4096, 4096]. Therefore, the seed sequences x (1), ..., x (256) in the circular table are evenly distributed in [-4096, 4096]. In order to facilitate calculation, the distribution of the seed sequence is adjusted between [-(2115-1), (215-1)], that is X = 215 = 32767. Therefore, a total of 16 bits including a 1-bit sign bit can be used to store the complement of the seed number, so that the modulo X addition operation can be realized by adding the complement of the carry. The upper 13 bits of the complement operation result or the right shift by 3 bits can be directly used as the offset address of the mapping table for subsequent table lookup operations, and can be evenly distributed within [-4096, 4096].

Considering the actual situation, the variance of the Gaussian noise distribution to be sought is generally between (0, 100), and the mean is generally between [-255, 255]. The gray value of the actual image exists in the form of integer [0, 255], Therefore, the accuracy of the noise can be controlled within an integer range, and the accuracy of the mapping table is sufficient as long as it reaches 0.01. The distribution of data in the mapping table is between [-4.00, 4.00]. If stored as an integer, the original data can be stored in 16-bit length units by multiplying by 128.

The table can also be modified on this basis, so that the mean and variance of the Gaussian distribution after the mapping are directly equal to the mean u and variance σ given by the user. The modification is relatively simple, replace each cell value y in the mapping table as follows:

y = (y * σ) >> 7 + u

The data in this table can be in the original code form or the complement form, depending on the specific needs.

Follow WeChat

Interesting and informative information and technical dry goods

Download Audiophile APP

Create your own personal electronic circle

Follow the audiophile class

Lock the latest course activities and technical live broadcast