| Electronics > Projects, Designs, and Technical Stuff |
| Algorithm for calculating previous states of LFSR counters ? |
| << < (4/9) > >> |
| hamster_nz:
So what *exactly* do you know, and what exactly do you want to find out? For example, if you precompute the LFSR in a (maybe 512GB) table you can find the distance between two states in two lookups. |
| ataradov:
You know the polynomial. You also know a number N . The current state is 0 (or any other fixed state). The goal is to find out what state was N generations ago. |
| hamster_nz:
As it is a linear system, it appears you can decompose the state into a set of bits, have precalced values for those bits advanced through N states, and then recombine them. So you could have precanceled values for advancing the LFSR through 2^24 bits, and through 2^12 bits, and of course, one bit. You can then take a 36-bit LFSR through to any state in at most 2 ^12 * 3 operations, rather than 2^36-1 operations, With 36 sets of precalculated values (first set to advance through 1 state, second to advance through 2 states, advance through 4 states, ... advance through 2^34 states, advance through 2^35 states), you move through any number of states in 36 decompose-lookup-merge operations. Calculating these is table values relatively simple. Calculate the first set, use them twice to calculate the second set. Use them twice to calculate next set, and so on. The code below is a maximal 5-bit XNOR LFSR, and calculates four states ahead. --- Code: ---#include <stdio.h> #include <stdint.h> uint32_t advance_lfsr(uint32_t state) { uint32_t new_bit; new_bit = 1^((state & 0x10) ? 1 : 0) ^ ((state & 0x02) ? 1 : 0); state = (state << 1 )|new_bit; state &= 0x1f; return state; } int main(int argc, char *argv[]) { uint32_t initial = 0x00; uint32_t state = initial; printf("Calculated and guessed are the LFSR advanced by 4 states\n"); printf("\n"); printf("State Calculated Guessed Error?\n"); do { uint32_t guess, calced, i; guess = 0x0c; if((state & 0x01) != 0) guess ^= 0x19 ^ 0x0C; if((state & 0x02) != 0) guess ^= 0x07 ^ 0x0C; if((state & 0x04) != 0) guess ^= 0x0e ^ 0x0C; if((state & 0x08) != 0) guess ^= 0x09 ^ 0x0C; if((state & 0x10) != 0) guess ^= 0x06 ^ 0x0C; calced = state; for(i = 0; i < 4; i++) { calced = advance_lfsr(calced); } printf("%02x %02x %02x %s\n", state, calced, guess, calced ^ guess ? "yes" : "no"); state = advance_lfsr(state); } while(state != initial); return 0; } --- End code --- And the results: --- Code: ---Calculated and guessed are the LFSR advanced by 4 states State Calculated Guessed Error? 00 0c 0c no 01 19 19 no 03 12 12 no 06 05 05 no 0c 0b 0b no 19 16 16 no 12 0d 0d no 05 1b 1b no 0b 17 17 no 16 0f 0f no 0d 1e 1e no 1b 1d 1d no 17 1a 1a no 0f 15 15 no 1e 0a 0a no 1d 14 14 no 1a 08 08 no 15 11 11 no 0a 02 02 no 14 04 04 no 08 09 09 no 11 13 13 no 02 07 07 no 04 0e 0e no 09 1c 1c no 13 18 18 no 07 10 10 no 0e 00 00 no 1c 01 01 no 18 03 03 no 10 06 06 no --- End code --- Why would you be needing to do this? (Oh the key point I missed is that going forward by four states is the same as going backwards by (2^n-1)-4 states). |
| bsccara:
Thank you all for your replies, particularly 'hamster_nz'. As to the why... I'm implementing a design that requires multiple counters working as timers. I need them to take a programmable number of clock cycles to reach all-zeros, which signals end-of-count. These counters are implemented on a FPGA along with a lot more logic, so I need the counters to be as fast as possible (the feedback network needs to be simple) to be able to achieve timing closure and as nimble as possible on the resources. Hence LFSRs. I don't care about which states the counters go through as long as the number of them match the programmable setting. So I need to calculate which value to program into the counters as a starting state in order for them to go through that number of states prior to reaching all-zeros. These values will be provided from outside the FPGA, from software running on a PC. Since each counter may run consecutively with different starting states, up to thousands of count cycles back to back, I need the calculation to be fast. Presently I'm using brute force along with a pre-computed sparse table but the original question was if a better way existed. 'hamster_nz', I'm now looking into your reply to figure out if those pre-computed tables are feasable. |
| StillTrying:
I've always thought that whatever sequence a LFSR counts, you can always create another one that counts through the same sequence but in reverse, I could be wrong though. :) The output stream is reversible; an LFSR with mirrored taps will cycle through the output sequence in reverse order. https://en.wikipedia.org/wiki/Linear-feedback_shift_register |
| Navigation |
| Message Index |
| Next page |
| Previous page |