PRNG

How important is it that the numbers are uncorrelated? The 10 LSBs of an LFSR at time t+1 will be nine of the bits from time t and one new one, so if you saw 100 at time t you know it's either 200 or 201 next go. If that's OK, use the end of one LFSR; if not, use several.

But if it's actually important that the random numbers are unpredictable, don't use LFSRs: given 3n bits from a length-n LFSR you can pretty much write down the rest of the sequence.

Tom

LFSRs are typically specified as one bit at a time arrangements. As to the LFSR to use, you don't need a 31 bit LFSR to get a 10 bit result. Even if you use a 31 bit LFSR you need to turn the crank 10 times to get 10 unique bits, otherwise adjacent numbers will have strong correlations.

There is no reason that an LFSR has to generate one bit at a time. If you do the math you can produce the next 10 bits in one clock cycle which is what I believe you are thinking of doing.

Doing the math is just a matter of iterating on the calculations 10 times. Some of the bits get a bit long winded, but it is nothing you can't do without too much trouble. The hard part is to not make an error, so I suggest that you verify the results between simulations of a single bit approach and a multiple bit approach.

Rick

How would you know which length-n to use? I believe that every maximal-length sequence must include all sequences of lesser length. So how exactly do you determine that you have seen enough data that can identify which length-n you are working with? Don't you have to continue monitoring until the sequence repeats?

Rick

Pick a large K and a smaller L, write out the KxL matrix with row N being bits N through N+K, and ask your favourite linear-algebra-over-GF(2) package whether it has a non-trivial kernel; if it doesn't, increase L or K and try again. If it does, check whether the relation implied by the kernel works for all the rest of the bits.

This will work whenever L is greater than n and K greater than 2n (I think)

No; consider the sequence x_3 = x_0 + x_2 (which goes 0011101 repeating) and the sequence x_4 = x+0 + x_3 (which goes

000111101011001 repeating) ; the former sequence isn't a subsequence of the latter.

Any maximal-length sequence (that is, of length 2^n - 1) will contain all 2^n - 1 sets of n bits not all zero as subsequences, but that's not the statement you were making.

Tom

It's probably more challenging than you make it sound, because there's a lot of XORing going on -- but it can probably be done, and it may even be amenable to pipelining.

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

I've only scratched the surface of cryptographicaly secure random number generation -- are there any schemes that are amenable to working on an FPGA?

Most of the ones that I've seen have a divide in there someplace, and divides are expensive...

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

But the lovely thing about XORing is that it's linear; I would hope that any optimiser worth the name could take the for-loop version and convert it to the correct pile of XOR gates. Certainly you shouldn't be doing that sort of Boolean algebra by hand in order to feed it to an optimising Boolean algebra tool!

I'd be surprised if you needed to pipeline very much, though I guess a full 32-input XOR is three layers of 4-LUT (eleven LUTs) or two of

6-LUT (seven LUTs) deep. Bit of a routing nightmare but it feels like the sort of thing that P&R software designers use as a test-case.

Tom

Come on guys, this problem has been solved a long time ago. Either put a for-loop around the bit-serial implementation and use synthesis, or use the Easics tool for a pre-digested version:

--
Jan Decaluwe - Resources bvba - http://www.jandecaluwe.com
     Python as a HDL: http://www.myhdl.org
     VHDL development, the modern way: http://www.sigasi.com
     World-class digital design: http://www.easics.com

First, there are two different ways to implement LFSRs.

The way commonly implemented in sofware is to take the shifted output and XOR it with some of the bits of the register.

That can conveniently be done N bits at a time with a 2**N entry lookup table. That can also be done in hardware.

A more common hardware implementation is to feed a shift register input with the XOR of some of the register bits.

The two can be shown to be equivalent, though the actual register contents at any point are not the same.

As to the OP, in the latter implementation the low bits at each clock are just a shifted version of those from the previous clock cycle, so not so random. In the former one, though, depending on where the taps are, the bits won't be exactly shifted, but will still have some correlations.

Note, though, that you don't need to take the low 10 bits, but other combinations of 10 bits (such as every 3rd bit) could also be used. Or even the XOR of some combinations of bits.

