Thread: Elusive bug in LFSR implementation

  1. #1
    Registered User gardhr's Avatar
    Join Date
    Apr 2011

    Elusive bug in LFSR implementation

    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?
    Attached Files Attached Files

  2. #2
    Registered User
    Join Date
    Apr 2012
    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; 
            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.


  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #4
    Registered User gardhr's Avatar
    Join Date
    Apr 2011
    Of course! Such an unbelievably silly mistake, too. Oh well, problem solved now. Thanks so much for the keen eyes. Cheers!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 12-01-2009, 03:59 PM
  2. Replies: 7
    Last Post: 10-01-2008, 07:45 PM
  3. Finding the elusive memory leak...
    By dpro in forum C++ Programming
    Replies: 4
    Last Post: 08-31-2005, 11:58 PM
  4. Catching the elusive winsock
    By jinx in forum C++ Programming
    Replies: 0
    Last Post: 04-04-2002, 08:19 PM
  5. an elusive function
    By Unregistered in forum C Programming
    Replies: 8
    Last Post: 12-05-2001, 08:51 AM