[sdiy] Non maximal-length LFSR

Richie Burnett rburnett at richieburnett.co.uk
Thu Mar 3 15:51:21 CET 2016


Hi guys,

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

The advantage that I see of this approach is that by carefully choosing the 
48 words that are pre-loaded into the circular buffer at initialisation, I 
can seed each of the sixteen 48-bit LFSR algorithms to start at radically 
different places in their sequence, to eliminate any short-term correlation 
between the various bits within each noise word.  The XOR working on words 
calculates sixteen LFSRs simultaneously, so although they are mathematically 
all generating the same sequence, they can be seeded such that their 
long-sequences are misaligned by minutes, if not hours or days.  So for 
practical purposes each bit in the noise word is an independent noise source 
with poor correlation to the other bits.

That's why I'm keen to keep the shift-register length at 48.  Because 47 is 
one too few to make up my 1 millisecond output buffer, and 49 is one too 
many.

Incidentally what would happen if I ran the algorithm 49 times with a 49-bit 
shift-register for each audio frame, but just discarded the 49th word of 
noise each time.  Noise is random anyway, right?  so throwing away one word 
out of every 49 would still sound like random noise?  (It would surely sound 
better than generating 47 words and repeating the last one twice!)  But the 
length of the sequence would be 48/49th of the maximum length, but 2^49 is 
huge anyway, so I don't care?  Does that sound reasonable?

-Richie,


-----Original Message----- 
From: mskala at ansuz.sooke.bc.ca
Sent: Thursday, March 03, 2016 11:55 AM
To: Tom Wiltshire
Cc: synth-diy DIY
Subject: Re: [sdiy] Non maximal-length LFSR

On Thu, 3 Mar 2016, Tom Wiltshire wrote:
> Since all maximal length sequences produce the same values, and are
> similarly distributed, I don't see how one could sound significantly
> different to another. The distribution is key, since a rising binary
> count also produces all the output values, but it doesn't sound remotely
> random.

Two different maximal-length sequences will contain the same subsequences
up to the length of the register.  They'll contain very different sets
of subsequences of any greater length.  For instance, here are two
different maximal-length sequences for registers of length 5 (Perl code
below my signature):

taps at 5 and 2:
1010111011000111110011010010000

taps at 5, 4, 3, and 2:
1011010100011101111100100110000

One of these contains a string of 8 ones and 1 zero; the other does not
contain any nine-bit sequence with that much bias in either direction.
This will make a difference in what comes out if they go through an
integrator or low pass filter.  *I haven't tried it*, but it's reasonable
to guess that they might also sound different if changed into audio
waveforms.  The fact that people working on semiconductor testing do find
reasons to prefer some polynomials over others even though the preferred
ones are more expensive to build - and those people care a lot about
saving implementation complexity and wouldn't use the more expensive
polynomials without good reason - suggests that there are at least some
real ways in which different maximal-length sequences differ from each
other.

-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/

#!/usr/bin/perl

$x=1;

# $poly=0x12;
$poly=0x1E;

for ($y=0;$y<31;$y++) {
  print ($x&1);
  if ($x&1) {
    $x>>=1;
    $x^=$poly;
  } else {
    $x>>=1;
  }
}

print "\n";

_______________________________________________
Synth-diy mailing list
Synth-diy at dropmix.xs4all.nl
http://dropmix.xs4all.nl/mailman/listinfo/synth-diy


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




More information about the Synth-diy mailing list