[sdiy] Non maximal-length LFSR

nvawter nvawter at media.mit.edu
Thu Mar 3 15:53:14 CET 2016

```Hi Richie!

I've played a lot with LFSRs and non-maximal ones.  I figured out lots
of things with short, tonal ones!  Great timbre space, there.  I did
that all with perl, like someone else on this thread and analyzing to
find redundant waveforms....  Remind me to publish that at some point...

Anyway, w/r/t to compromising length for maximizing efficiency:
You can make the longest LFSRs with a very simple computation.
The computation is merely a shift and 3 XOR operations.  You're probably
already familiar with it.
Take a look at:
http://www.eetimes.com/document.asp?doc_id=1274550&page_number=2
http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf

You'll see to make extremely long sequence, you only need to XOR the two
proper bits, XOR that operation and feed it
to the input of the shift register.   If you hunt, you'll find the tap
locations for even longer sequences, but the
principle is the same, you only need to combine two bits with three XORs
to produce the new bit.

I don't think you'll get any simpler computation that that!  The latency
is two clock cycles and the resources are absolutely minimal.

Let us know if this isn't what you were thinking :)

BTW when I first did my search, many sources weren't that hot and showed
much more complex polynomials to get LFSRs that appeared to grow in
complexity with the sequence length.  They are deceiving.  You only need
two taps, even for trillions of bits :)

On 2016-03-03 03:16, Richie Burnett wrote:
> Hi guys,
>
> I'm wondering if one of the maths gurus here can help me out with
> something...
>
> 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?
>
> 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.  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.
>
> In response to "why don't you just try it and find out"  I've coded up
> my noise generator, and I can't hear any repetition, but obviously my
> ear probably isn't going to detect the repeats if they're more than a
> few seconds apart.  I've also looked at the average power spectrum of
> 3 mins of noise, versus the average power spectrum of 6 mins, and the
> second spectrum is much flatter suggesting to me that the sequence
> isn't simply repeating over in the additional 3 mins.  My problem is
> getting some handle on the sequence length but I suspect it is going
> to get complicated, and possibly even depend on the initial conditions
> of the shift-register!?  I can't even get an answer in a reasonable
> time using simulation or autocorrelation because even though the
> polynomial doesn't result in a sequence that's maximum-length, it's
> probably still very long?
>
> Any help or pointers would be much appreciated.
>
> Many thanks,
>
> -Richie,
>
> *
> http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
>
> _______________________________________________
> Synth-diy mailing list
> Synth-diy at dropmix.xs4all.nl
> http://dropmix.xs4all.nl/mailman/listinfo/synth-diy

```