[sdiy] LFSR using lookup tables

Ben Stuyts ben at stuyts.nl
Thu Feb 20 17:51:16 CET 2020


Hi Tom,

I have done a quick and dirty test using the LFSR routines from https://en.wikipedia.org/wiki/Linear-feedback_shift_register <https://en.wikipedia.org/wiki/Linear-feedback_shift_register>. See that page for the lfsr1.. lfsr3 routines. I also added lfsr4() which is basically the lfsr1() routine with a lookup table:

uint16_t bittable[256];

void init_lfsr4(void)
{
    int i;
    uint16_t bit;

    for (i=0; i<256; i++)
    {
        /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = ((i >> 0) ^ (i >> 2) ^ (i >> 3) ^ (i >> 5)) /* & 1u */;
        bittable[i] = bit << 15;
    }
}

unsigned lfsr4(void)
{
    // as lfsr1, but use lookup table

    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<15 later in the code */
    unsigned period = 0;

    do
    {   /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = bittable[lfsr & 0xff];
        lfsr = (lfsr >> 1) | bit;
        ++period;

        PORTB = lfsr; // make noise on beeper output PB4
    }
    while (lfsr != start_state);

    return period;
}

I compiled this for a 16 MHz Atmega128 using the CrossWorks compiler with max optimisation on and timed each routine:

lfsr1  t = 1257 ms, n = 65535, bps = 52136.039062
lfsr2l t =  243 ms, n = 65535, bps = 269691.343750
lfsr2r t =  223 ms, n = 65535, bps = 293878.937500
lfsr3  t = 2768 ms, n = 65535, bps = 23675.939453
lfsr4  t =  325 ms, n = 65535, bps = 201646.156250

So lfsr4() using the lookup table gave a 4 times improvement over lfsr1(). But interestingly, the Galois LFSRs lfsr2l and lfsr2r (for left and right shifting versions) were even faster. This makes sense if you look at the source code, it is very simple.

This is a very simple test of course, and many optimisations can be made. Perhaps shifting per byte and not per bit. And not using C… But I just wanted to have a ballpark relative comparison.

Ben



> On 19 Feb 2020, at 19:04, Ben Stuyts <ben at stuyts.nl> wrote:
> 
> Hi Tom,
> 
> Your link was the first I looked up after watching that video, as your noise pic’s were the first thing that came to my mind. :-)
> 
> Ben
> 
> 
>> On 19 Feb 2020, at 15:17, Tom Wiltshire <tom at electricdruid.net <mailto:tom at electricdruid.net>> wrote:
>> 
>> I shall be interested to hear how you get on, Ben.
>> 
>> I *love* a nice look-up table. My first rule is “Don’t do hard sums!”, which means “pretty much anything beyond an addition”!
>> 
>> I suspect for the very-lower-level stuff I’ve been doing, the table overhead is worse than the alternative (doing shifts of the LFSR one byte at a time, as described here: https://electricdruid.net/practical-lfsr-random-number-generators/ <https://electricdruid.net/practical-lfsr-random-number-generators/>). But it’d great if it wasn’t!
>> 
>>> On 19 Feb 2020, at 13:43, Ben Stuyts <ben at stuyts.nl <mailto:ben at stuyts.nl>> wrote:
>>> 
>>> I just watched this interesting talk about using lookup tables (in hardware and software): https://www.youtube.com/watch?v=LnqqvVp_UZg <https://www.youtube.com/watch?v=LnqqvVp_UZg>
>>> 
>>> At the very last end (around 29:11 minutes) he starts talking about LFSR's and maximising their performance using lookup tables instead of the more conventional XOR method. He has a 6 times performance increase. Very cool, I’m going to try this out soon.
>>> 
>>> Ben
>>> 
>>> 
>>> _______________________________________________
>>> Synth-diy mailing list
>>> Synth-diy at synth-diy.org <mailto:Synth-diy at synth-diy.org>
>>> http://synth-diy.org/mailman/listinfo/synth-diy <http://synth-diy.org/mailman/listinfo/synth-diy>
>> 
> 
> _______________________________________________
> Synth-diy mailing list
> Synth-diy at synth-diy.org
> http://synth-diy.org/mailman/listinfo/synth-diy

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://synth-diy.org/pipermail/synth-diy/attachments/20200220/514856a9/attachment.htm>


More information about the Synth-diy mailing list