Author Topic: Algorithm for calculating previous states of LFSR counters ?  (Read 5794 times)

0 Members and 1 Guest are viewing this topic.

Offline bsccaraTopic starter

  • Contributor
  • Posts: 23
  • Country: pt
On a design I'm working on I use LFSR counters with 9 and 35 bit widths, using XNOR gates for the taps. The counters run from an initial set state to an all-zero one, which signals end-of-count. I need to know what initial state to set the counters to to take a specified number of clock ticks to the all-zero state. Does anyone know of an algorithm to calculate that initial state, apart from brute-force (with pre-computed sparse tables) ?

P.S. I have found a blog post that dwelves into it at https://www.embeddedrelated.com/showarticle/1114.php but it calculates the output bit only and I can't figure out the math to expand it to all bits.
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #1 on: July 02, 2019, 05:44:43 pm »
LFSRs are fully reversible. There is only one state that would lead to 0. This state depends on the configuration of your taps. The same way, N-1 state can be reached from only one N-2 state.

So all you have to do is "play back" the sequence N times and you will arrive at the requested configuration.
Alex
 

Offline bsccaraTopic starter

  • Contributor
  • Posts: 23
  • Country: pt
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #2 on: July 02, 2019, 06:59:27 pm »
You are right but that's the brute-force approach. Worst case I'd have to cycle through the algorithm 235-2 times to compute the initial condition (or split it half way and cycle through 234-2 times either direction, depending on the specified count). What I'm looking for is an algorithm that runs at a much lower cost, preferably something like N or N2, where N would be the LFSR size in bits.
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #3 on: July 02, 2019, 07:01:20 pm »
No, you will need to cycle N times, where N is your number of steps that lead to the value of 0. LFSR size is irrelevant here.
Alex
 

Offline bsdphk

  • Regular Contributor
  • *
  • Posts: 212
  • Country: dk
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #4 on: July 02, 2019, 08:45:07 pm »
2^35 isn't really much for modern hardware.

Calculating LFSR's forward is much cheaper than backward, so the fastest strategy may be to start from zero, move forward, snapshot state every 2^28 steps until you get back to zero.

Now you know your cycle-length, so restart from the snapshot previous to your target and find it again.

As far as I know, there is no other way to ensure that the cycle which includes a particular value (in your case zero) has sufficient length to what you are trying to do.

See also: https://users.ece.cmu.edu/~koopman/crc/index.html

Specifically: https://users.ece.cmu.edu/~koopman/crc/crc36.html
 

Offline bsccaraTopic starter

  • Contributor
  • Posts: 23
  • Country: pt
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #5 on: July 02, 2019, 09:33:53 pm »
Alex, we're saying the same thing; being a 35 bit counter and having a maximum period of 235 - 1 if a count of 235-2 is needed the algorithm would have to cycle that many times (or alternatively once, going forward). That's what I want to avoid. The blog post I mentioned (check out the 'Time shifts' section) seems much faster but calculates just the output bit and relies on finite fields math that I don't fully understand.
bsdphk, as for 235 not being much, the code I now use to precalculate the sparse table (currectly the table stores every 220th initial state but all states are computed, obviously) takes several minutes to run; granted that it may not be the greatest code nor particularly optimized but thats orders of magnitude slower than what I'd like it to be.
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #6 on: July 02, 2019, 09:37:16 pm »
Ah, OK. I thought your look back number was relatively small. This is an interesting problem, I would need to think about it a bit more.
Alex
 

Offline rstofer

  • Super Contributor
  • ***
  • Posts: 9963
  • Country: us
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #7 on: July 03, 2019, 01:44:07 am »
If a LFSR is truly reversible, why not just start with an output of zero.  There is only one prior state that, when mangled by the XOR gates, leads to zero  for the next state and it would seem to me that starting in state zero, the next state is exactly the state that transitions to zero when counting forward.

Or not...  I haven't thought about LFSRs in many years.
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #8 on: July 03, 2019, 01:47:54 am »
That is exactly what I'm proposing. The problem is that it may still require 2^35 iterations. I mean you can shorten it to 2^34 and iterate either backward or forward depending on what is closer.

