[sdiy] Long LFSRs (Was Psych Tone)

[ASSI]

On Sunday, January 6, 2019 7:02:23 PM CET Donald Tillman wrote:
> On Jan 6, 2019, at 9:16 AM, Donald Tillman <don at till.com> wrote:
> > For any given LFSR length, there are one, or more, or a lot more, choices
> > for feedback taps for a maximum length sequence.
> I've long forgotten the math behind this, and apparently there is no easy
> algorithm, so finding the taps for a maximum length sequence might be a
> brute force operation.

Getting a maximum-length LFSR involves finding primitive polynomials defined 
over a Galois extension field.

https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory)

That polynomial is called the generator or characteristic polynomial depending 
on which way the theory gets derived.  There's also a way to write out the 
state equations as a so-called companion matrix that clearly shows where the 
"linear" comes from in LFSR.  The terms with non-zero weight are related to 
the tap sequence (again, can be left-to-right or the other way around, 
depending on what canonical form gets used).  There are only a few software 
packages that let you do this without writing your own programs, the only one 
easily accessible (I know of) is the demo server for a software called Magma 
(maybe Wolfram Alpha does it also by now).  The demo truncates the output, so 
for larger state space you don't get the full set of possible polynomials.

http://magma.maths.usyd.edu.au/calc/

> Being practical, if you've got a 127 bit shift register, I think you'd do
> pretty well with just an arbitrary bunch of taps along the length.

It's just as easy to end up with a non-primitive polynomial and multiple runts 
and cycles, some of them possibly very short.  For instance, any state length 
divisible by three and five can't be generated from a primitive trinomial.  At 
least for trinomials and pentanomials (i.e. LFSR with two and four feedback 
taps) some interesting theory exists on how to more efficiently (than brute 
force enumeration) find them.


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

Factory and User Sound Singles for Waldorf Blofeld:
http://Synth.Stromeko.net/Downloads.html#WaldorfSounds