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

FPGA wrote:

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

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

achitecture processflow of generator is
begin
CLKED:process
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" <g...@ugcs.caltech.edu> wrote in message
news:k4qdnWK4LOGX5wTa...@comcast.com...

[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 :

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.

"Mike Treseler" <mike_t...@comcast.net> wrote in message
news:5vurphF...@mid.individual.net...

[Tricky]

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

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]

glen herrmannsfeldt wrote:

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.

[Sky4...@trline5.org]

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

Sky4...@trline5.org wrote:

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]

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]

Jim Granville wrote:

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]

Aragorn <me.ar...@gmail.com> writes:
> 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.

"Aragorn" <me.ar...@gmail.com> wrote in message
news:37a00fd4-62e6-402e...@s12g2000prg.googlegroups.com...

[Ray Andraka]

You have to be careful using a ring oscillator on-chip, as chip
parasitics will cause it to sync up to other clocks on the chip, and you
will lose randomness. That said, as long as you use the ring oscillator
right at start-up before it has an opportunity to lock to the system
clock, you will probably be OK.

Alternatively, if you have two independent external clocks, you can use
a divided version of one to capture the state of a toggle flip-flop
clocked by the other (or a divided version of the other) to determine if
there are an even or odd number of clocks between successive edges.
Assuming the two clocks are truely asynchronous to one another, you will
get a good quality one bit random for each event. Use successive events
to assemble a parallel seed value (note for an LFSR you can just clock
the bits in as they occur, so there is no need to deserialize it.

Additionally, the LFSR only produces one new pseudo-random bit for each
clock, so if you need more than a 1 bit random, you need to operate the
LFSR for the number of clock cycles equal to number of bits you need.
Obviously, the LFSR has to have a long enough sequence so that only a
small fraction of the cycle is completed within your longest observation
window in order for the bits to appear random.

If your clocks really are de-correlated, then you don't need the LFSR at
all, you can just use the odd/even timing measurement of the successive
edges between the two clocks and get a good random.