Random Number Generation in VHDL

Good luck with the random numbers, but if you want pseudo-random:

Xilinx also has an excellent document on LFSRs with polynomials up to about 1000 bits or so.

google is your friend :)

The answer to this question will depend on the FPGA architecture that you're using, as well as your needs for cryptographic security. This is because, when it comes to pseudo-random number generation, "best" can be subjective. e.g., "best" speed? "best" area? "best" power consumption? "best" random numbers (cryptographically secure)?

This is a well-studied area; I recommend that you do some reading to see what suits you ...

Kris

Hello FPGA,

Maybe it's off-topic for you, because you want to implement in FPGA rather than simulating your design, but have you seen this package :

?

Ed

LFSR are pretty popular for random numbers, and very easy to implement in an FPGA.

-- glen

I just found out that I need random number generator just for simulation. I do not need to synthesize it. Some feedback on this would be helpful. I am having a look at some of the links posted here.

Thanks

OK, that's easy. The math_real package contains an excellent random number generator that you can adapt for your own purposes.

use ieee.math_real.all; ... process variable R: real; variable S1, S2: positive := 42; --- seed variables, change initialization to --- get a different random number stream begin ... uniform(S1, S2, R); ...

This modifies seed variables S1 and S2 ready for the next call to uniform() - DON'T DO ANYTHING ELSE with these two variables. And it also puts a random number into R, uniformly distributed in the real range 0.0 to

0.99999...; you can then very easily scale this number to get whatever you want. A couple of examples:

--- Get the integer value "5" with 20% probability, --- and "7" with 80% probability if R < 0.2 then x := 5; else x := 7; end if; --- --- Get an integer in the range LO to HI (where LO, HI --- are both integers and LO

Not so easy, it seems: apologies for this off-by-one error...

That should be R := R * real(HI+1-LO) + real(LO);

Sorry

-- Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK snipped-for-privacy@MYCOMPANY.com

The contents of this message may contain personal views which are not the views of Doulos Ltd., unless specifically stated.

I usually use a maximal LFSR to obtain psuedo random numbers.

The following link will give you some good information.

I like Appendix B wich lists the tap points up to 168bits for a maximal length LFSR.

The following would generate psudeo random 64 bit numbers starting with seed value 1.

entity generator is port ( clk:in bit; a:out bit_vector(63 downto 0)); end;

achitecture processflow of generator is beg>

aaargh.... note that this gives you one pseudo-random BIT per clock cycle.... but the 64-bit words are painfully strongly correlated from one cycle to the next. You need to clock your N-bit LFSR for at least N cycles before pulling the next N-bit value from it.

Even then, the random numbers aren't brilliantly random (or at least that's what I am led to understand - I don't have a particularly good grip on the somewhat scary math) but LFSRs are indeed a good source of quasi-random stuff for non-critical applications. Just remember to clock them enough times!

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which 
are not the views of Doulos Ltd., unless specifically stated.

Ann wrote: (snip)

LFSR are fairly popular now for software implementations, though linear congruential generators are also still popular.

Linear congruential is probably easy for simulation, not quite as easy as LFSR for synthesis.

The favorite reference is Knuth, "The Art of Computer Programming", volume 2. Worth having for anyone working with computers.

-- glen

some typos:

architecture

1 ; ;

Mike Treseler a écrit :

temp := temp(62 downto 0) & (temp(63) xor temp(62) );

(shift register)

I was quickly typing an example. I didn't even copy paste from my old vhdl code. or even verify the code would parse correctly. Have to leave some thing for others to do.

Sly's and Mike's corrections are what the code should have had.

It doesn't look like a very good one, either. You want one based on a primitive polynomial

which is sort of related to a prime number. There is a good explanation in "Numerical Recipes" including some primitive polynomials. The CRC32 polynomial has been well studied, and should have pretty good properties. For 64 bits you could use multiple LFSR of different lengths and generate a new value in much less than 64 cycles.

-- glen

seed

63) xor temp(62) );

I am very thankful to everyone for their feedback. I am a beginner in this field and this forum has helped me a long way. I am thankful to everyone who put in their valuable time to advise others. I appreciate it.

The math_real package has a random number function in it, uniform. It generates reals between 0 and 1. you can use this to easily generate an integer, which can then be converted to anything.

I created this function specifically for testbenches:

--min and max can be swapped quite happily procedure rand_int( variable seed1, seed2 : inout positive; min, max : in integer; result : out integer) is variable rand : real; begin uniform(seed1, seed2, rand); result := integer(real(min) + (rand * (real(max)-real(min)) ) ); end procedure;

Ahem... if you'd read my correction to my own post, you might have spotted that this is in fact wrong... Your function's probability of getting exactly "max" or "min" is only half the probability of getting any other values in the range. To see why, consider this:

max = 3, min = 0 So real(max) - real(min) = 3.0 and rand is in the range 0.0 ... 1.0 (not quite 1.0) so rand*(real(max)-real(min)) is in range 0.0 ... 3.0

The conversion integer(some_real) rounds to the nearest whole number, so...

0.0 .... 0.5 rounds to 0 0.5 .... 1.5 rounds to 1 1.5 .... 2.5 rounds to 2 2.5 .... 3.0 rounds to 3

Clearly the integers 0 and 3 have only a "width" of 0.5, whereas all the other values have a "width" of 1.0 and thus the edge values have only half the probability.

My solution yields a uniform integer distribution. Note also that I used "floor()" from math_real to be sure that there's no risk of getting (max+1).

Getting these probability distribution things just right is often quite a bit of work. That's why I and many others are unimpressed with the argument that "VHDL random generation is just as good as SystemVerilog's constraint solver because you can write whatever you need in VHDL". The better solution to this problem, surely, is...

rand int N; constraint N_uniform { N inside {[min:max]}; }

or whatever is the right syntax in your chosen testbench automation language. Traditional procedural languages just don't cut it for smart randomization.

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which 
are not the views of Doulos Ltd., unless specifically stated.

That's great for testbenching, but it isn't helpful for implementation in an FPGA.

LFSRs are fine for a psuedo-random sequence. If it needs to be truely random however (such as with crypto), an LFSR is not suitable because the output is predictable given the history. If you do use an LFSR, take only one bit per clock of the LFSR, as the bits are highly correlated in the shift register.

My former employee, Jennifer Brady (who did much of the algorithm work for my ultra-fast FFT core), recently finished her master's thesis on random number generation in FPGAs. I know she looked at distribution as well as randomness in her study. I don't have her conclusions or dissertation, but I have asked her to chime in here.