Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
<< < (6/9) > >>
bsccara:
'duak', I've tested your idea prior to my reply using the following HDL:


--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity Timer2 is
port
(
CLK: in std_logic;
COUNT: out std_logic_vector(35 downto 0)
);
end Timer2;
 
architecture RTL of Timer2 is
signal lfsr1: std_logic_vector(18 downto 1) := (others => '0');
signal lfsr2: std_logic_vector(18 downto 1) := (others => '0');
begin
process(CLK)
begin
if rising_edge(CLK) then
lfsr1(1) <= lfsr1(18);
lfsr1(11 downto 2) <= lfsr1(10 downto 1);
lfsr1(12) <= lfsr1(11) xnor lfsr1(18);
lfsr1(18 downto 13) <= lfsr1(17 downto 12);
end if;
end process;

process(CLK)
begin
if rising_edge(CLK) then
if lfsr1 = "000000000000000000" then
lfsr2(1) <= lfsr2(18);
lfsr2(11 downto 2) <= lfsr2(10 downto 1);
lfsr2(12) <= lfsr2(11) xnor lfsr2(18);
lfsr2(18 downto 13) <= lfsr2(17 downto 12);
end if;
end if;
end process;

COUNT <= lfsr2 & lfsr1;
end RTL;

--- End code ---

and used the following for a single, larger LFSR:


--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity Timer is
port
(
CLK: in std_logic;
COUNT: out std_logic_vector(34 downto 0)
);
end Timer;
 
architecture RTL of Timer is
signal lfsr: std_logic_vector(35 downto 1) := (others => '0');
begin
process(CLK)
begin
if rising_edge(CLK) then
lfsr(1) <= lfsr(35);
lfsr(33 downto 2) <= lfsr(32 downto 1);
lfsr(34) <= lfsr(33) xnor lfsr(35);
lfsr(35) <= lfsr(34);
end if;
end process;

COUNT <= lfsr;
end RTL;

--- End code ---

I ran both through the Lattice Diamond toolchain, using LSE for synthesis, as top-level modules. And I got these results for Fmax for the CLK signal on a Mach XO2:

Stage2 x 18 bit LFSR1 x 35 bit LFSRSynthesis136.799 MHz298.240 MHzMap139.762 MHz400.000 MHzPlace & Route177.305 MHz358.938 MHz
Given these results I'd rather stick with my current LFSR design; the zero detection is not a (big) issue as it is indeed pipelined and the timer as a whole can run at well over 200 MHz.
bsccara:
'hamster_nz', indeed you are correct on the polynomials. Also I'd like to thank your interest on my question as I'm struggling with your algorithm. Your code uses several 'magic' values that I don't quite get their origins but they do seem to be (or at least they are equal to):


--- Code: ---0x0c == fourth state after 00000
0x19 == fourth state after 00001
0x07 == fourth state after 00010
0x0e == fourth state after 00100
0x09 == fourth state after 01000
0x06 == fourth state after 10000

--- End code ---

If I'm correct your code is very efficient at computing the state at a fixed offset from any initial state, requiring only six 'magic' values. But I need to be able to compute the state at any offset from a fixed initial state (given the periodic nature of the LFSR, as you already mentioned, that initial state can be 0 and the offset can be reversed). From your code and explanation the first 'magic' value alone would require a table with one element for each possible offset, totally negating the purpose of the algorithm. So, can you clarify the origin of those 'magic' numbers ?
langwadt:

--- Quote from: bsccara on July 03, 2019, 10:35:33 pm ---'duak', I've tested your idea prior to my reply using the following HDL:


--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity Timer2 is
port
(
CLK: in std_logic;
COUNT: out std_logic_vector(35 downto 0)
);
end Timer2;
 
architecture RTL of Timer2 is
signal lfsr1: std_logic_vector(18 downto 1) := (others => '0');
signal lfsr2: std_logic_vector(18 downto 1) := (others => '0');
begin
process(CLK)
begin
if rising_edge(CLK) then
lfsr1(1) <= lfsr1(18);
lfsr1(11 downto 2) <= lfsr1(10 downto 1);
lfsr1(12) <= lfsr1(11) xnor lfsr1(18);
lfsr1(18 downto 13) <= lfsr1(17 downto 12);
end if;
end process;

process(CLK)
begin
if rising_edge(CLK) then
if lfsr1 = "000000000000000000" then
lfsr2(1) <= lfsr2(18);
lfsr2(11 downto 2) <= lfsr2(10 downto 1);
lfsr2(12) <= lfsr2(11) xnor lfsr2(18);
lfsr2(18 downto 13) <= lfsr2(17 downto 12);
end if;
end if;
end process;

COUNT <= lfsr2 & lfsr1;
end RTL;

--- End code ---

and used the following for a single, larger LFSR:


--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity Timer is
port
(
CLK: in std_logic;
COUNT: out std_logic_vector(34 downto 0)
);
end Timer;
 
