Random Generators
(Last update May 13 2017)
Random
numbers are often needed for test signals, for dithering undesired
carriers and to create seeds for the generation of cryptographic keys.
It may sound surprising but random data, for analog thinking people
let's call it noise, is an important and very hard to achieve signal!
Analog Noise
Generators
In theory every
physical process generates noise. This is a basic property of quantum
physics. So the easiest way to achieve a noise signal is to simply
amplify thermal noise of a resistor or shot noise of a semiconductor
junction. Zener diodes too can be very noisy. So a first draft circuit
could look like this:
Fig. 1 analog noise generator
Zener noise of Q1 gets amplified by OP1. At pin AOUT an analog random
signal is available. Comparator COMP1 converts the analog signal into a
random bit stream available at output DOUT. But is it really pure noise? No!
In a true random signal it should be impossible to guess what will be a
future state knowing past states. The circuit shown suffers from
various imperfections:
1. Zener noise is not pure noise. Depending on the electrical field
inside the junction certain amplitudes are preferred.
2. Amplifier OP may have an offset that leads to different likelyhoods
for a logic 1 or a logic 0 at output DOUT.
3. To reduce the effect of offsets the DC gain of the amplifier is 1
while the AC gain is 10. The chance of a 0101.. pattern is surely
higher than the chance of a 00000011111111 pattern below the cut off
frequency of R2 and C.
4. Neither OP1 nor COMP1 are unlimited fast. So every signal will have
successors with identical data (at DOUT) or similar voltage (at AOUT)
5. Since OP1 and COMP1 have a limited supply rejection any modulation
of the supply will change the statistics of this analog generator.
6. Slightest electromagnetic interference will also change the
statistics.
To achieve reasonably good random signals using physical effects is
tricky because it requires:
- Amplifiers with excellent supply rejection
- Fast Amplifiers.
- Low Offset.
- Good shielding against unwanted periodic (or otherwise predictable)
disturbance.
- High bandwidth circuits.
Conclusion: Creating noise or random numbers from physical effects is
expensive and error prone.
Digital Noise
Generators
Digital noise
generators basically produce very long data streams with a quasi random
sequence of ones and zeros. With an 8 bit shift register and some XOR
gates in the feedback path the data stream is already 256 bit long.
With a 16 bit shift register the stream starts to repeat after 65536
bit. Making the register longer and longer we get closer to real random
(although we never reach real random).
Fig. 2: Digital Random Generator
The example of figure 2 produces a stream of 256 bit length. After
reset the content of the shift register is 00000000. To start the
random sequence a 1 is needed as a seed. This 1 is produced by the or
gates in the upper feedback path.
Once the shift register is running the lower feed back path with the
XNOR gates produces the quasi random sequence.
If you want to play with some behavioral verilog code, here it is:
module RANDOM8 (OUT, CLK, RESET);
input CLK, RESET;
output OUT;
reg[7:0] SH;
reg xnor1, xnor2, xnor3;
wire OUT;
always @ (RESET or posedge CLK) begin
if (RESET==1) #1 SH=0;
else begin
if (SH==0) #1
SH[0]<=1;
else begin
xnor1=(SH[1]~^SH[2]);
xnor2=(SH[4]~^SH[7]);
xnor3=(xnor1~^xnor2);
SH[7]<=SH[6];
SH[6]<=SH[5];
SH[5]<=SH[4];
SH[4]<=SH[3];
SH[3]<=SH[2];
SH[2]<=SH[1];
SH[1]<=SH[0];
SH[0]<=xnor3;
end
end
end
assign OUT = SH[6];
endmodule
However the statistics of this digital approach is not quite clean
either. Since the signal is periodic the output signal can be regarded
as a spectrum with discrete lines with a spacing of the spectral lines
of 1/256 of the clock frequency.
The following waveforms shos the signals and the internal states of the
shift register. The bus SH[7:0] is displayd as an analog trace to
graphically represent the states.
Fig. 3: Signals of an 8 bit quasi random shift register
The two cursors mark begin and end of one period (clock period is 10
time quantas).