[sdiy] Non maximal-length LFSR
Tom Wiltshire
tom at electricdruid.net
Thu Mar 3 11:54:25 CET 2016
I've done some experiments with simulations of non-maximal length sequences for the same reasons you're considering it. "Not worth it" was my conclusion.
The trouble is that for non-maximal length sequences, you break the output up into several cycles instead of one. So yes, starting value is key, because that decides which one of the non-maxmal series you'll get. Also you no longer get *all* the values output, so you can't guarantee that you'll get a unbiased result, although in practice for long LFSRs, it seems like you get something near enough for audio. If you do the experiments with short LFSRs (like 5 or 6 bits) you can find combinations which do give a serious bias, but it gets harder as the numbers go up.
I agree with Ove. Use the 47-bit register and ignore the top bit. It'll give you a better result than a degenerate 48-bit register would anyway.
HTH,
Tom
On 3 Mar 2016, at 08:16, Richie Burnett <rburnett at richieburnett.co.uk> 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
More information about the Synth-diy
mailing list