The outputs of ten 32 bit LFSRs is more closely related to ten bits of a 320 bit LFSR, though. Taking the appropriate combination of bits from a sufficiently long generator should be random enough. You need to figure out how many bits long, and which bits to take. (That is, it will be the result of a slightly less than maximal 320 bit LFSR.)

As you note, for the most randomness use ten LFSRs of ten different lengths. Again, equivalent to an appropriate LFSR of the total number of bits.

-- glen

FYI: I found interesting papers about true (and pseudo) random number generation in FPGAs. They are using ff metastability or PLL jitter for this:

Thomas

Am 01.06.2012 18:02, schrieb Thomas Womack:

My requirements are (I guess) pretty weak. The use case is difficult to explain; I'll try with this model:

I will collect the numbers into a histogram; the counts in the histogram bins should increase 'statistically', without any visible pattern.

Thanks for all the suggestions; will give me some interesting thoughts over the weekend.

Thomas

Well, obviously, if your use one LFSR, at each clock, you only get ONE new bit, all the others are old, just moved to another position. That's not too random.

Jon

Not really; in particular the period is 2^32 rather than 2^320. Of course period 2^32 is good enough for many applications, and the original poster's task doesn't require cryptographic quality.

Not quite if the lengths aren't coprime (a 4-bit period-15 and 6-bit period-63 LFSR produce a cycle length of 315, which you can't do with an LFSR of ten bits no matter what polynomial you choose.

(or is the EE definition of LFSR different from the mathematical one? I reckon that an LFSR is anything defined by f(t) as a XOR together of the values of f(t-a_i) for some fixed set of a_i)

Tom

Are you familiar with the Mersenne Twister? I used some GPL VHDL code in a project a long time ago.

Pete

(snip, I wrote)

Yes. If you need enough random numbers, or even just enough randomness, to notice the period of 2**32. Using the low bits off a 32 bit LFSR gives short term correlations, where ten 32 bit LFSR's, started appropriately, doesn't.

Yes, I should have put more "sort of" in there. Actually, I am not so sure I know how it works if you choose a non-primitive polynomial. It is usual to discuss only the maximal length cycle, but the hardware doesn't require that.

Well, LFSR pretty much describes a physical system, not a logical (mathematical) one. It might be that the EE definition includes any combination of XOR gates and shift registers. The math is usually done in terms of factoring polynomials modulo 2, which is more restrictive.

-- glen

a

s,

r

of

r

I haven't read the papers, but typically any digital "true" random number generator is not "truly" random. When it is measured and analyzed critically it has biases which allow a degree of predictability. I have read about other attempts based on diode noise which resulted in easily measurable biases.

Rick

(snip, someone wrote)

If you put enough state bits into the calculation, you should be able to keep the predictability long enough that, in a practical time frame, it isn't noticed.

I used to have the paper about an Intel chip with a built-in noise source based generator. There is logic to remove at least the first order bias. (Equal ones and zeros.) It should be possible to remove any specific bias if you know about it and try to remove it. You need to know which biases the specific problem is sensitive to.

I do remember stories about many of the early generators that weren't so bad except when taken in triplets there was some correlation between triplets. That turned out bad when used to generate points in 3D space. Once known, it can be fixed.

There is always a tradeoff between randomness and time needed by the generator.

-- glen

et a

bits,

for

.

Yes, it all depends on what you need.

I was watching a local government cable channel once about a state hearing where a representative of a gambling machine company was trying to explain to the regulating board how this machine was different from the machines prohibited in this state. It seems that there were machines that for some amount of coin would give you a pre- printed ticket that told you your winnings, if any. Because the sequence was pre-arranged and once the prizes have all sold out (the barkeeper would know when that happens) the remaining tickets were all losers and further play was no longer "gambling". So the gaming board banned these machines.

This spokesperson claimed that the microprocessors in the machine always produced random results and so was not like the illegal pre- printed ticket machines. We all know that this is nonsense and that they actually were using something like an LFSR, possibly with a time based modification that would not produce truly random results. For example, I expect their machines would never produce a sequence of 100 big winners no matter how long you played. A real random machine would produce this sequence eventually if played long enough.

I don't know what the outcome of the hearing was. I suspect the gaming commission got more info from other sources and learned that a microprocessor does not produce random results.

Rick