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

[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