2-bit Pseudo Random Number Generator

Hi

I should have some kind of PRNG that generates me for each clock
2 random bits. I was thinking for a start of implementing an
8-bit LSFR and just using then the last two bits as output.
I am just wondering if there is an easy way to change the seed
in each run when I initialise the temp variable? The design
should work on an FPGA in the end ;)

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

entity PRNG is
   port (
     clk : in std_logic;
     R0  : out std_logic;
     R1  : out std_logic
   );
end PRNG;


architecture Behavior of PRNG is

begin

   process(clk)
     variable temp : std_logic_vector(7 downto 0) := B"01111101";
   begin
     temp := (temp(1) xor temp(0)) & temp(7 downto 1);
     R0 <= temp(0);
     R1 <= temp(1);
   end process;

end architecture Behavior;

Many thanks,
Clemens

On Mon, 19 May 2008 13:44:21 +0100, Clemens wrote:

>I should have some kind of PRNG that generates me for each clock
>2 random bits. I was thinking for a start of implementing an
>8-bit LSFR and just using then the last two bits as output.

Don't do that.  R(0) on the next clock will then be exactly
the same as R(1) on this clock.  Not very random-like.

Consider using two separate LFSRs of different lengths to 
generate the two bits.

>I am just wondering if there is an easy way to change the seed
>in each run when I initialise the temp variable?

So, on an FPGA what do you mean by "on each run"?  Do you want
each build of the FPGA to have a different seed, or do you want 
the FPGA to choose a different seed each time it powers-up?
The first of these is achieved by cunning scripts, the second
probably by exploiting some variable physical behaviour such as
the value of a real-time clock.  I guess it's fair to say that
*either* there must be something nonvolatile in your system
that can keep track of time-of-day, or perhaps save some 
state across power cycles; *or* there must be some way to
measure a physical effect at the moment you start up.
-- 
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.

> Don't do that.  R(0) on the next clock will then be exactly
> the same as R(1) on this clock.  Not very random-like.
> 
> Consider using two separate LFSRs of different lengths to 
> generate the two bits.

Thanks Jonathan, I just saw this not very random like behaviour in the
simulator ;). So I am thinking of using two 16-bit LFSRs with different
seeds each providing one bit of information.

> So, on an FPGA what do you mean by "on each run"?  Do you want
> each build of the FPGA to have a different seed, or do you want 
> the FPGA to choose a different seed each time it powers-up?

A different seed for each power-up would have been nice. Its not in an
end product, I am just doing some "research" and it would be interesting
to evaluate the behaviour of my implementation with different seeds for 
different runs. If the worst comes to the worst I have to sythesise the
design with a different hardcoded seeds each time...

Cheers,
Clemens

On 19 Mai, 15:20, Clemens <Clem...@hotmail.com> wrote:

> A different seed for each power-up would have been nice. Its not in an
> end product, I am just doing some "research" and it would be interesting
> to evaluate the behaviour of my implementation with different seeds for
> different runs. If the worst comes to the worst I have to sythesise the
> design with a different hardcoded seeds each time...

Run the LFSRs continously and start your application with a
pushbutton.
This should produce enough randomness for requirements as low as
yours.

Kolja

Clemens wrote:
> 
>> Don't do that.  R(0) on the next clock will then be exactly
>> the same as R(1) on this clock.  Not very random-like.
>>
>> Consider using two separate LFSRs of different lengths to generate the 
>> two bits.
> 
> Thanks Jonathan, I just saw this not very random like behaviour in the
> simulator ;). So I am thinking of using two 16-bit LFSRs with different
> seeds each providing one bit of information.

You could also modify the LFSR to make it perform several steps at each 
clock cycle.

Clemens wrote:
> 
>> Don't do that.  R(0) on the next clock will then be exactly
>> the same as R(1) on this clock.  Not very random-like.
>>
>> Consider using two separate LFSRs of different lengths to generate the 
>> two bits.
> 
> Thanks Jonathan, I just saw this not very random like behaviour in the
> simulator ;). So I am thinking of using two 16-bit LFSRs with different
> seeds each providing one bit of information.
> 
>> So, on an FPGA what do you mean by "on each run"?  Do you want
>> each build of the FPGA to have a different seed, or do you want the 
>> FPGA to choose a different seed each time it powers-up?
> 
> A different seed for each power-up would have been nice. Its not in an
> end product, I am just doing some "research" and it would be interesting
> to evaluate the behaviour of my implementation with different seeds for 
> different runs. If the worst comes to the worst I have to sythesise the
> design with a different hardcoded seeds each time...
> 
> Cheers,
> Clemens

Not sure it matters in your application, but two 16-bit LFSRs still only 
provide as much randomness as one 16-bit LFSR, i.e. you still have a 
repetition length of 2^16-1.  Conversely, a 16-bit LFSR feeding one bit, 
and a 15-bit LFSR feeding the other, have a much higher repetition length.

--
Rob Gaddi, Highland Technology
Email address is currently out of order

Clemens wrote:

