| Electronics > Projects, Designs, and Technical Stuff |
| Algorithm for calculating previous states of LFSR counters ? |
| << < (7/9) > >> |
| hamster_nz:
--- Quote from: Someone on July 03, 2019, 11:51:23 pm --- --- Quote from: bsccara on July 03, 2019, 06:24:25 pm ---for a lower Fmax and increased propagation delays, making timing closure much harder. --- End quote --- You're talking about a loadable counter, have you looked at the critical timing paths? Using a binary counter with "hard" carry resources and the overflow as your end of count indicator is likely to be faster than an lfsr and the comparison logic. --- End quote --- I initially thought that too, but the LFSR with two taps soon becomes quicker that a long counter as bit length grows. For example in Spartan 3 the carry chain is ~0.05 ns per bit. so a 36 bit counter needs 1.8ns for just carry chain alone, and then you need at least one level of logic in the loop as a MUX to load the preset values. A long "LFSR with load" and two taps requires only one level of logic, making it at least 1.8ns faster than the a long counter (in Spartan 3). The logic required to detect the zero state is another thing. That would need to be pipelined to run fast... |
| langwadt:
--- Quote from: hamster_nz on July 04, 2019, 12:27:11 am --- --- Quote from: Someone on July 03, 2019, 11:51:23 pm --- --- Quote from: bsccara on July 03, 2019, 06:24:25 pm ---for a lower Fmax and increased propagation delays, making timing closure much harder. --- End quote --- You're talking about a loadable counter, have you looked at the critical timing paths? Using a binary counter with "hard" carry resources and the overflow as your end of count indicator is likely to be faster than an lfsr and the comparison logic. --- End quote --- I initially thought that too, but the LFSR with two taps soon becomes quicker that a long counter. For example in Spartan 3 the carry chain is ~0.05 ns per bit. so a 36 bit counter needs 1.8ns for just carry chain alone, and then you need at least one level of logic in the loop as a MUX to load the preset values. A long "LFSR with load" and two taps requires only one level of logic, making it at least 1.8ns faster than the a long counter (in Spartan 3). The logic required to detect the zero state is another thing. That would need to be pipelined to run fast... --- End quote --- a single bit as prescaler/CE on a 35 bit counter and you have twice as much time ? |
| hamster_nz:
Curiosity got the better of me. Here is the implementation for the 9-bit LFSR, that dynmically builds the tables test it works for all values. The 36-bit one will involve: - changing uint32_t to uint64_t - changing BITS to 36 - changing the taps used in advance_lfsr() - a slightly longer time to test for all values. ;D --- Code: --- #include <stdio.h> #include <stdint.h> #define BITS (9) static uint32_t magic_zero[BITS]; static uint32_t magic[BITS][BITS]; /***************************************** * The LFSR calculation ****************************************/ static uint32_t advance_lfsr(uint32_t state) { uint32_t new_bit; new_bit = 1^((state & 0x100) ? 1 : 0) ^ ((state & 0x010) ? 1 : 0); state = (state << 1 )|new_bit; state &= (1<<BITS)-1; return state; } /***************************************** * The LFSR speedup, that advances 2^bit_to_advance ****************************************/ static uint32_t advance_fast(uint32_t state, int bit_to_advance) { uint32_t guess, i; guess = magic_zero[bit_to_advance]; for(i = 0; i < BITS; i++) { if((state & (1<<i)) != 0) guess ^= magic[bit_to_advance][i]; } return guess; } /***************************************** * Calculate the magic values that are the * future contributions of 'zero' and than * the contribuions of each bit. ****************************************/ static void calculate_magic_values(void) { int i, bit; /* Calculate the first entry, using the traditional LFSR function */ magic_zero[0] = advance_lfsr(0); for(i = 0; i < BITS; i++) { magic[0][i] = advance_lfsr(1<<i) ^ magic_zero[0]; } /* Calculate all other entries, by applying the last set of values twice */ for(bit=1; bit < BITS; bit++) { uint32_t state = 0; state = advance_fast(state,bit-1); state = advance_fast(state,bit-1); magic_zero[bit] = state; for(i = 0; i < BITS; i++) { state = 1<<i; state = advance_fast(state,bit-1); state = advance_fast(state,bit-1); magic[bit][i] = state ^ magic_zero[bit]; } } /* Print out the table */ for(i = 0; i < BITS; i++) { printf("%03x", magic_zero[i]); for(bit = 0; bit < BITS; bit++) { printf(" %03x", magic[i][bit]); } printf("\n"); } } int main(int argc, char *argv[]) { uint32_t distance; calculate_magic_values(); /* Verify that it works for all distances */ for(distance = 0; distance < 1<<BITS; distance++) { uint32_t initial = 0; uint32_t state = initial; printf("\n"); printf("distance = %i\n", distance); printf("State Calculated Guessed Error?\n"); do { uint32_t calced, guess, i; /* Calculate it the fast way */ guess = state; for(i = 0; i < BITS; i++) { if((distance & (1<<i)) != 0) { guess = advance_fast(guess,i); } } /* Now calculate it the long way */ calced = state; for(i = 0; i < distance; i++) { calced = advance_lfsr(calced); } /* Show results */ printf("%03x %03x %03x %s\n", state, calced, guess, calced ^ guess ? "yes" : "no"); /* Move on to next state */ state = advance_lfsr(state); } while(state != initial); } return 0; } --- End code --- |
| Someone:
--- Quote from: hamster_nz on July 04, 2019, 12:27:11 am --- --- Quote from: Someone on July 03, 2019, 11:51:23 pm --- --- Quote from: bsccara on July 03, 2019, 06:24:25 pm ---for a lower Fmax and increased propagation delays, making timing closure much harder. --- End quote --- You're talking about a loadable counter, have you looked at the critical timing paths? Using a binary counter with "hard" carry resources and the overflow as your end of count indicator is likely to be faster than an lfsr and the comparison logic. --- End quote --- I initially thought that too, but the LFSR with two taps soon becomes quicker that a long counter as bit length grows. For example in Spartan 3 the carry chain is ~0.05 ns per bit. so a 36 bit counter needs 1.8ns for just carry chain alone, and then you need at least one level of logic in the loop as a MUX to load the preset values. A long "LFSR with load" and two taps requires only one level of logic, making it at least 1.8ns faster than the a long counter (in Spartan 3). The logic required to detect the zero state is another thing. That would need to be pipelined to run fast... --- End quote --- ... so if you're able to accept pipelining the comparison, then why not pipeline a binary (and/or other types of) counter in the first place? |
| hamster_nz:
--- Quote from: Someone on July 05, 2019, 01:11:31 am ---... so if you're able to accept pipelining the comparison, then why not pipeline a binary (and/or other types of) counter in the first place? --- End quote --- More a question for the OP, but I assume their view is it takes a problem you can solve with simple, fast, well understood hardware design and some not-too-hard software into one that needs tricky (and maybe unfeasible) hardware design with the goal of making it simple for software. |
| Navigation |
| Message Index |
| Next page |
| Previous page |