Presumably there is some magic that could take polynomial and offset N, and then quickly jump by N from any valid state. You would do precomputation on the polynomial alone before. This is what happens in the article - polynomials are expressed in the matrix form and then matrix exponentiation is used to quickly evaluate jumped value. But I have no idea how to apply this to movements back. I guess you could just move forward by 2^35-N using that stuff. But it is still not trivial.

I would be interested to know what is the actual application of this. It may be  solved much easier.
« Last Edit: July 03, 2019, 01:52:50 am by ataradov »
Alex
 

Offline 0culus

  • Super Contributor
  • ***
  • Posts: 3032
  • Country: us
  • Electronics, RF, and TEA Hobbyist
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #9 on: July 03, 2019, 01:54:30 am »
If a LFSR is truly reversible, why not just start with an output of zero.  There is only one prior state that, when mangled by the XOR gates, leads to zero  for the next state and it would seem to me that starting in state zero, the next state is exactly the state that transitions to zero when counting forward.

Or not...  I haven't thought about LFSRs in many years.

All zero is a lockup state, so that won't work. Doesn't apply to XNOR
« Last Edit: July 03, 2019, 01:59:43 am by 0culus »
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #10 on: July 03, 2019, 01:57:05 am »
All zero is a lockup state, so that won't work.
Not for the XNOR-based LFSR. In that case all-1s is a lock up state. LFSR can't naturally produce its lock up state, so you could never arrive at it.
Alex
 

Offline 0culus

  • Super Contributor
  • ***
  • Posts: 3032
  • Country: us
  • Electronics, RF, and TEA Hobbyist
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #11 on: July 03, 2019, 01:59:22 am »
All zero is a lockup state, so that won't work.
Not for the XNOR-based LFSR. In that case all-1s is a lock up state. LFSR can't naturally produce its lock up state, so you could never arrive at it.

Ahh, I missed the XNOR part. My bad.
 

Offline T3sl4co1l

  • Super Contributor
  • ***
  • Posts: 22436
  • Country: us
  • Expert, Analog Electronics, PCB Layout, EMC
    • Seven Transistor Labs
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #12 on: July 03, 2019, 02:20:47 am »
It runs same forwards as backwards, no?  So just do the same thing with the inverted matrix.  (I'd... have to read that rather in depth to know if the matrix representation even is invertible, but it should be?)

That gives you access to a parallel computing approach.  Sample the space with a series of exponentiated shortcuts, then linear search from each of those points.  You could binary search if the sequence were ordered, but it's not that kind of ring unfortunately.  Actually, is that wrong?  It's a linear function, so it has to work with superposition.  But with XOR rather than addition-with-carry, there's still no ordering to it?

You can certainly precalculate the steps nearest to zero, saving a few there; but I'm not sure that there's anything more to find beyond that?  It gets to be more of a crypto question...

Tim
Seven Transistor Labs, LLC
Electronic design, from concept to prototype.
Bringing a project to life?  Send me a message!
 

Offline cur8xgo

  • Regular Contributor
  • *
  • Posts: 148
  • Country: us
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #13 on: July 03, 2019, 02:53:36 am »
It gets to be more of a crypto question...


ya I bet if you read about weaknesses of LSFR based security or LSFR predictability you will get a few papers or articles that show how to break them without brute force

or at least a clear statement that brute force is the only way

 

Online Siwastaja

  • Super Contributor
  • ***
  • Posts: 9330
  • Country: fi
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #14 on: July 03, 2019, 06:10:53 am »
Needing no data and completely fitting CPU registers, this is a problem that should parallelize very well. Try to run it on GPU so you have hundreds of the shader CPUs executing in parallel? Give each one a different start state from your sparse precomputed table.
 

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2812
  • Country: nz
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #15 on: July 03, 2019, 06:36:00 am »
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.


Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Online ataradov

  • Super Contributor
  • ***
  • Posts: 11905
  • Country: us
    • Personal site
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #16 on: July 03, 2019, 06:47:34 am »
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.
Alex
 

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2812
  • Country: nz
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #17 on: July 03, 2019, 10:25:58 am »
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: [Select]
#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;
}

