# Can Linear Feedback Shift Register be used to generate pseudo radnom numbers with uniform distribution and zero correlation?

I need to implement a circuit inside the FPGA that generates pseudo random numbers with uniform distribution and zero correlation. To make the repeat period of the sequence long, it would require a moderately big shift register. I think 64 bits is sufficient.

As far as I am aware, it is important to wait N clock cycles before reading the state of the LFSR to get Pseudo-Random Numbers. In this case N would be 64. However, I am not sure what is the simplest way to create a uniform distribution zero cross correlation pseudo-random number generator using linear feedback shift registers inside an FPGA, or even if it is at all possible. What can be done to reduce the cross correlation drawback of LFSR?

• Random or pseudo-random?
– user16324
Commented Mar 30, 2020 at 12:37
• pseudo random will do Commented Mar 30, 2020 at 12:41
• Look here for example code and comments and pitfalls with LFSR on pseudo random generator. Commented Mar 30, 2020 at 13:00
• Depends what you want to use the numbers for. I built an audio noise source some time ago, starting with a single very long m-sequence. The resulting hiss was quite uneven, described by several listeners as 'having an occasional lump of concrete in it!' Splitting the registers into 3 shorter different length m-sequences and XORing their outputs produced a 'smooth' sound, even though both generators had essentially the same repeat length and correlation statistics. Always test your PR-numbers against the precise purpose they will be used for. Commented Mar 30, 2020 at 15:02
• What do you consider a "long" repeat period? What is the size of the numbers you want to generate? With a 64-bit shift register, you get a repeat period long enough that you could generate 464 bits per second and the repeat period would be longer than the age of the universe. Commented Mar 30, 2020 at 15:09

Can Linear Feedback Shift Register be used to generate

• pseudo random numbers

Yes,

• with uniform distribution

yes,

• and zero correlation?

impossible!

The structure of an LFSR says that the next state is just a result of the current state, with a deterministic (even linear) function applied to that.

The state of the LFSR is fully defined by the values in the shift register.

There's a finite number of possible states.

Hence, the LFSR must repeat itself, latest after $$\p^N-1\$$ numbers generated, where $$\N\$$ is the length of your shift register, and $$\p\$$ is the cardinality of the possible values in each shift register (typically, your LFSR is binary, $$\p=2\$$).

The case where an $$\N\$$-deep LFSR really only repeats after $$\p^N-1\$$ values, and not earlier (i.e. isn't caught circling in some sub-field) is a special one, we call the resulting sequence the maximum length sequence.

So, you most definitely have a correlation!

If you want to use LFSRs to generate longer sequences, you can combine two or more; that's not really part of your question, so let me just refer you to Gold Sequences. They have real-world applications as white sequences, used e.g. in spreading systems / CDMA.

Also, if you worry about correlation, you probably also worry about linear dependencies of your values, and then the LFSR simply isn't the right tool; it's, as the name says, an inherently linear thing.

• The usual substitute for "zero correlation" in this context is "zero expectation value for the correlation for randomly chosen shifts less than the pattern period" or something like that. Commented Mar 30, 2020 at 15:11
• @ThePhoton that makes sense, especially when we think of LFSR as an algebraic structure. Nevertheless, LFSRs in general don't even have any guarantees about correlation within their periods, so... not a great choice on their own, either way. Commented Mar 30, 2020 at 16:25