Random Number Generation in VHDL

[FPGA]

Hello members,

I would like to know if VHDL already has functions defined to generate
Random Numbers.

If not, which would be the best algorithm for generating random
numbers for implementation on an FPGA.

Thank you

 

[jens]

Good luck with the random numbers, but if you want pseudo-random:
http://en.wikipedia.org/wiki/LFSR.

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

 

[Kris Vorwerk]

I would like to know if VHDL already has functions defined to generate

Random Numbers.

google is your friend

http://www.velocityreviews.com/forums/t22430-random-number-generator.html

If not, which would be the best algorithm for generating random
numbers for implementation on an FPGA.

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 ...

http://en.wikipedia.org/wiki/Random_number_generator


Kris

 

[ed]

Hello members,

I would like to know if VHDL already has functions defined to generate
Random Numbers.

If not, which would be the best algorithm for generating random
numbers for implementation on an FPGA.

Thank you

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 :
http://www.janick.bergeron.com/wtb/packages/random1.vhd ?


Ed

 

[glen herrmannsfeldt]

I would like to know if VHDL already has functions defined to generate
Random Numbers.

If not, which would be the best algorithm for generating random
numbers for implementation on an FPGA.

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

-- glen

 

[Ann]

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

 

[Dwayne Dilbeck]

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

The following link will give you some good information.
www.xilinx.com/ipcenter/catalog/logicore/docs/lfsr.pdf

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;
aut bit_vector(63 downto 0));
end;


achitecture processflow of generator is
begin
CLKEDrocess
variable temp:bit_vector(63 downto 0) :=
X"0000_0000_0000_0001";
begin
temp := temp(63 downto 0 ) & (temp(63) xor temp(62) );
a <= temp;
wait until (clk = '0');
end process
end

 

[glen herrmannsfeldt]

Ann wrote:
(snip)

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.

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

 

[Mike Treseler]

some typos:

achitecture processflow of generator is

architecture

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

;

 

[sly]

Mike Treseler a écrit :

some typos:

;

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

(shift register)

 

[Dwayne Dilbeck]

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.

 

[Tricky]

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

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;

 

[Ray Andraka]

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

-- glen

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.

 

[Sky465nm]

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.

Maybe one could exploit gated clocks, signal races, metastability etc.. to
get randomness without resorting to hardware? (like transistor white noise).

 

[Ray Andraka]

Maybe one could exploit gated clocks, signal races, metastability etc.. to
get randomness without resorting to hardware? (like transistor white noise).

I think Jenny tried using ring oscillators to get a seed, but found that
given enough time the ring oscillators sync'ed up thanks to
parasitics. I was hoping she'd post here and maybe provide a link to
her thesis.

 

[Jim Granville]

I think Jenny tried using ring oscillators to get a seed, but found that
given enough time the ring oscillators sync'ed up thanks to
parasitics. I was hoping she'd post here and maybe provide a link to
her thesis.

That would always be a risk, but you could use multiple ring-osc, and
run them one at a time ?

I did find them to be very good thermometers

Targeting the metastable window would be another approach, but that
seems to be very narrow.
Be interesting to see plots of time/aperture width ..

-jg

 

[Ray Andraka]

That would always be a risk, but you could use multiple ring-osc, and
run them one at a time ?

I did find them to be very good thermometers

Targeting the metastable window would be another approach, but that
seems to be very narrow.
Be interesting to see plots of time/aperture width ..

-jg

I think one approach she was looking at was a high order LFSR seeded by
a state machine that divined the phase difference between a pair of ring
oscillators. The idea was to obtain a random seed before the ring
oscillators got a chance to sync up, and then use the LFSR to get the
random sequence. The seeding is necessary to get a random start point
in the LFSR. Still, that doesn't give a true random. I know she was
looking for techniques that would pass a battery of randomness tests,
and very few approaches actually did. I'll give her a call to try to
get her to speak up here, and maybe put her thesis up on the 'net
somewhere.

 

[Aragorn]

Hi
I am new to this group. I am an undergraduate student working on an
implementation of RSA on an FPGA. I am using a LFSR for random number
generation, but I also need a random state of the LFSR to begin with,
don't I? How do I get that? What does one do in such a case? I don't
want to restart the whole random no. generation business with a new
method!!

I want the user to get a different key each time he uses the key
generation system.

Thanks

 

[Eric Smith]

I am using a LFSR for random number
generation, but I also need a random state of the LFSR to begin with,
don't I? How do I get that?

Generally speaking, you need some source of entropy external to the FPGA.
For instance, if you put a counter in the FPGA that is clocked at a fairly
high frequency, and use it to measure the time between switch presses by a
human operator, the low bits of the counter can be used as a source of
entropy.

Another approach I've seen used is to measure how long it takes an
analog PLL to lock.

With any timing-based method, you can't get too many bits of entropy
per event, or they won't be sufficiently random.

 

[David Binnie]

Make a ring counter which nearly oscillates at 1/1024th (say) frequency as
your off-chip clock.

Divide the external clock by 1024, then compare and count the phase
difference in clock cycles.

Hey presto a random number ! (well nearly) which is different every time
you switch on.