[sdiy] Non maximal-length LFSR

[Richie Burnett]

Hi Brian,

I totally agree with what you have said.

What you are saying is to clock a single LFSR 16 times to produce 16 fresh 
uncorrelated bits to make up each 16-bit word of noise that I need.  This I 
understand, and have implemented before.  It gives good de-correlation 
between the bits of the noise but is expensive to implement in terms of CPU 
cycles.

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.

It's really hard to explain in an Email, but if you have the time and are 
still curious take a look at this code snippet I found online:-

http://faculty.uml.edu/jpropp/r250.c

This basically implements what I'm trying to do and is written in C so is 
surely easier to follow than dsPIC assembler!

As I said, I didn't invent this algorithm, I'm just trying to adapt what 
someone else has done, to make it suit my needs.  It took me ages to get my 
head around how it worked.

-Richie,



-----Original Message----- 
From: rsdio at audiobanshee.com
Sent: Thursday, March 03, 2016 7:17 PM
To: Richie Burnett
Cc: synth-diy DIY
Subject: Re: [sdiy] Non maximal-length LFSR

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?

Brian


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.)
>


-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2016.0.7442 / Virus Database: 4537/11740 - Release Date: 03/03/16