Digital noise generation in PLDs a digital noise generator based on random bits by J.S. This article describes a method to generate actual random, unpredictable bit sequences, which ggare in principle equally distributed and have no preferences. This makes it possible to generate actual random numbers, which in turn can be used as noise. For the realization in VHDL buffers must still be used as well as circuit parts must be preserved by means of "keep". The solution is chosen in a way that no PLLs or external circuitry is needed.

 

 Table of contents
1 History
2 Principle
2.1 The free-running counter
2.2 Single ring oscillator
2.3 Multiple ring oscillator
2.4 Desynchronized ring oscillators
2.5 Self-desynchronizing ring oscillators
3 Realization proposal
3.1 Realization for consumer quality
3.2 Realization for measurement
3.2.1 Construction proposal / example
4 Quality estimation
4.1 Simulation
4.2 Problems of the real circuit
4.2.1 Twister as Symmetry Aid
4.3 Measurements
4.4 Suitability as random number generator
4.4.1 Uniform distribution
4.4.2 Normal distribution
4.4.3 Other distributions
4.5 Possibilities for improvement
4.6 Suitability as a noise generator
5 Applications
5.1 Signal processing 5.2 Image processing

 

History The circuit worked at that time with CMOS inverters and a 4000 series binary counter. The last bit served as a switch between the inverter chains of different lengths.

 

Principle

 

 The idea is based on the sampling of a clock moving asynchronously to the target domain, which can change practically during every conceivable sampling process and thus can take on completely random values. The bits sampled in this way are then assembled into bytes independently of each other, which in principle also allows long sequences of ones and zeros to be created. For this, however, the asynchronous clock must be sampled comparatively slowly.

 

The free-running counter

 

 A simple circuit for the bit generator in VHDL results from a counter, from which a clock (here 1/8th - it often works also 1/4th) is derived and which can also count down due to the asynchronous feedback: signal toggle : std_logic_vector(2 downto 0) := "000"; signal clock : std_logic; p_osc : process (toggle) begin toggle <= toggle + "1"; clock <= toggle (2); end process; The division of the clock is not necessary for some FPGAs, but a simple feedback of type toggle <= not toggle; is sometimes not generated, or it is too fast to generate a clean clock. The wider the vector "toggle" is set, the greater the probability that the counter counts incorrectly and performs period jumps. However, the output frequency becomes lower. However, this simple formulation leads to very technology-dependent implementations, which vary from synthesis run to synthesis run. An example can be found in the color multiplexing module of my VGA core. A better approach is to purposefully build a self-oscillating system at the technology level.

 

Simple ring oscillator

 

 The obvious approach is a self-oscillating ring oscillator that operates independently of the target domain and can in principle represent any edge state. Such oscillators can easily be formed by feedback inverter chains, which by principle can never oscillate to a stable state and therefore always oscillate. Compared to the counter, higher clock rates are achieved. However, experience shows that such a simple oscillator usually does not jitter sufficiently to be able to generate really all conceivable combinations over ven�ftige time periods, since in the short term consideration always an interference to the sampling clock will occur. Furthermore, it turns out that such ring oscillators tend to synchronize to neighboring circuit parts. When these are triggered with the read clock, observable spectra appear in the generated bit sequences.

 

Multiple ring oscillator

A significant improvement is the use of two oscillators which interfere with each other and, depending on the time overlap, produce a sometimes very fast toggling bit by linking it to an EXOR, which already generates good random values if sampled infrequently enough. The more such oscillators are connected, the higher the probability of a bit change in the range of the sampling edge. Unfortunately, however, this arrangement of ring oscillators also tends to synchronize to influences of the residual circuitry, which manifests itself in the FFT analysis and accumulation measurement of the generated output signal. Desynchronized ring oscillators An effective way to suppress any synchronization tendencies is to permanently switch the frequencies of the oscillators so that none of them can assume a stable phase position. Just as at the beginning of the transient phase, the oscillator needs a few oscillations after switching to become reasonably stable. This is especially true if it wants to adjust to some external event. If switching is done in time, the oscillator has no chance to settle to neighboring circuits. Switching works by changing the length of the inverter chain by driving a control signal to a multiplexer that selects between two paths. In the simplest case, you just add 2 more inverters, which lowers the frequency a bit. Depending on the technology, 4 inverters are better, as this results in a more significant frequency swing. It is also crucial with this method that a phase jump is generated by the switching. If the oscillator has started to synchronize to an event, this will immediately set the relevant clock edge to another point.

 

