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
There was an error while thanking
Thanking...

Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod