[sdiy] Non maximal-length LFSR

Tom Wiltshire tom at electricdruid.net
Thu Mar 3 22:30:10 CET 2016


On 3 Mar 2016, at 20:20, ASSI <Stromeko at nexgo.de> wrote:

> Hi Richie,
> 
> On Thursday 03 March 2016, 19:55:59, Richie Burnett wrote:
>> What my intended algorithm does instead, is implement sixteen identical
>> LFSRs in parallel at the same time using an XOR instruction acting on
>> 16-bit words in a circular buffer.  But these 16 bits aren't 16 bits of
>> one Linear Feedback Shift Register, they are all the same bit but across
>> sixteen different LFSR instances.  This is how I propose to generate the
>> 16-bit words ensuring de-correlation between the bits, by initialising
>> the 16 different shift registers to different initial states.  The taps
>> are currently one bit apart but I can move them anywhere I want.
> 
> You are still using bits from the same sequence (each LFSR, a bitslice of 
> your 48 registers, has the same structure), so you need to carefully 
> initialize the LFSR states to have a large enough distance.  You reduce the 
> correlation length by a factor of 16, which is inconsequential if you keep 
> the sequences the maximum of 2^44 cycles apart, but could have unintended 
> results if they are quite close together.  If you really want just 16 random 
> bits per cycle, one of the pseudo-random generators that are used elsewhere 
> might actually be much less of a headache.  You don't need one that's 
> cryptographically secure, so there are lots of existing examples around.

I've used a linear congruential noise generator that can produce a "random" (ish) word in 2 instructions, but I haven't found anything else that could come close. LFSRs produce a much better output than the LCG, so Richie's tricks for getting that down to two instructions is pushing the performance hard. After all, you can't shave much more off 2 instructions.

T.





More information about the Synth-diy mailing list