[sdiy] Non maximal-length LFSR

rsdio at audiobanshee.com rsdio at audiobanshee.com
Thu Mar 3 20:17:56 CET 2016

Hi Richie,

It's been decades since I worked on LFSR code (on a 1 MHz Apple ][ 6502 with 8-bit DAC for sound), but I think I recall a few important concepts.

A) One iteration of LFSR produces only 1 new bit, no matter how large the accumulator. Whether the XOR function takes in 2 bits or 4 bits, the operation only produces 1 new bit in the LSBit. This means that all of the rest of the bits in the accumulator are related from one iteration to the next due to the bit shift operation.

B) Most software implementations suffer in terms of randomness because the iterations only occur when the processor executes them. In contrast, a hardware LFSR can be clocked separately, such that reading its value twice in a row could have no related bits, depending upon how many clock cycles have passed and therefore how many iterations were calculated.

C) If you want random numbers that are not correlated (at least that don't have matching bits anywhere), then you can run multiple iterations.

In your case, you need a new 16-bit sample from a 48-bit (or other size) LFSR. If you can run the LFSR calculation 16 times before taking the 16 LSBs as a noise sample, then you should have completely uncorrelated noise samples for as many channels as you want from a single LFSR. This means that you'll run through the maximum-length bit sequence 16 times faster, but I'm fairly certain it means that you don't need separate LFSR buffers to produce unrelated noise sample sequences.

I'm not quite sure that I understand your implementation. Are your 2 LFSR taps separated by exactly 16 bits? or 1 bit? Typical LFSR taps that I remember have taps that are usually separated by exactly 2 or 3 bits for optimizing the reduction of correlated bits in each iteration. i.e. When the new bit is produced in the LSBit, it's best that the XOR input bits come from as close to the MSBit as possible without getting too far down towards the LSB. It's also best if the taps are not part of the word being used for data, but that the taps are part of the excess accumulator bits representing the history of previously used data bits.

I think your implementation is effectively shifting by 16 bits on each operation. That would certainly be efficient for what I describe. I just don't see how you have selected the taps. If I understand your implementation correctly, I'd think that you'd want to grab two 16-bit words from non-adjacent MSW addresses (i.e. not pointer+1, but pointer+3) for the XOR operation and store the result in the LSW.

Does this make any sense?


On Mar 3, 2016, at 6:51 AM, Richie Burnett <rburnett at richieburnett.co.uk> wrote:
> Thanks for all your suggestions.  I think I need to explain what I'm trying to do, and why!...
> I'm implementing 16 simultaneous 48-bit LFSR algorithms on a DSPIC by making use of a 48-word circular buffer in RAM, and doing the XOR function on words of 16-bits at a time.  Why 48-bit, because my end application buffers everything in 1ms frames at 48kHz sample-rate.
> Each LFSR is just like a convention LFSR working with however many bits, it's just that I am stringing out those bits across the LSBs of 48 consecutive words in RAM.  Another similar LFSR uses all of the next most significant bits of those 48 words, etc, etc. so we have a 48-bit LFSR using the n'th bit of each of the words in the circular buffer.
> The reason is this.  I can do the whole calculation in only two instructions for each 16-bit noise word being generated.  (This is provided I can tolerate only using two taps in the LFSR, hence asking.)  The pseudo-code looks like this:
> mov    [pointer+1],accumulator
> xor      [pointer],accumulator,[pointer++]
> The hardware modulo-addressing feature of the dsPIC and the post-increment of the address pointer take care of wrapping the circular buffer pointers. It means that I can just repeat those two instructions 48 times and it will produce 48 complete 16-bit words of noise right there in the buffer for me to read out when I need them (every 1ms.)

More information about the Synth-diy mailing list