And the results:
Code: [Select]
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

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).
« Last Edit: July 03, 2019, 10:45:04 am by hamster_nz »
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 
The following users thanked this post: T3sl4co1l, Forty-Bot

Offline bsccaraTopic starter

  • Contributor
  • Posts: 23
  • Country: pt
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #18 on: July 03, 2019, 02:25:36 pm »
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.
 

Offline StillTrying

  • Super Contributor
  • ***
  • Posts: 2850
  • Country: se
  • Country: Broken Britain
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #19 on: July 03, 2019, 03:43:11 pm »
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
.  That took much longer than I thought it would.
 

Offline duak

  • Super Contributor
  • ***
  • Posts: 1048
  • Country: ca
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #20 on: July 03, 2019, 04:02:39 pm »
Could you break the 35 bit LFSR into smaller segments that would be easier to un-hash?  eg., if I wanted to count to 100 in decimal, I could use a 7-bit binary counter and convert to decimal or I could use two 4-bit BCD counters.  Here, two 18 bit LFSRs could be cascaded.  The more significant LFSR would only shift when the least significant LFSR is in state 0.  It might make more sense to use even smaller segments to speed up the un-hash conversion.
 

Offline bsccaraTopic starter

  • Contributor
  • Posts: 23
  • Country: pt
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #21 on: July 03, 2019, 06:24:25 pm »
'duak', that would reduce the maximum number of steps (and inherently maximum count) for the same bit size, as a 36 bit LFSR would have a maximum period of 236-1, while two 18 bit ones would have a (218-1)2 maximum period. Also having the most significant LFSR being enabled through a multi-LUT zero detection would make for a lower Fmax and increased propagation delays, making timing closure much harder.
 

Offline duak

  • Super Contributor
  • ***
  • Posts: 1048
  • Country: ca
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #22 on: July 03, 2019, 07:52:12 pm »
bsccara: yes, you are correct that the segmented LFSR counter scheme is not as efficient, however if my algebra is correct the maximum period is 2^36 - 2*2^18 + 1.  This is greater than 2^35 which is your minimum requirement.

If I remember correctly, LFSRs can be described using Galois Fields.  I know nothing more although I understand that the French cigarettes are named after Evariste Galois, the mathematician that developed the theory behind them.

I don't know what device(s) you are planning to use to implement the counters - FPGAs or gate arrays or ?.  I agree there will likely be another gate delay that has to be compensated for.

I think the limiting speed of the entire counter chain is determined by two factors (in addition to the clock rate of the flips-flops):

1.) detecting zero - depending on the resources of the device, this could be as simple as a wired-OR or something as complicated  as a multilevel tree.  It may be possible to pipeline the zero detect and have it spread over two clock cycles.  This could be compensated for by adjusting the preload pattern by one.  Alternately, you could also detect the state before all zeros.  However, these schemes will limit the minimum count.

2.) the second LFSR segment will need to be enabled for one clock cycle at a time - basically the 'carry' or zero detect out of the first segment.  Again, I don't know what resources your device has, but what is needed is either a 'D' flip-flop with an enable input or a gateable clock.
 
The following users thanked this post: Someone

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2812
  • Country: nz
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #23 on: July 03, 2019, 09:44:20 pm »
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.

If you tell me enough to know what you are doing I might end up doing most of the work for you...  ;D

e.g. which polynomial  - Maybe I should just assume 35,33 & 9,5.
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Online ejeffrey

  • Super Contributor
  • ***
  • Posts: 4033
  • Country: us
Re: Algorithm for calculating previous states of LFSR counters ?
« Reply #24 on: July 03, 2019, 10:10:46 pm »
IIRC LFSR can be trivially reversed.  I think what you do is mirror the taps and then it will cycle through mirrored state registers in reverse order.  I don't exactly remember the details but it should be easy to figure out.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf