| Electronics > Projects, Designs, and Technical Stuff |
| Algorithm for calculating previous states of LFSR counters ? |
| (1/9) > >> |
| 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 |
| Message Index |
| Next page |