# [sdiy] Long LFSRs (Was Psych Tone)

ASSI Stromeko at nexgo.de
Sun Jan 6 20:21:36 CET 2019

```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: