[sdiy] Non maximal-length LFSR

[Tom Wiltshire]

On 3 Mar 2016, at 11:55, mskala at ansuz.sooke.bc.ca wrote:

> On Thu, 3 Mar 2016, Tom Wiltshire wrote:
>> Since all maximal length sequences produce the same values, and are
>> similarly distributed, I don't see how one could sound significantly
>> different to another. The distribution is key, since a rising binary
>> count also produces all the output values, but it doesn't sound remotely
>> random.
> 
> Two different maximal-length sequences will contain the same subsequences
> up to the length of the register.  They'll contain very different sets
> of subsequences of any greater length.  For instance, here are two
> different maximal-length sequences for registers of length 5 (Perl code
> below my signature):
> 
> taps at 5 and 2:
> 1010111011000111110011010010000
> 
> taps at 5, 4, 3, and 2:
> 1011010100011101111100100110000
> 
> One of these contains a string of 8 ones and 1 zero; the other does not
> contain any nine-bit sequence with that much bias in either direction.
> This will make a difference in what comes out if they go through an
> integrator or low pass filter.  *I haven't tried it*, but it's reasonable
> to guess that they might also sound different if changed into audio
> waveforms.  The fact that people working on semiconductor testing do find
> reasons to prefer some polynomials over others even though the preferred
> ones are more expensive to build - and those people care a lot about
> saving implementation complexity and wouldn't use the more expensive
> polynomials without good reason - suggests that there are at least some
> real ways in which different maximal-length sequences differ from each
> other.

Hi Matthew,

Yes, I found I was able to find short LFSRs with markedly different results much like yours. However, this is a bit like coin-tosses being distributed 50/50. For a small number of tosses, it's fairly easy to get a result that's "all heads" or "all tails". As the number of coin tosses goes up, it gets harder and harder. I found something similar with the length of LFSRs. They get closer to a smooth white distribution as they get longer. The number of sub-sequences of a particular length also starts to approach what you'd expect if it were genuinely statistically random.

However, your point still stands - this *isn't* random, and some LFSRs might be better for some uses than others. It's just that for something as long as 47/48-bit and in an application as undemanding as audio, I don't think it matters.

Regards,
Tom