PRNG

[Thomas Heller]

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?

Thanks,
Thomas

 

[Tim Wescott]

On Fri, 01 Jun 2012 09:15:19 -0700, rickman wrote:

On Jun 1, 11:04 am, Thomas Heller <thel...@ctypes.org> wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

Thanks,
Thomas

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.

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

 

[Tim Wescott]

On Fri, 01 Jun 2012 17:02:10 +0100, Thomas Womack wrote:

In article <a2s3v7Fv1fU1@mid.individual.net>, Thomas Heller
theller@ctypes.org> wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

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.

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

 

[Jan Decaluwe]

On 06/01/2012 06:56 PM, Tim Wescott wrote:

On Fri, 01 Jun 2012 09:15:19 -0700, rickman wrote:

On Jun 1, 11:04 am, Thomas Heller<thel...@ctypes.org> wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

Thanks,
Thomas

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.

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.

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:

http://www.easics.com/webtools/crctool

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

 

[Thomas Womack]

In article <a2s3v7Fv1fU1@mid.individual.net>,
Thomas Heller <theller@ctypes.org> wrote:

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?

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

 

[rickman]

On Jun 1, 11:04 am, Thomas Heller <thel...@ctypes.org> wrote:

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?

Thanks,
Thomas

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

 

[rickman]

On Jun 1, 12:02 pm, Thomas Womack <twom...@chiark.greenend.org.uk>
wrote:

In article <a2s3v7Fv1...@mid.individual.net>,
Thomas Heller  <thel...@ctypes.org> wrote:

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?

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

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

 

[Thomas Heller]

Am 01.06.2012 18:57, schrieb Tim Wescott:

On Fri, 01 Jun 2012 17:02:10 +0100, Thomas Womack wrote:

In article<a2s3v7Fv1fU1@mid.individual.net>, Thomas Heller
theller@ctypes.org> wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

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.

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

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

http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf

http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm03.pdf

Thomas

 

[Thomas Womack]

In article <c6ec76d4-f2fc-4ebd-96b8-ae8e5aca3ee5@3g2000vbx.googlegroups.com>,
rickman <gnuarm@gmail.com> wrote:

How would you know which length-n to use?

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)

I believe that every
maximal-length sequence must include all sequences of lesser length.

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

 

[Thomas Heller]

Am 01.06.2012 18:02, schrieb Thomas Womack:

In article<a2s3v7Fv1fU1@mid.individual.net>,
Thomas Heller<theller@ctypes.org> wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?

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.

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

 

[Jon Elson]

Thomas Heller wrote:

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length, one
for each bit?
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

 

[Thomas Womack]

In article <gISdner7drm2aVXSnZ2dnUVZ_oSdnZ2d@web-ster.com>,
Tim Wescott <tim@seemywebsite.com> wrote:

On Fri, 01 Jun 2012 09:15:19 -0700, rickman wrote:

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.

It's probably more challenging than you make it sound, because there's a
lot of XORing going on

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

 

[pfraser]

Thomas Heller wrote:

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.

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

http://www.ht-lab.com/freecores/mt32/mersenne.html

Pete

 

[glen herrmannsfeldt]

Thomas Heller <theller@ctypes.org> wrote:

I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get
a new random number on each clock by using the 10 least significant
bits, or do I have to use 10 independent LFSR's of different length,
one for each bit?

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

 

[Thomas Womack]

In article <jqb17h$mj3$1@speranza.aioe.org>,
glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

The outputs of ten 32 bit LFSRs is more closely related
to ten bits of a 320 bit LFSR, though.

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.

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.

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

 

[glen herrmannsfeldt]

Thomas Womack <twomack@chiark.greenend.org.uk> wrote:

In article <jqb17h$mj3$1@speranza.aioe.org>,

(snip, I wrote)

The outputs of ten 32 bit LFSRs is more closely related
to ten bits of a 320 bit LFSR, though.

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.

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.

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.

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.

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.

(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)

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

 

[rickman]

On Jun 1, 2:36 pm, Thomas Heller <thel...@ctypes.org> wrote:

Am 01.06.2012 18:57, schrieb Tim Wescott:









On Fri, 01 Jun 2012 17:02:10 +0100, Thomas Womack wrote:

In article<a2s3v7Fv1...@mid.individual.net>, Thomas Heller
thel...@ctypes.org>  wrote:
I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
random numbers.

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

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.

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

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

http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf

http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm...

Thomas

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

 

[glen herrmannsfeldt]

rickman <gnuarm@gmail.com> wrote:

(snip, someone wrote)

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?

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

http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf

http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm...

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.

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 have read about other attempts based on diode noise
which resulted in easily measurable biases.

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

 

[rickman]

On Jun 5, 4:17 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:

rickman <gnu...@gmail.com> wrote:

(snip, someone wrote)

Can I use a LFSR of sufficient length (31 bit, for example), and get a
new random number on each clock by using the 10 least significant bits,
or do I have to use 10 independent LFSR's of different length, one for
each bit?
FYI: I found interesting papers about true (and pseudo) random number
generation in FPGAs. They are using ff metastability or PLL jitter
for this:
http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf
http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm....
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.

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 have read about other attempts based on diode noise
which resulted in easily measurable biases.

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

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