# Generate desired random number in range in verilog

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

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

3. ## Re: Generate desired random number in range in verilog

Originally Posted by ThisIsNotSam
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. ## Re: Generate desired random number in range in verilog

Originally Posted by tayyab786
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.

•

5. ## Re: Generate desired random number in range in verilog

Originally Posted by ThisIsNotSam
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. ## 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 - - -

Originally Posted by ThisIsNotSam
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.

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

1 members found this post helpful.

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

•

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

12. ## Re: Generate desired random number in range in verilog

Originally Posted by KlausST
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. ## 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. ## [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. ## 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. ## 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. ## 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. ## 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.

19. ## 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. ## Re: Generate desired random number in range in verilog

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

•

--[[ ]]--