Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
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
[0] Message Index
[#] Next page
[*] Previous page
Go to full version