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