[sdiy] Non maximal-length LFSR

[rsdio at audiobanshee.com]

> On Mar 3, 2016, at 7:59 AM, Richie Burnett <rburnett at richieburnett.co.uk> wrote:
>> Also you can always mix two not-so-good random streams together to get a
>> longer and often better random data stream. Say you have a stream with a
>> sequence length N and another one with a sequence length M the xor of
>> the two streams yields a random stream of length GCD(m,n).
> 
> I can try this, although it is not really "quality" in a mathematical purist or Cryptographic sense that I am aiming for as much as "super efficient noise source".  The ability to produce 16-bit noise samples with poor correlation between the bits in just two instructions per sample is what is appealing to me about this technique.
> 
> I didn't invent this idea, BTW.  I came across the R250 Random Number Generator that uses an array of 250 words in a circular buffer and takes its feedback from taps 147 and 250 to produce a sequence of 16-bit random numbers that is (2^250)-1 in length!!!!  Obviously this is far longer than necessary for audio, but the efficiency of the algorithm is very tempting when run on DSP hardware.  Hence me trying to modify it to fit a buffer length of 48 words.  (You might say that 48 words is a lot of RAM resources to use up generating some random numbers, but I would use this space for the 1ms output buffer of the noise source anyway.)

As I've mentioned, the length is deceiving.

Thinking in terms of 1-bit LFSR implementations for now - not your improved 16-bit LFSR - each iteration only produces 1 bit. It doesn't matter how long the sequence is: an iteration only produces 1 bit. The length is merely used to increase the length before the 1-bit pattern starts repeating. If you try to use more than 1 bit for a single iteration, then those bits will be correlated by definition, because they're merely (phase) shifted.

In your implementation, the LFSR produces 16 bits per iteration. You can use only 1 word per iteration. Attempting to make the register 48 words long so that you can produce 48 samples means that your samples will be phase-shifted copies of each other. Much less random than if you executed 1 iteration per sample.

The interesting thing is that if you perform an iteration per sample then it doesn't matter how many sample you need per millisecond. Your register length merely determines the time period of the maximum sequence.

Brian