+ Post New Thread
Results 1 to 20 of 21

27th November 2017, 20:14 #1
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 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

27th November 2017, 20:34 #2
 Join Date
 Apr 2016
 Posts
 1,342
 Helped
 232 / 232
 Points
 6,329
 Level
 18
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.

28th November 2017, 04:15 #3
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 Level
 3
Re: Generate desired random number in range in verilog
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

28th November 2017, 04:24 #4
 Join Date
 Apr 2016
 Posts
 1,342
 Helped
 232 / 232
 Points
 6,329
 Level
 18

Advertisment

28th November 2017, 04:44 #5
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 Level
 3

28th November 2017, 06:12 #6
 Join Date
 Feb 2015
 Posts
 887
 Helped
 256 / 256
 Points
 5,356
 Level
 17
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   
This scales really bad unless you implement the LFSR for this usecase. You basically want bitreversed 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 bitreversed it becomes 2**N, ... 8, 4, 2, 1.
1 members found this post helpful.

28th November 2017, 07:18 #7
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 42,690
 Helped
 13008 / 13008
 Points
 245,688
 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.

Advertisment

28th November 2017, 08:09 #8
Awards:
 Join Date
 Apr 2014
 Posts
 12,624
 Helped
 2928 / 2928
 Points
 61,937
 Level
 60
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 = N1 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.
KlausPlease don´t contact me via PM, because there is no time to respond to them. No friend requests. Thank you.
1 members found this post helpful.

Advertisment

28th November 2017, 09:30 #9
 Join Date
 Feb 2015
 Posts
 887
 Helped
 256 / 256
 Points
 5,356
 Level
 17
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.

28th November 2017, 09:49 #10
Awards:
 Join Date
 Apr 2014
 Posts
 12,624
 Helped
 2928 / 2928
 Points
 61,937
 Level
 60
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.
KlausPlease don´t contact me via PM, because there is no time to respond to them. No friend requests. Thank you.

28th November 2017, 10:39 #11
 Join Date
 Nov 2006
 Location
 Brazil
 Posts
 8,182
 Helped
 1034 / 1034
 Points
 27,344
 Level
 40
 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 )

28th November 2017, 18:21 #12
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 Level
 3

29th November 2017, 05:12 #13
 Join Date
 Feb 2015
 Posts
 887
 Helped
 256 / 256
 Points
 5,356
 Level
 17
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.

10th December 2017, 18:55 #14
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 Level
 3
[Moved]range of lfsr depend upon input value
hi
i have written the code of 8bit lfsr in verilog. its work fine e.g it randomly generate value from 1255
now i want to transform this code to general lfsr e.g if user put 35 it generate random value from 135. and so on

10th December 2017, 22:26 #15
 Join Date
 Jun 2015
 Posts
 23
 Helped
 2 / 2
 Points
 649
 Level
 5
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 135 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

11th December 2017, 02:29 #16
 Join Date
 Feb 2015
 Posts
 887
 Helped
 256 / 256
 Points
 5,356
 Level
 17
Re: Generate desired random number in range in verilog
35 might be possible. But arbitrary numbers might not be. You can create LFSRs with nonmaximal 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 skiplarger approach, there is an average time of a bit over 7 cycles per output.

11th December 2017, 03:00 #17
 Join Date
 Mar 2017
 Posts
 28
 Helped
 0 / 0
 Points
 335
 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 035 range in such a way that it randomness cannot distrube . suggest any method other than y=ax+b

11th December 2017, 07:13 #18
 Join Date
 Feb 2015
 Posts
 887
 Helped
 256 / 256
 Points
 5,356
 Level
 17
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.

11th December 2017, 17:50 #19
 Join Date
 Sep 2013
 Location
 USA
 Posts
 6,721
 Helped
 1604 / 1604
 Points
 29,150
 Level
 41
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.

11th December 2017, 18:22 #20
 Join Date
 Jun 2015
 Posts
 23
 Helped
 2 / 2
 Points
 649
 Level
 5
Re: Generate desired random number in range in verilog
Xilinx have one as well, it's old and there might be a newer around
https://www.xilinx.com/support/docum...es/xapp052.pdf

Advertisment
+ Post New Thread
Please login