Electronic – How are LFSRs used in real applications as PRNGs

digital-logic

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?

Best Answer

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.

Related Topic