[sdiy] Non maximal-length LFSR

mskala at ansuz.sooke.bc.ca mskala at ansuz.sooke.bc.ca
Thu Mar 3 10:10:14 CET 2016

On Thu, 3 Mar 2016, Richie Burnett wrote:
> For example there are maximum-length polynomials shown for shift-register
> length 47 and length 49 that contain just two taps.  That's great because
> they're cheap to implement, but the maximum-length polynomial for
> shift-register length 48 contains four taps and is more expensive to
> implement.  In-short I want to use a shift-register of length 48 bits, but
> with just 2 taps, and accept the fact that I won't get a maximum-length
> sequence of (2^48)-1 bits out of it, but it will hopefully still be quite long
> and adequate for white noise synthesis purposes.

A few thoughts:

First, unless something forces you to have one of the taps be right on the
highest bit, you could just use your favourite 47-bit polynomial with a
48-bit register and ignore the highest bit of the register.

Not all maximal-length sequences are created equal.  Using a polynomial
with very few taps may mean compromising the quality of the sequence in a
way other than shortening its length.  It'll create a simple correlation
structure between the sequence and shifted versions of itself.  When
people apply LFSRs to semiconductor testing and error detection, they seem
more pleased with the sequences that come from LFSRs with more taps, and
I've read some interesting research suggsting cellular automata may
produce nicer sequences for semiconductor testing than LFSRs even though
they are in some sense mathematically equivalent (same sequence length,
same polynomials under the covers).  Whether this will make a difference
for audio I don't know, but it wouldn't surprise me if you built a two-tap
register and a four-tap register, listened to them both, and found that
the four-tap register sounded better.

You and that application note both refer to "the" polynomial for each
register length, but there are actually many polynomials that generate
maximal-length sequences of each length - probably billions of them when
we're talking about registers of length 47 or 48.  There might exist a
maximal-length polynomial with only two or three taps for register size 48
even if the table only lists a four-tap polynomial.

I'm sure there is some algebra someone can do to compute the exact length
of the sequence generated by a polynomial (perhaps by first factoring the
polynomial) but I don't know it off the top of my head and am not sure it
would be worth it to research if this problem only has to be solved once.
What I'd be inclined to do instead would be write a program in any
convenient language (I'd probably choose Perl, others might prefer Python)
to simulate the shift register with the polynomial I was considering and
find out how long a sequence it generates.  That shouldn't be very hard.

> answer in a reasonable time using simulation or autocorrelation because
> even though the polynomial doesn't result in a sequence that's
> maximum-length, it's probably still very long?

How long do you *need* it to be?  If it's at least the length of a 40-bit
maximal sequence, then it'll give you 1000 bits per second for a few days.
That should be easily achievable with two taps on a 48-bit register, and a
decently-written simulation program should be able to verify the sequence
length at a rate of a million steps per second or more, which should cover
2^40 in less time than it would take a person to learn the algebra to do
it really right.

Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.

More information about the Synth-diy mailing list