[sdiy] Long LFSRs (Was Psych Tone)

[rsdio at audiobanshee.com]

On Jan 6, 2019, at 10:02 AM, Donald Tillman <don at till.com> 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.
> 
> Here's a table of taps:
> 
>    Philip Koopman: Maximal Length LFSR Feedback Terms
>    http://users.ece.cmu.edu/~koopman/lfsr/
> 
> His computations only go to 32 bits long, and he found 67,108,864 combinations of taps for that (the text file lists only the first 100).
> 
> 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.

Well, not completely arbitrary. If at least one of the taps is not at position 127, then you’ll necessarily end up with a shorter sequence. The extra bits in the shift register wouldn’t really serve much of a purpose, certainly not to extend the sequence.

… but someone has already cited the heavy math - mostly affected by selecting prime-numbered taps - that is involved in picking taps without giving in to brute force.

Brian