Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
bsccara:
On a design I'm working on I use LFSR counters with 9 and 35 bit widths, using XNOR gates for the taps. The counters run from an initial set state to an all-zero one, which signals end-of-count. I need to know what initial state to set the counters to to take a specified number of clock ticks to the all-zero state. Does anyone know of an algorithm to calculate that initial state, apart from brute-force (with pre-computed sparse tables) ?
P.S. I have found a blog post that dwelves into it at https://www.embeddedrelated.com/showarticle/1114.php but it calculates the output bit only and I can't figure out the math to expand it to all bits.
ataradov:
LFSRs are fully reversible. There is only one state that would lead to 0. This state depends on the configuration of your taps. The same way, N-1 state can be reached from only one N-2 state.
So all you have to do is "play back" the sequence N times and you will arrive at the requested configuration.
bsccara:
You are right but that's the brute-force approach. Worst case I'd have to cycle through the algorithm 235-2 times to compute the initial condition (or split it half way and cycle through 234-2 times either direction, depending on the specified count). What I'm looking for is an algorithm that runs at a much lower cost, preferably something like N or N2, where N would be the LFSR size in bits.
ataradov:
No, you will need to cycle N times, where N is your number of steps that lead to the value of 0. LFSR size is irrelevant here.
bsdphk:
2^35 isn't really much for modern hardware.
Calculating LFSR's forward is much cheaper than backward, so the fastest strategy may be to start from zero, move forward, snapshot state every 2^28 steps until you get back to zero.
Now you know your cycle-length, so restart from the snapshot previous to your target and find it again.
As far as I know, there is no other way to ensure that the cycle which includes a particular value (in your case zero) has sufficient length to what you are trying to do.
See also: https://users.ece.cmu.edu/~koopman/crc/index.html
Specifically: https://users.ece.cmu.edu/~koopman/crc/crc36.html
Navigation
[0] Message Index
[#] Next page
Go to full version