[sdiy] Non maximal-length LFSR
ASSI
Stromeko at nexgo.de
Thu Mar 3 20:38:02 CET 2016
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
More information about the Synth-diy
mailing list