PRNG

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

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

On Jun 1, 11:04=A0am, 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

On Jun 1, 12:02=A0pm, Thomas Womack <twom...@chiark.greenend.org.uk>
wrote:
> In article <a2s3v7Fv1...@mid.individual.net>,
> Thomas Heller =A0<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? =A0The 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. =A0If 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

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

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

> On Jun 1, 11:04&nbsp;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

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

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

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