+ Post New Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 21
  1. #1
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    Generate desired random number in range in verilog

    I am trying to generate a desired random number in range.

    for random number we use LFSR alogorithm. Now I want...First time LFSR output become the min number . Now in next cycle the random number should greater than previous LFSR number and so on, but it also not exceed with max value. max value is the max number which can be generate by LFSR(depend on the number of bits using in LFSR e.g 8 bit LFSR generate 255 max value)

    I know some method e.g
    min+LFSR draw back : it can exceed max value which is not desired
    fixed some bits in LFSR with min value draw back: 1.not lie in desired range 2.e.g max value is 8 and previous LFSR output is 6...Now in 8 bit how to
    fixed min value as well as LFSR output?

    Can any one suggest solution that would be applied in verilog language

    •   Alt27th November 2017, 20:14

      advertising

        
       

  2. #2
    Advanced Member level 4
    Points: 5,038, Level: 16

    Join Date
    Apr 2016
    Posts
    1,062
    Helped
    189 / 189
    Points
    5,038
    Level
    16

    Re: Generate desired random number in range in verilog

    you can keep sampling the LFSR until you find a number that fits your current criteria. it's not ideal as you will waste clock cycles. but the implementation is so trivial that is worth mentioning.

    you can add the min from previous sample to the remainder of the division of the current sample by max. this can be done in 1 cycle.
    Really, I am not Sam.



  3. #3
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    Re: Generate desired random number in range in verilog

    Quote Originally Posted by ThisIsNotSam View Post
    you can keep sampling the LFSR until you find a number that fits your current criteria. it's not ideal as you will waste clock cycles. but the implementation is so trivial that is worth mentioning.

    you can add the min from previous sample to the remainder of the division of the current sample by max. this can be done in 1 cycle.
    Not fit in current criteria e.g e.g in 3 bit LFSR, min number is 5, now next time suppose lfsr generate 3, Now according to your logic min+(lfsr_output/max value) gives 5+6=11 which is not in range. also it require floating point division which is not supportive in some FPGA, but division is not porblem the main problem is it will take less time e.g not waste any cycle or slow some clock



  4. #4
    Advanced Member level 4
    Points: 5,038, Level: 16

    Join Date
    Apr 2016
    Posts
    1,062
    Helped
    189 / 189
    Points
    5,038
    Level
    16

    Re: Generate desired random number in range in verilog

    Quote Originally Posted by tayyab786 View Post
    Not fit in current criteria e.g e.g in 3 bit LFSR, min number is 5, now next time suppose lfsr generate 3, Now according to your logic min+(lfsr_output/max value) gives 5+6=11 which is not in range. also it require floating point division which is not supportive in some FPGA, but division is not porblem the main problem is it will take less time e.g not waste any cycle or slow some clock
    What? Floating point? We are not talking about the same thing.
    Really, I am not Sam.



  5. #5
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    Re: Generate desired random number in range in verilog

    Quote Originally Posted by ThisIsNotSam View Post
    What? Floating point? We are not talking about the same thing.
    for division we require floating point division. But as i mentioned this is not problem. can you give me some example which will fit in current criteria



  6. #6
    Advanced Member level 3
    Points: 4,845, Level: 16

    Join Date
    Feb 2015
    Posts
    808
    Helped
    235 / 235
    Points
    4,845
    Level
    16

    Re: Generate desired random number in range in verilog

    It seems like you want a saturated accumulator. Basically a mux where P <= max when P+x > max else P + x; The accumulator might need an extra MSB. (the result of P+x might need it, the accumulator shouldn't actually need it, but 1 register is effectively free for an FPGA.)

    Because this is monotonically increasing, this method can be pipelined if needed, so this can work at high rates and wide bit widths -- assuming the LFSR also can run at these rates.

    Likewise, if you don't need floating point for the wide dynamic range, you might consider having something compute 1/max. perhaps a PC even.

    - - - Updated - - -

    Quote Originally Posted by ThisIsNotSam View Post
    you can keep sampling the LFSR until you find a number that fits your current criteria. it's not ideal as you will waste clock cycles. but the implementation is so trivial that is worth mentioning.
    This scales really bad unless you implement the LFSR for this use-case. You basically want bit-reversed Galois or equivalent. This is because, as you get closer to max, the number of acceptable outputs drops to a potentially very rare occurance. Galois at least will always have the sequence 1, 2, 4, 8, ... 2**N. If this is bit-reversed it becomes 2**N, ... 8, 4, 2, 1.


    1 members found this post helpful.

    •   Alt28th November 2017, 06:12

      advertising

        
       

  7. #7
    Super Moderator
    Points: 237,346, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    41,069
    Helped
    12542 / 12542
    Points
    237,346
    Level
    100

    Re: Generate desired random number in range in verilog

    To generate random number in a specific range, I would apply integer scaling y = ax+ b.



  8. #8
    Super Moderator
    Points: 53,103, Level: 56
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster

    Join Date
    Apr 2014
    Posts
    10,691
    Helped
    2534 / 2534
    Points
    53,103
    Level
    56

    Re: Generate desired random number in range in verilog

    Hi,

    How many turns you decide this should work?
    Even with a float there very soon will be the time where the result will not become bigger anymore.

    Here my integer approach:
    N = number of turns
    B = bit width of random number
    --> result bit width will be N + B + 1. With a theoretical max value of 2^(N + B + 1) -1. But it won't saturate at this value.
    *****
    For x = N-1 down to 0, stepsize = 1; x = loop counter
    Result = result + (random(x) << x)
    Next x
    *****
    It is very fast, uses low resources, doesn't need divider. It's just "SHIFT and ADD" of integer values.
    Maybe you don't need the full bit width of the result, then just take as much bits as desired beginning from the MSB.

    Klaus
    Please donīt contact me via PM, because there is no time to response to them. Thank you.


    1 members found this post helpful.

    •   Alt28th November 2017, 08:09

      advertising

        
       

  9. #9
    Advanced Member level 3
    Points: 4,845, Level: 16

    Join Date
    Feb 2015
    Posts
    808
    Helped
    235 / 235
    Points
    4,845
    Level
    16

    Re: Generate desired random number in range in verilog

    I suspect the divider is based on an unstated requirement that the final output be multiplied by 1/max and/or presented in floating point format to avoid this conversion on the endpoint.



  10. #10
    Super Moderator
    Points: 53,103, Level: 56
    Achievements:
    7 years registered
    Awards:
    Most Frequent Poster

    Join Date
    Apr 2014
    Posts
    10,691
    Helped
    2534 / 2534
    Points
    53,103
    Level
    56

    Re: Generate desired random number in range in verilog

    Hi,

    How do you come to that conclusion?

    In post#1 the OP speaks of an example with value "255", to me it sounds like an integer 8 bit value.

    Btw: in any case... then this is a division with a constant value, that can be substituted with a multiplication (faster, less resources, more suitable for PLDs)

    ...Letīs see what the OP says.

    Klaus
    Please donīt contact me via PM, because there is no time to response to them. Thank you.



  11. #11
    Super Moderator
    Points: 24,730, Level: 38
    andre_teprom's Avatar
    Join Date
    Nov 2006
    Location
    Brazil
    Posts
    7,435
    Helped
    926 / 926
    Points
    24,730
    Level
    38
    Blog Entries
    5

    Re: Generate desired random number in range in verilog

    If you have clocks in different domains and come from independent oscillators, a counter continuously overflowing from MIN to MAX could solve, the instantaneous value took from the counter being the random value obtained, but this is actually a particular case, perhaps not applicable to your design.
    --------------------------------------------------------------------------------------------------
    Part of the world that you live in, You are the part that you're giving ( Renaissance )



  12. #12
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    Re: Generate desired random number in range in verilog

    Quote Originally Posted by KlausST View Post
    Hi,

    How many turns you decide this should work?
    Even with a float there very soon will be the time where the result will not become bigger anymore.

    Here my integer approach:
    N = number of turns
    B = bit width of random number
    --> result bit width will be N + B + 1. With a theoretical max value of 2^(N + B + 1) -1. But it won't saturate at this value.
    *****
    For x = N-1 down to 0, stepsize = 1; x = loop counter
    Result = result + (random(x) << x)
    Next x
    *****
    It is very fast, uses low resources, doesn't need divider. It's just "SHIFT and ADD" of integer values.
    Maybe you don't need the full bit width of the result, then just take as much bits as desired beginning from the MSB.

    Klaus
    Thanks klaus. This approach almost 70% solve my problem



  13. #13
    Advanced Member level 3
    Points: 4,845, Level: 16

    Join Date
    Feb 2015
    Posts
    808
    Helped
    235 / 235
    Points
    4,845
    Level
    16

    Re: Generate desired random number in range in verilog

    I'm still not seeing why you can't just have a saturating accumulator. This system has to reach max eventually, ending the sequence. The logic is small and can be pipelined. The size of the accumulator can also be greater than the lfsr size. That just means that some values of max will generate a sequence that is always longer than two values. (eg, longer than min, max)

    A possible reason not to do this is if it is easier to preform everything in floating point. This is similar to what Klaus suggests in terms of resources. Either can also be pipelined. The advantage is potentially avoiding the need for multiple/large barrel shifters.



  14. #14
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    [Moved]range of lfsr depend upon input value

    hi
    i have written the code of 8-bit lfsr in verilog. its work fine e.g it randomly generate value from 1-255
    now i want to transform this code to general lfsr e.g if user put 35 it generate random value from 1-35. and so on



  15. #15
    Junior Member level 1
    Points: 540, Level: 4

    Join Date
    Jun 2015
    Posts
    19
    Helped
    2 / 2
    Points
    540
    Level
    4

    Re: range of lfsr depend upon input value

    LFSR are not real random you just the numbers will repeat in the same pattern over and over, but they are very useful for kind of random.
    Also they are build of a numbers of registers, for 8 bit you have 255 combinations (0 are not used since it will stop the xor) so to make 1-35 are not a magic numbers of registers and you have to think different.

    What you could do is to have a comparator to determinate if the number generated are greater than you limit (>35) if so the just give the LFSR another clock and you get a new "random" number and if it's within your range load it to a output register.

    Hope it makes sense



  16. #16
    Advanced Member level 3
    Points: 4,845, Level: 16

    Join Date
    Feb 2015
    Posts
    808
    Helped
    235 / 235
    Points
    4,845
    Level
    16

    Re: Generate desired random number in range in verilog

    35 might be possible. But arbitrary numbers might not be. You can create LFSRs with non-maximal lengths. For example the 5 bit lfsr using the 2 msbs as taps will not give the full length sequence. (gives a sequence of length 21, 7, or 3 based on the initial seed.) Modern computers are fairly fast, so you can probably brute force tap+seed combos until you find all sequences you want.

    Depending on what the actual requirements are, you might be able to get away with using a larger LFSR and then a table of fixed point multiplier coef's.

    For a skip-larger approach, there is an average time of a bit over 7 cycles per output.



  17. #17
    Junior Member level 3
    Points: 271, Level: 3

    Join Date
    Mar 2017
    Posts
    26
    Helped
    0 / 0
    Points
    271
    Level
    3

    Re: Generate desired random number in range in verilog

    i want to convert lfsr_output into in desired range and it does not take more than 2 cycle.. for 8 bit lfsr it max output is 255. now when user enter a value e.g 35 it convert 255 into 0-35 range in such a way that it randomness cannot distrube . suggest any method other than y=ax+b



  18. #18
    Advanced Member level 3
    Points: 4,845, Level: 16

    Join Date
    Feb 2015
    Posts
    808
    Helped
    235 / 235
    Points
    4,845
    Level
    16

    Re: Generate desired random number in range in verilog

    My advice would be to use a large lfsr. I guess a 65 bit or whatever. Just something that has no taps lower than the 18th bit. And if shouldn't be factored by 2**17 - 1. This means you can generate a 17 bit shifted version of the lfsr trivially. From there, generate a lookup table of the 24 bit coef to do the fixed point multiply.


    I don't understand what you mean here. -- "in such a way that it randomness cannot distrube" . This is not precise language.



    •   Alt11th December 2017, 07:13

      advertising

        
       

  19. #19
    Super Moderator
    Points: 27,821, Level: 40
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    6,355
    Helped
    1540 / 1540
    Points
    27,821
    Level
    40

    Re: Generate desired random number in range in verilog

    If you want specific length LFSRs then take a look at this paper, that has an extensive list of 2 and 4 tap polynomials for maximal length sequences. It's the only paper I've ever found that actually goes way past the first 40 or so lengths and has both the 2 and 4 tap versions.

    I've verified that both the 2 and 4 tap polynomials produce maximal length sequences up to 32, but didn't go any further than that.



  20. #20
    Junior Member level 1
    Points: 540, Level: 4

    Join Date
    Jun 2015
    Posts
    19
    Helped
    2 / 2
    Points
    540
    Level
    4

    Re: Generate desired random number in range in verilog

    Quote Originally Posted by ads-ee View Post
    It's the only paper I've ever found that actually goes way past the first 40 or so lengths and has both the 2 and 4 tap versions.
    Xilinx have one as well, it's old and there might be a newer around
    https://www.xilinx.com/support/docum...es/xapp052.pdf



--[[ ]]--