repak shawahb
sufficiently advanced magic is indistinguishable from madness

^
   

rsw@jfet.org


blogroll

        
Fri, 29 Feb 2008

white event

Tonight I was playing around with Octave et al studying the frequency content of sequences generated by a 16-bit LFSR as a function of its feedback polynomial. Using a random selection from Philip Koopman's list of feedback polynomials that produce maximal 16-bit LFSRs, I generated the corresponding sequence and plotted its FFT in Octave.

What I found, effectively, is that more terms in the feedback polynomial whitens the sequence rather substantially. For example, a short feedback polynomial (0x8148) produces the following spectrum:

On the other hand, the spectrum for 0xfff6 looks like this:

This suggests that feedback polynomials with lots of terms are better for dithering sequences. The downside of this, of course, is that each term requires an additional XOR. Fortunately, if you use a Galois LFSR the computation delay is independent of the number of terms.

In case you're curious (more or less identical to what's in the Wikipedia article): 

#include <stdio.h>
#include <stdint.h>

int main(int argc, char **argv)
{
        uint16_t poly;
        uint16_t lfsr = 1;
        uint16_t period = 0;

        if (argc > 1) { poly = (uint16_t) strtoul(argv[1],NULL,0); }
        else { poly = 0xb400; }


        do {
                lfsr = (lfsr >> 1) ^ (-(lfsr & 1) & poly);
                printf("%d\n",lfsr);
        } while (lfsr != 1);
}

All the data, code, et cetera is also available.


[ permalink | 1 comment ]