[sdiy] Non maximal-length LFSR

rsdio at audiobanshee.com rsdio at audiobanshee.com
Fri Mar 4 07:43:23 CET 2016


I partly understood what you're doing.

I had started to ask whether you needed to pull 1 bit from each array to produce a 16-bit sample, and then I realized that you are effectively running 16 LFSRs in parallel. That much makes sense.

My problem is two-fold:

A) that you're XOR'ing two "bits" that are adjacent. If you look at r250.c, that example takes bits that are very far apart. As I mentioned in my first reply, I usually see at least two bit cells between each bit that is taken for the XOR, and certainly more than 0.

B) I don't understand why your LFSR length has to be related to your 48 kHz sample rate. You're not using more than one word of your 48-word buffer, are you? That won't really work well, because each word is related to the others in the buffer, and you'd produce the exact same noise signal with a phase shift. My understanding is that you can really only use one word from your LFSR buffer, and you merely need to make the buffer long enough that the maximum length before repetition is long enough to avoid detection. The unused words in the buffer are merely there to provide a long enough state history that the signal produced by the 1 word you use won't repeat too soon.

Brian


On Mar 3, 2016, at 11:55 AM, Richie Burnett <rburnett at richieburnett.co.uk> wrote:
> 
> 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
> 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.)



More information about the Synth-diy mailing list