Elusive bug in LFSR implementation

[gardhr]

Okay, so I've put together a basic LFSR class as well as a test driver to verify that it was implemented correctly (the driver employs a brute force approach that simply cycles through every possible configuration). After running a few iterations of the test I compared the results with this document. All of the odd-degree LFSR's seem to be working correctly, but for some reason none of the LFSR's that are built from even-degree polynomials produce maximal length sequences (MLS's). On closer inspection, the longest sequences turned out to be exactly half of the MLS for that particular degree of polynomial, and a nominal count of them turned out to be precisely the number of MLS's expected for said degree. So I spent the better half of yesterday on this (and now more in the wee hours today), but I just can't figure out where I went wrong. Can anyone provide some insight into this?

[DavX]

The problem seems to be in your next() function: you should only clock the shift register by one position each time so the following should be correct:

Uint next(void)
{
    Uint feedback = zero, taps = m_value & m_polynomial; 
    while(taps)
    {
        feedback ^= taps & one;
        taps >>= one;
    }
    m_value <<= one;
    m_value |= feedback;            
    m_value &= m_mask;
    return m_value;
}

That should solve your problem - hope it makes sense.

Dav

[oogabooga]

I was just going to say that!
At any rate, you probably would have got help sooner if you posted the code in code tags instead of attaching it.

[gardhr]

Of course! Such an unbelievably silly mistake, too. Oh well, problem solved now. Thanks so much for the keen eyes. Cheers!