[SOLVED] uniformly distributed random number [0,1]

[rakeshk.r]

Hi,
I am generating the uniform random numbers using the tap number table given in this url:
**broken link removed**
Below shows the snippet of the code generating the random number in VHDL.

                    -- 39 bits tap no: 39,35 --
                    shf_reg(0) <= shf_reg(38);
                    shf_reg(34 downto 1) <= shf_reg(33 downto 0);
                    shf_reg(35) <= shf_reg(34) xnor shf_reg(38);
                    shf_reg(38 downto 36) <= shf_reg(37 downto 35);

Now I want to have this 39-bit random number in the range [0,1] then what should I do ? The suggestions you give should be synthesizable. Thank you.

 

[ads-ee]

Uh, arbitrarily place the decimal point to the left end of the 39-bit value. Not sure why this isn't obvious.

You do know that a straight implementation of an LFSR isn't necessarily that good of a random number generator. If you need a better random number generator take a look at Mother-of-all and variants.

 

[rakeshk.r]

I did move the decimal point before. But i was skeptical doing it. (Because my design when tested with matlab 'rand' function as an input, gave me the required output but with the lfsr based random number generator, it didn't ) since I am novice to this field. So I was looking for conventional methodologies available. I was also thinking if I could mutiply with (1/7FFFFFFFFF) to bring it in the range [0,1].

 

[ads-ee]

I did move the decimal point before. But i was skeptical doing it. (Because my design when tested with matlab 'rand' function as an input, gave me the required output but with the lfsr based random number generator, it didn't )

I see you reported this as solved. But you indicate here it's not working with the lfsr?

I was also thinking if I could mutiply with (1/7FFFFFFFFF) to bring it in the range [0,1].

That is pretty much the same as doing a right shift by 39 (arbitrarily moving the decimal point to the left end of the number). The problem with using an lfsr is you can never get a value of 0 as that is the stuck state of the lfsr also you can never have 1 as that would mean there would have to be values generated with a '1' to the left of the decimal point (i.e. a 40-bit value). Therefore an lfsr can only generate values between 0 < lfsr < 1.

 

[rakeshk.r]

oh! sorry for the discrepancy. The design which I mentioned here

Because my design when tested...

was another component which takes a random number as input. BTW I got the message from your replies. Thank you.

 

[mrflibble]

I see you reported this as solved. But you indicate here it's not working with the lfsr?


That is pretty much the same as doing a right shift by 39 (arbitrarily moving the decimal point to the left end of the number). The problem with using an lfsr is you can never get a value of 0 as that is the stuck state of the lfsr also you can never have 1 as that would mean there would have to be values generated with a '1' to the left of the decimal point (i.e. a 40-bit value). Therefore an lfsr can only generate values between 0 < lfsr < 1.

But the good news is: taking these 39-bits directly as output and expecting a sequence that is even remotely decently random is rather ... optimistic. So all the above does not even get a chance of becoming a problem. Because other problems get in the way first.

Because while the OP says it is a 39-bit random number, it's not. What you have there is a 39-bit LFSR, that is generating a sequence of 1-bit random numbers. There's a difference between the two.

If you don't believe me ... seed it with whatever seed you like (well apart from the stuck state ), and then lets say 10K simulation steps and take your 39-bit "random" number. Then compute the cross correlation between the sequence and delayed versions of itself. A proper random sequence has very low correlation. This 39-bit number sequence has correlation galore. Why? Two words: shift register.

That is why you can only use 1-bit output. If you want more, then addition steps are required.

Anyways, normal distribution is fairly easy. If you want an N-bit uniformly distributed number, you clock out N bits from that 39-bit LFSR. One bit at a time. So it will take you N clock cycles to get that number.

If you want multiple bits in one clock, either use multiple LFSR's in parallel, or use leap ahead.

 

[D.A.(Tony)Stewart]

Everytime in the past when I tested the spectral distribution of different LFSR's it was perfectly flat with more resolution with longer codes. The audio versions I used, although were obviously cyclic noise of running water.

The seed must have good entropy for many reasons and none for others such as BER testers for a Comm channel with expected data synced at the receiver from a known test start.

Many other pattern lengths can be chosen based on the XOR feedback tap positions and pattern length

For those who don't already know.
**broken link removed**

 

[mrflibble]

Everytime in the past when I tested the spectral distribution of different LFSR's it was perfectly flat with more resolution with longer codes.

Exactly the same here as what you just said.

Just to be clear, are you suggesting that the OP can take that 39-bit LFSR, and then for example take the top 32-bits EVERY clock cycle, and treat that as a 32-bit random number? I suspect (hope) you don't, but would be interesting if you did mean that. Because if you do mean that, how is that going to be random? Besides, AFAIK there is a difference between spectral density and correlation. You can have a perfectly flat distribution, while your correlation is total crap (i.e not really all that random).

Could be I'm totally missing something, in which case .. what? Always fun to learn new tricks.

For those who don't already know.
**broken link removed**

Another interesting read on the subject is this xilinx app note by Peter Alfke:
https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

 

[mrflibble]

It can be called whatever you want while you are typing the sentence. But yes, you are correct. And so am I. ;-) Auto-correlation is crosscorrelation with self. But I agree that "autocorrelation" would have been less ambiguous.

 

[D.A.(Tony)Stewart]

The bits and taps are for maximal length random sequences for that serial length. These are used or random noise or number generation for radios and modems.

Since a flat Spectral Density depends on even distribution of duty cycle and phases or binary random distribution of pattern codes , how can they not be evenly distributed for a given length and rate and thus bandwidth. The reverse is not necessarily true.

and not all Random number generators are maximal length sequence, as was the case for Apple ]['s in the 80's, when we vector mapped and toggled every pixel for each number like cards in a deck for a random HDD seek test. We had to add more entropy to the function call.

 

[rakeshk.r]

If you want multiple bits in one clock, either use multiple LFSR's in parallel, or use leap ahead.

I was going through the leap ahead architecture for galios type lfsr in the document attached here. I have some questions from this article.
1. In equation (7) , they need all tap values to be zero in order to find the tranform matrix. Which I don't get. How could one have all taps to be zero?
2. In their implementation and results, for m=18, they get n=22, which i don't know how did they obtain.

could some one nurture me on this, preferably with an example will be of great help. Thank you.

 

[std_match]

1. No, not all tap values are zero. Only (m-1) of them.

2. I can not follow their calculations for this. They want the period of the 18-bit random generator to be exactly 2^18. For this, I think they have to leap ahead more than 18 steps in each clock cycle, but I am not sure.