How are LFSRs used in real applications as PRNGs?

Question

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.

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.