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

[0] Message Index

[#] Next page

[*] Previous page

There was an error while thanking
Thanking...
Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod