8
\$\begingroup\$

I am programming a LFSR (Linear Feedback Shift Register) in software for learning purposes, and have encountered some limitations in its use as a pseudo-random number generator (PRNG).

  • If the seed have few '1' bits and few taps are used, it requires a large "startup time" to produce apparently random output, with almost equal distribution between '1's and '0's or short '0's runs. I guess with more taps such startup would be far quicker, but all precalculated tables I find give two or four taps.
  • Sequential numbers are highly correlated, which is to be expected, given that if the output bit is 0 the next number will be half of the previous one. For a 15-bit LFSR with taps [15, 14], plotting a pair of sequential numbers as points in a plane gives the following. An ideal PRNG should spread these points all over the place.

image

I know that LFSRs are used as fast hardware counter, but I've also seen it is used as a PRNG to create white noise. How is it used in such real world applications with such poor quality?

\$\endgroup\$
  • \$\begingroup\$ As @rawbrawb points out, LFSRs are not very good for generating pseudorandom numbers. If you use only a portion of the contents of the shift register (e.g. 16 least significant bits in a LFSR of length 32 bits) as a random number, matters are much worse. See this recent Q&A on crypto.SE for some more information about this. \$\endgroup\$ – Dilip Sarwate Jan 22 '13 at 3:25
4
\$\begingroup\$

An excellent source for all things PRNG is "Shift register sequences" by Solomon Golomb. It discusses the various classes, and techniques.

To start up by resetting all the registers is one way. Or a parallel load of a seed is another. But do remember that a sting of all zeros' is a valid state.

Choosing the right codes are important as not every feedback setting on a shift register ensures that you get a maximal PRNG sequence.

How you operate a PRNG affects it's performance.

For a 15 bit register and looking up the codes, [15,4] is maximal as is [15,1] but [15,14] is not listed. -> Source- "Spread spectrum systems and applications" - Robert Dixon 3rd Ed. Pg 94. This book is a very good reference on implementation.

In general LFSR's make poor PRNG's and the general practise is to only use the lower bits. Alternatively you can generate two PRNG's of different lengths and codes and xor the lower bits to generate the new code. Probably less than 1/2 of bit length should be used. So a 30 and 31 bit length register and XOR the 15 LSB's.

NIST has excellent testing code here. So yes, it sucks, for PRNG's.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If you have the set of taps [nbits, a, b, c], another set that is maximal is [nbits, nbits-a, nbits-b, nbits-c]. This way, both [15,14] and [15,1] are maximal. \$\endgroup\$ – Bruno Kim Jan 22 '13 at 1:52
  • \$\begingroup\$ Depending on your register setup, either all-zero or all-one is invalid. In most stuff I do, all-zero is invalid, but you noted it as valid above so wanted to make sure this was thrown out there. ;) \$\endgroup\$ – Aaron D. Marasco Jan 22 '13 at 2:12
  • \$\begingroup\$ Added the details on how to get better performance. But it doesn't do that well. I've used these in SSDS - the self-correlating nature. I'd forgotten about duals. \$\endgroup\$ – placeholder Jan 22 '13 at 3:17
  • \$\begingroup\$ Interesting idea, to XOR different LFSRs, but I guess the numbers would still be correlated. Probably its better to use Tim's answer and perform a full cycle before picking another number. \$\endgroup\$ – Bruno Kim Jan 22 '13 at 12:26
  • \$\begingroup\$ @BrunoKim it's not original, it's more computation or area efficient. It's repeat length would be 2^30th as well. \$\endgroup\$ – placeholder Jan 22 '13 at 14:48
7
\$\begingroup\$

Sequential numbers are highly correlated, which is to be expected, given that if the output bit is 0 the next number will be half of the previous one. For a 15-bit LFSR with taps [15, 14], plotting a pair of sequential numbers as points in a plane gives the following. An ideal PRNG should spread these points all over the place.

If you want to generate random numbers with a 15-bit LFSR, you don't pull a new random number each clock cycle. As you said since you're only adding one new bit to the register each clock cycle, the value in cycle N and N+1 will be very strongly correlated. If you want to generate random values (assuming you have proper taps), then you need to only pull a new value every 15 clocks.

A LFSR only guarantees you one random bit each cycle, not 15 random bits.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm coding for arbitrary bit numbers. In general, if I want a random integer (64 bits), I should use a 128-bit LFSR (following rawbrawb suggestion) and do 64 iterations before picking a number? Wouldn't some number be missed, and others picked more times than expected for a "uniform" distribution? \$\endgroup\$ – Bruno Kim Jan 22 '13 at 12:28
2
\$\begingroup\$

A real world example can be found in the MPC7450 RISC Microprocessor Family Reference Manual. The 7450 used a pRNG for L2 and L3 replacement that is composed of 16 latches having three simple shift registers with bits 0 through 4, bits 5 through 9, and bits 10 through 15. Bit 0 comes from an XOR of bits 4 and 15, bit 5 comes from an XOR of bits 4 and 9, and bit 10 comes from an XOR of bits 6 and 15. The replacement way in the 8-way caches is indicated by bits 4, 9, and 15 for L2 and by bits 0, 5, and 10 for L3. The bits were shifted every cycle, but obviously cache replacements did not occur that frequently. (An alternate counter-based replacement mechanism was also provided.)

This was recognized as potentially problematic:

Due to the latency of the L2 cache look-up, there are 3 clock cycles between a read miss and the allocation of the replacement line. Thus, it would be possible that the same way can be chosen for replacement for two, or even three consecutive read misses with the algorithm as described above. In order to avoid this, the actual algorithm compares a selected replacement line with the three previous replacement lines. If the selected line matches with one of the three previous ones, a value of one, two, or three is automatically added to the value that selects the way for replacement.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.