Self-desynchronizing ring oscillators

An extension of the solution from above is now to let the timing of the switchover be determined randomly as well. This is most easily done by a similarly constructed counterpart, which in turn is again randomly controlled. In the first step, the 2-fold coupled OSC described below is created. With three self-oscillating oscillators chained in a ring like this one gets a nearly random behavior of the phase, because always one of the oscillators is in the transient process and its contribution to the exor shifts strongly, so that also in the local view no visible interference patterns appear any more.

 

Realization proposal:

Here is an example solution with 2 coupled oscillators: Each of the two OSC is formed by an inverter chain with a total odd number of inverters, where the even numbered inverter stages form a delay. The feedback is done by a multiplexer, which is switchable. For example, there are 7 and 9 inverters in the chain once, and 11 or 13 in the other. Each of the two oscillators drives its own counter, which counts up to 13 or 27. The respective highest bit of the counter is used to switch the chain length of the other oscillator. By the asymmetrical distribution 8/13 to 5/13 or 16/27 to 11/27 it is achieved that there is a longer and a shorter phase. During the longer phase one switches the lower frequency, during the longer one the higher frequency. This results in the following sequence for the chain length: OSC1 : ...7.7.7.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.9.7.7.7.7.7.7.7.7.7.7.7.9.9.9.9..... OSC2 : ....13.13.11.11.11.11.11.11.11.11.13.13.13.13.13.11.11.11.11.11.11.11.11.13.13... So oscillator 1 is allowed to oscillate alternately for a longer period at the slightly lower frequency, and then for a shorter period at the higher frequency. At some point in between, it switches the frequency of the second. Since the other behaves in the same way, there are roughly 4 frequency combinations which overlap differently and variably. The long phases of at least >5 beats ensure that even with fast technologies the respective OSC oscillates again, if it jumped into the middle of a state change during the switching. Exactly this shifts the phases again and again very randomly, so that the frequency is not stable for a long time and the oscillators cannot synchronize to environmental influences. The outputs are mixed with Exor, which still results in up to 5-10 MHz of completely random bits when sampled by another domain. /n Realization for consumer quality 16bit noise values are then obtained according to the method above at about 500kHz, in which you sample continuously and push the values into SR. For my audio workstation, I use a sampling rate of ~4.5MHz and generate 24 bit values with 192kHz sample rate from that. Patterns in the audio frequency range are not discernible in the spectrum. Initially, I had also set up several generators in parallel and mixed the 24 bit values, but found no more improvement. However, I sometimes had the case that statistically more zeros came out (53%:47%). I then simply built two similar generators (different chain lengths) and mixed one channel inversely. For my purposes this is now perfectly sufficient. For metrological purposes, one would have to examine it more closely. If you want to mix any noise sources, you should set up an extra source instead of tapping the first one as well, unless this is necessary for signal processing. When generating drum sounds, I occasionally got strange metallic-sounding cancellations when two instruments (generated by filter) sounded at the same time. A simple remedy is a bit swapper. Realization for measurement For metrological applications one should sample low enough, e.g. 1/MHz/bit. For each additional bit or MHz another generator is added, which is parameterized differently. This is only a minor problem in terms of space, since only 50-100 logic elements are needed, depending on the realization. The noise generators should sit at different places in the FPGA and should not share logic cells -> use FPGA /nor for mapping / constraints. A possible 1:0 distribution problem should be solvable with two complementary noise sources, while the allocation of the noise bits can also still be changed by using another oscillator which cyclically generates addresses selecting one of several multiplexers with alternating bit mapping. Also, several noise generators can be superimposed to increase the resolution, with the problem that results in the middle range of values are then more likely than values at the edge. If one wants to prevent this, the values are always to be linked bitwise over EXOR. Construction proposal / example An array of 2x32 noise sources (approx. 500 LEs) is read in asynchronously with a PLL-based clock of 1MHz in 64 registers. Via a 64:64 bit exchanger with randomly changing mapping, these are combined to two 32 2-bit values, which are subtracted / added complementary from each other with an exor and an inverter. The results go to a synchronous asymmetric 32:8 FiFo, which produces 8-bit noise values at 4MHz that are statistically perfectly uniformly distributed. Quality estimation Simulation Even with fixed values for the inverter delays, which are after all subject to strong randomness in real life, a ModelSIM simulation for the 2-fold solution produces a very complex pattern with a low repetition rate. In reality, a corresponding jitter can be measured, which sweeps several periods of the sampling clock. With an analog simulation, minimal changes in the switching behavior can be investigated. For example, varying the slope of only one inverter output of an oscillator by 0.5% results in a qualitatively different picture after only a few oscillations, because the switching points of the other oscillator move a little, resulting in a different phase constellation. 2 cases of coupled oscillators The two blue oscillators vary minimally, which is already visible from the resulting 2bit code (visualization of the state sequence) = violet curve. The signal value formed with an EXOR (turquoise), is sampled with an arbitrary clock in the FPGA (red), resulting in the green output value. A small change in the behavior of an inverter already causes a different output pattern; Problems of the real circuit Unfortunately, the problem arises that in case of coincident edge changes no clear signal is generated at the output of the XOR gate and the sampling FF of the target domain sees an intermediate value. Due to the non-100% balanced circuit topology in CMOS circuits, the switching threshold for the FF input is not at the 50% level, so sometimes one state (0 or 1) is preferred and occurs more frequently. This prblem can be solved by a twister: Twister as a symmetry aid. By connecting a further approx. factor 8-16 slower running random bit generator, the meaning of a bit at state 1 is inverted, which is realized by a further XOR. Thus a high number of ones suppresses itself. The statistical distribution of numbers is thus virtually inverted. Assuming an asymmetric generator delivers 60% ones and only 40% zeros, another generator of the same kind would invert 60% of the bits each. The result would be: 60% * 60% = 36% to 0 (1 changed) 40% * 60% = 24% to 1 (0 changed) 60% * 40% = 24% at 1 (1 unchanged) 40% * 40% = 16% at 0 (0 unchanged) So in the result 36%+16% = 52% zeros and 48% ones and thus considerably more symmetrical, than the input assumption. The twister has already proven itself in another context and is also suitable for other forms of random generators. Measurements FFT analysis of 2 coupled oscillators The picture (screenshot) shows an FFT analysis of artificially generated 16bit noise from two coupled oscillators. The blue area shows the mirror symmetric 1024 FFT at 16Mhz. Min, max, mean and standard deviation are automatically marked on the left. The reduced turquoise area shows the values averaged over 16 measurements reduced by a factor of 2...; Suitability as random number generator. The random bits generated in this way are usually already sufficient for good random numbers, as they are needed in simulations for technical applications. They are generated by simply stringing together several bits with a shift register. Uniform distribution Stringing bits together does not favor any number. Theoretically, every number occurs with the same frequency. Exceptions are due to technology, as described above, and can be improved by the symmetrizer. Distribution of generated numbers The graph shows the distribution of numbers generated with a noise generator. Numbers are generated with 8 concatenated bits and their accumulation is counted, where the same number occurs with a heavy emphasis about 10-40x within 4096 "throws". If the experiment is continued and summed up further, asymmetries balance out again somewhat and the curve becomes smoother. At 15000 throws, the dynamic between rare and frequent numbers is about 60-120. The variance is finally still about +/- 12% after >250,000 throws. Due to space limitations, only the first 128 numbers are shown...; Normal distribution Due to the addition of noise values, values in the middle of the number space naturally occur more frequently because there are several possible combinations of how they can occur. Values at the edge are very rare. To cover the 8-bit number space, another number was added for the rounding error. Thus the number range 0...255 is representable. Otherwise only 16x15 = 240 would be attainable. Further distributions If you want to generate specific distributions and make sure that numbers occur at least once after certain times, you have to do a little more. See Digital random number generator in VHDL. Possibilities for improvement To further increase randomness, the loop of one or more oscillators can be formed using external pins, which leads to strong temperature and copy fluctuations. This is especially advantageous when using only one oscillator. However, it reduces the maximum frequency of the generator. Suitability as a noise generator. Due to the true randomness of the values, no statements can be made about the spectral behavior, making the system suitable as a non-deterministic noise generator. No preferentially generated frequencies were observed in the test.

 

 Applications


Signal processing Random numbers are often used as initial values for deterministic random number generators

 

 Image processing

 

 Noise generators are used in image processing to improve image quality by, for example, using the "salt and pepper" method to smooth edges due to sampling artifacts.