> A different seed for each power-up would have been nice.

Here's a method I've used for this in the past:

Create a ring oscillator that can be stopped by some other bit. The ring 
oscillator drives a 2-bit ripple counter.

Once the FPGA clock starts up, count off say 1 second's worth pulses of 
your high speed system clock and then disable the ring oscillator. The 
ripple counter will now have your 4-bit random value.

This method relies on slight differences in the ring osc rate due to 
heating, etc. to add up over 1 second at startup. You might need to 
experiment with adding buffers (and make sure the tools don't remove 
them) and such to make sure the ring osc rate is not too high.

-Jeff

"Jeff Cunningham" <jcc@sover.net> wrote in message 
news:483200e3$0$11170$4d3efbfe@news.sover.net...
> Clemens wrote:
>
>> A different seed for each power-up would have been nice.
>
> Here's a method I've used for this in the past:
>
> Create a ring oscillator that can be stopped by some other bit. The ring 
> oscillator drives a 2-bit ripple counter.
>
> Once the FPGA clock starts up, count off say 1 second's worth pulses of 
> your high speed system clock and then disable the ring oscillator. The 
> ripple counter will now have your 4-bit random value.
>
> This method relies on slight differences in the ring osc rate due to 
> heating, etc. to add up over 1 second at startup. You might need to 
> experiment with adding buffers (and make sure the tools don't remove them) 
> and such to make sure the ring osc rate is not too high.
>
> -Jeff

Hi Jeff,

I've heard that ring oscillators can phase lock to other clocks on the same 
die. What did you find? I came across  this link that gives some insights 
into the pitfalls.
http://warmcat.com/_wp/

Now, this guy really knows how to do random!
http://inventgeek.com/Projects/alpharad/overview.aspx

Cheers, Syms.

Symon wrote:
> "Jeff Cunningham" <jcc@sover.net> wrote in message 
> news:483200e3$0$11170$4d3efbfe@news.sover.net...
>> Clemens wrote:
>>
>>> A different seed for each power-up would have been nice.
>> Here's a method I've used for this in the past:
>>
>> Create a ring oscillator that can be stopped by some other bit. The ring 
>> oscillator drives a 2-bit ripple counter.
>>
>> Once the FPGA clock starts up, count off say 1 second's worth pulses of 
>> your high speed system clock and then disable the ring oscillator. The 
>> ripple counter will now have your 4-bit random value.
>>
>> This method relies on slight differences in the ring osc rate due to 
>> heating, etc. to add up over 1 second at startup. You might need to 
>> experiment with adding buffers (and make sure the tools don't remove them) 
>> and such to make sure the ring osc rate is not too high.
>>
>> -Jeff
> 
> Hi Jeff,
> 
> I've heard that ring oscillators can phase lock to other clocks on the same 
> die. What did you find? I came across  this link that gives some insights 
> into the pitfalls.
> http://warmcat.com/_wp/

Hi Syms,

To generate one number at startup it seemed to work fine, though I admit 
I didn't subject it to statistical analysis beyond just looking a a 
bunch of samples. I actually used it to create a GUID that would be 
stored in flash the first time the product was ever turned on. The goal 
was that no two devices would have the same number. It seemed to work 
well for that. Maybe not a good technique for crypto.

Interesting web site though.

-Jeff

Hi Clemens,
one simple solution:
add an RC-circuit to one of your FPGAs inputs.
(
R VCC IO
C IO  GND
)

Connect the IO to the Enable input of some cunning counter or LFSR, 
whatsoever, which is clocked as fast as possible. Make sure that the 
time constant of the RC-Circuit is significantly greater than the clock 
period.
The (e.g.) counter should stop, when the input goes High. Then you can 
use it's output as your seed value.

Due to variations in temperature, humidity etc. the seed value should 
be different on each powerup of the board.

If you are very clever, you can use an LDR or NTC/PTC resistor or some 
other resistive or capacitive sensor in your circuit to increase the effect.

I know there are drawbacks in effectiveness, but it's just a simple toy 
solution and better than nothing.

Have a nice synthesis
   Eilert



Clemens schrieb:
> 
>> Don't do that.  R(0) on the next clock will then be exactly
>> the same as R(1) on this clock.  Not very random-like.
>>
>> Consider using two separate LFSRs of different lengths to generate the 
>> two bits.
> 
> Thanks Jonathan, I just saw this not very random like behaviour in the
> simulator ;). So I am thinking of using two 16-bit LFSRs with different
> seeds each providing one bit of information.
> 
>> So, on an FPGA what do you mean by "on each run"?  Do you want
>> each build of the FPGA to have a different seed, or do you want the 
>> FPGA to choose a different seed each time it powers-up?
> 
> A different seed for each power-up would have been nice. Its not in an
> end product, I am just doing some "research" and it would be interesting
> to evaluate the behaviour of my implementation with different seeds for 
> different runs. If the worst comes to the worst I have to sythesise the
> design with a different hardcoded seeds each time...
> 
> Cheers,
> Clemens