architecture RTL of Timer is
signal lfsr: std_logic_vector(35 downto 1) := (others => '0');
begin
process(CLK)
begin
if rising_edge(CLK) then
lfsr(1) <= lfsr(35);
lfsr(33 downto 2) <= lfsr(32 downto 1);
lfsr(34) <= lfsr(33) xnor lfsr(35);
lfsr(35) <= lfsr(34);
end if;
end process;

COUNT <= lfsr;
end RTL;

--- End code ---

I ran both through the Lattice Diamond toolchain, using LSE for synthesis, as top-level modules. And I got these results for Fmax for the CLK signal on a Mach XO2:

Stage2 x 18 bit LFSR1 x 35 bit LFSRSynthesis136.799 MHz298.240 MHzMap139.762 MHz400.000 MHzPlace & Route177.305 MHz358.938 MHz
Given these results I'd rather stick with my current LFSR design; the zero detection is not a (big) issue as it is indeed pipelined and the timer as a whole can run at well over 200 MHz.

--- End quote ---

how does that compare to a regular counter maybe with a bit or two of prescaler?
hamster_nz:

--- Quote from: bsccara on July 03, 2019, 10:56:39 pm ---'hamster_nz', indeed you are correct on the polynomials. Also I'd like to thank your interest on my question as I'm struggling with your algorithm. Your code uses several 'magic' values that I don't quite get their origins but they do seem to be (or at least they are equal to):


--- Code: ---0x0c == fourth state after 00000
0x19 == fourth state after 00001
0x07 == fourth state after 00010
0x0e == fourth state after 00100
0x09 == fourth state after 01000
0x06 == fourth state after 10000

--- End code ---

If I'm correct your code is very efficient at computing the state at a fixed offset from any initial state, requiring only six 'magic' values. But I need to be able to compute the state at any offset from a fixed initial state (given the periodic nature of the LFSR, as you already mentioned, that initial state can be 0 and the offset can be reversed). From your code and explanation the first 'magic' value alone would require a table with one element for each possible offset, totally negating the purpose of the algorithm. So, can you clarify the origin of those 'magic' numbers ?

--- End quote ---

I did leave enough breadcrumbs  ;D

I got those numbers exactly as you suggested -  I put 00 as the initial state of the LFSR, and ran it forward four states, giving 0C.

I then put 01 ran it forward four states, giving 19. To isolate the change that bit makes, I have to remove the change that would occur even if this bit wasn't set, hence why it is XORed with 0C

I then did the same for 02, 04, 08 & 10, so I know what effect that having each bit set leads to four cycles into the future.

There isn't anything magical about the number four, I just wanted something I could count lines on the screen.

So what if I want to jump ahead 8 states? Easy - just run it through it twice.


--- Code: ---
          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

          // advance the state four cycles into the future
          state = guess;
          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

          state = guess;
          // statue is now 8 cycles into the future

--- End code ---
         
Now If I run 00, 01, 02, 04, 08 and 10, through this "Advance 8 cycles" I will end up with 6 new magic numbers, that can be used to jump 8 states ahead in one operation.

You can probably see where this is going...

If you build a table "magic[5][6]" where:

* magic[0][] is what is used to jump ahead one state

* magic[1][] is what is used to jump ahead two states

* magic[2][] is what is used to jump ahead four states

* magic[3][] is what is used to jump ahead eight states

* magic[4][] is what is used to jump ahead sixteen states

You can calculate the value in magic[1][] by using the values in magic[0] twice. You can then calculate the value in magic[2][] by using calculate the value in magic[1][] twice, and so on. (For debugging the values for magic[2][] should be the numbers we already have)

So we now have a way to skip forward any of 1,2,4, 8 or 16 states.

If we want to skip back 10 states because the LFSR has 31 states is the same as skipping forward 21 states. You can use magic[0][], magic[2][] and magic[4][], to jump forward 1, then 4, then 16 states, for a total of 21, but only performing three sets of calculations:


--- Code: ---
So the end code looks something like:

for(index = 0; index < lfsr_bit_length; index++) {
   if((number_to_skip & (1<<index)) != 0) {
          guess = magic[index][0];
          if((state & 0x01) != 0) guess ^= magic[index][1] ^ magic[bit][0];
          if((state & 0x02) != 0) guess ^= magic[index][2] ^ magic[bit][0];
          if((state & 0x04) != 0) guess ^= magic[index][3] ^ magic[bit][0];
          if((state & 0x08) != 0) guess ^= magic[index][4] ^ magic[bit][0];
          if((state & 0x10) != 0) guess ^= magic[index][5] ^ magic[bit][0];
          state = guess;
    }
}

--- End code ---

For a small LFSR like this it doesn't help much, but for a 36 bit FSM it is far quicker that rolling through states.

In BigO notation it changes the runtime from O(2^n) to O(n^2).
Someone:

--- 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.
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