[sdiy] Non maximal-length LFSR

[ASSI]

Hi Richie,

On Thursday 03 March 2016, 08:16:59, Richie Burnett wrote:
> I'm wondering if one of the maths gurus here can help me out with
> something...

I am most certainly not a guru, but I have wondered about these things 
before… it's been a while, however, so I can just give a few pointers.

If you really want to do it with math, then you need a bit of Galois field 
theory.  Write out the connections on the LFSR in a certain way and you get 
something called the connection polynomial.  That can be developed into the 
recurrence equations and if you write them in matrix form you'll be able to 
determine the characteristic polynomial of that matrix (you don't really 
need the matrix form, but it is helpful for certain types of analysis).  The 
factors of that polynomial give you the sequence length of each possible 
sequence.  If the polynomial is primitive, then you get just 2^n-1 plus a 
degenerate cycle for a maximum length LFSR. 

> I want to make a white noise generator using a Linear Feedback Shift
> Register.  However, rather than using one of these (see link below)
> polynomials to choose the feedback tap locations to achieve the maximum
> possible length sequence, I would like to choose a sub-optimal polynomial
> for reasons of computational efficiency on the chosen implementation
> platform.  My question is then, how long will the resulting pseudo-random
> bit sequence be?

Working with non-maximum length sequences is a bit iffy since you can easily 
end up in short cycles or degenerate states.

> 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.

Yes, one of the arcane nuggets of that theory is that any length that can be 
divided by 3 or 5 (except 3 and 5 itself) can't have just two taps (the 
correspondence of which would be a three-term polynomial, called 
"trinomial").

> 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.

What you're looking for is called "almost primitive trinomials".  I'm not 
sure you want to go there, but here's a paper that covers your application 
(I think):

http://www.math.clemson.edu/~sgao/papers/BGL97.ps

But you have to make sure you start in the longest cycle, I don't think that 
paper talks about how to achieve that.


Regards,
Achim.
-- 
+<[Q+ Matrix-12 WAVE#46+305 Neuron microQkb Andromeda XTk Blofeld]>+

SD adaptations for KORG EX-800 and Poly-800MkII V0.9:
http://Synth.Stromeko.net/Downloads.html#KorgSDada