Random Number Generation in VHDL

Discussion in 'VHDL' started by FPGA, Jan 24, 2008.

  1. FPGA

    FPGA Guest

    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
     
    FPGA, Jan 24, 2008
    #1
    1. Advertising

  2. FPGA

    jens Guest

    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.
     
    jens, Jan 24, 2008
    #2
    1. Advertising

  3. FPGA

    Kris Vorwerk Guest

    > 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
     
    Kris Vorwerk, Jan 24, 2008
    #3
  4. FPGA

    ed Guest

    On 24 Jan., 18:54, FPGA <> wrote:
    > 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
     
    ed, Jan 24, 2008
    #4
  5. 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
     
    glen herrmannsfeldt, Jan 25, 2008
    #5
  6. FPGA

    Ann Guest

    On Jan 25, 1:01 am, glen herrmannsfeldt <> wrote:
    > 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


    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
     
    Ann, Jan 25, 2008
    #6
  7. 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:eek:ut 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" <> wrote in message
    news:...
    > 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
    >
     
    Dwayne Dilbeck, Jan 25, 2008
    #7
  8. 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
     
    glen herrmannsfeldt, Jan 25, 2008
    #8
  9. some typos:

    > achitecture processflow of generator is


    architecture

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

    1
    > end process

    ;
    > end

    ;
     
    Mike Treseler, Jan 25, 2008
    #9
  10. FPGA

    sly Guest

    Mike Treseler a écrit :
    > some typos:
    >
    >> achitecture processflow of generator is

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

    > 1
    >> end process

    > ;
    >> end

    > ;


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

    (shift register)
     
    sly, Jan 25, 2008
    #10
  11. 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" <> wrote in message
    news:...
    > some typos:
    >
    >> achitecture processflow of generator is

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

    > 1
    >> end process

    > ;
    >> end

    > ;
     
    Dwayne Dilbeck, Jan 25, 2008
    #11
  12. FPGA

    Tricky Guest


    >
    > > -- 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;
     
    Tricky, Jan 29, 2008
    #12
  13. FPGA

    Ray Andraka Guest

    glen herrmannsfeldt wrote:

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


    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.
     
    Ray Andraka, Feb 21, 2008
    #13
  14. FPGA

    Guest

    >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).
     
    , Feb 21, 2008
    #14
  15. FPGA

    Ray Andraka Guest

    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.

    >
    >
    > 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.
     
    Ray Andraka, Feb 21, 2008
    #15
  16. Ray Andraka wrote:
    > 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.

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


    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
     
    Jim Granville, Feb 21, 2008
    #16
  17. FPGA

    Ray Andraka Guest

    Jim Granville wrote:

    > Ray Andraka wrote:
    >
    >> 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.
    >>>
    >>>
    >>>
    >>>
    >>> 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.

    >
    >
    > 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.
     
    Ray Andraka, Feb 22, 2008
    #17
  18. FPGA

    Aragorn Guest

    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
     
    Aragorn, Mar 3, 2008
    #18
  19. FPGA

    Eric Smith Guest

    Aragorn <> 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.
     
    Eric Smith, Mar 3, 2008
    #19
  20. FPGA

    David Binnie Guest

    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" <> wrote in message
    news:...
    > 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
     
    David Binnie, Mar 3, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dpi

    Random Number Generation

    dpi, Mar 13, 2006, in forum: VHDL
    Replies:
    4
    Views:
    10,176
    vipinlal
    Mar 26, 2010
  2. ANM
    Replies:
    2
    Views:
    1,422
    Thomas Schodt
    Mar 7, 2004
  3. mescaline
    Replies:
    4
    Views:
    1,377
    Cy Edmunds
    Sep 10, 2003
  4. globalrev
    Replies:
    4
    Views:
    796
    Gabriel Genellina
    Apr 20, 2008
  5. VK
    Replies:
    15
    Views:
    1,279
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page