Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
Someone:
--- Quote from: hamster_nz on July 05, 2019, 01:55:29 am ---
--- 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.
--- End quote ---
Pipelining a counter is possibly unfeasible? I cannot see it being any more so than pipelining a match circuit. An LFSR that self resets to a loadable length is the oddball hardware design here. Seems like the classic case of pre-emptive optimisation gone wrong, having not seen any comparisons of fleshed out examples from you or the OP.
But do continue on your academic meander, its interesting if entirely missing the practicalities. Trying to suggest a binary counter as synthesised from high level code is somehow esoteric or complex in comparison has made my day.
hamster_nz:
--- Quote from: Someone on July 05, 2019, 04:25:59 am ---But do continue on your academic meander, its interesting if entirely missing the practicalities. Trying to suggest a binary counter as synthesised from high level code is somehow esoteric or complex in comparison has made my day.
--- End quote ---
To show the complexity:
if I were to race you to build either a 16-bit counter on a breadboard out of TTL Quad D-flipflops and two-input logic gates, I bet I could get my LFSR counter up and running quicker, and it would count faster, because it is less complex.
A full adder would need 5 gates per bit, so an adder-based binary counter would need 24 chips (80 for logic gates and and 16 FFs), but a LFSR would only need 5 (1 or two logic gates and 16 FFs). The binary counter might only need half that many logic gates as you can use half-adders... but that is still 14 chips vs 5.
If the OP is working past where a binary counter can meet timing, moving to an LFSR based timer is a workable solution.
LFSRs go from boring to interesting as you learn more about them, as they seem to pop up everywhere:
- Data integrity, such as CRC codes (https://en.wikipedia.org/wiki/Cyclic_redundancy_check)
- Scrambling (as used in PCIe, DisplayPort, SDI, networkng http://en.wikipedia.org/wiki/Scrambler)
- Communication such as GPS (eg.https://en.wikipedia.org/wiki/Direct-sequence_spread_spectrum)
- Forward Error correction (e.g. https://en.wikipedia.org/wiki/BCH_code, as used in HDMI)
- Pseudo-random binary sequences for such things as built in self tests and device characterization
- High speed counters
- Cryptography
Someone:
--- Quote from: hamster_nz on July 05, 2019, 05:29:08 am ---if I were to race you to build either a 16-bit counter on a breadboard out of TTL Quad D-flipflops and two-input logic gates, I bet I could get my LFSR counter up and running quicker, and it would count faster, because it is less complex.
A full adder would need 5 gates per bit, so an adder-based binary counter would need 24 chips (80 for logic gates and and 16 FFs), but a LFSR would only need 5 (1 or two logic gates and 16 FFs). The binary counter might only need half that many logic gates as you can use half-adders... but that is still 14 chips vs 5.
If the OP is working past where a binary counter can meet timing, moving to an LFSR based timer is a workable solution.
LFSRs go from boring to interesting as you learn more about them, as they seem to pop up everywhere:
--- End quote ---
Except the target is an FPGA, not discrete gates, and is programmed in a high level language. I'm fully aware of the wide use of LFSRs and that as a counter they can be power efficient, but that isn't looking at the specific example here of a self resetting loadable counter.
hamster_nz:
Two designs in the same wrapper.
--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
entity binary_counter is
Port ( clk : in STD_LOGIC;
load : in STD_LOGIC;
initial : in STD_LOGIC_VECTOR (35 downto 0);
pulse : out STD_LOGIC);
end binary_counter;
architecture Behavioral of binary_counter is
signal counter : unsigned(initial'length downto 0) := (others => '0');
constant zero : unsigned(0 downto 0) := (others => '0');
begin
process(clk)
begin
if rising_edge(clk) then
pulse <= std_logic(counter(counter'high));
if load = '1' then
counter <= zero & unsigned(initial);
else
counter <= (zero & counter(counter'high-1 downto 0)) + 1;
end if;
end if;
end process;
end Behavioral;
--- End code ---
--- Code: ---library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
entity lfsr_counter is
Port ( clk : in STD_LOGIC;
load : in STD_LOGIC;
initial : in STD_LOGIC_VECTOR (35 downto 0);
pulse : out STD_LOGIC);
end lfsr_counter;
architecture Behavioral of lfsr_counter is
signal state : STD_LOGIC_VECTOR(initial'high downto 0) := (others => '0');
begin
process(clk)
begin
if rising_edge(clk) then
if state = x"000000000" then
pulse <= '1';
else
pulse <= '0';
end if;
if load = '1' then
state <= initial;
else
state <= state(state'high-1 downto 0) & (state(state'high) xor state(5) xor '1');
end if;
end if;
end process;
end Behavioral;
--- End code ---
Although subtly different, both are constrained the same, to the time where both meet the same timing:
--- Code: ---TIMESPEC TS_clk = PERIOD "clk" 3.51 ns HIGH 50%;
--- End code ---
Want to guess which timing is the counter, and which the LFSR?
--- Code: --- Design statistics:
Minimum period: 3.509ns{1} (Maximum frequency: 284.981MHz)
--- End code ---
--- Code: --- Design statistics:
Minimum period: 2.586ns{1} (Maximum frequency: 386.698MHz)
--- End code ---
Someone:
--- Quote from: hamster_nz on July 05, 2019, 08:10:25 am ---Two designs in the same wrapper.
Want to guess which timing is the counter, and which the LFSR?
--- Code: --- Design statistics:
Minimum period: 3.509ns{1} (Maximum frequency: 284.981MHz)
--- End code ---
--- Code: --- Design statistics:
Minimum period: 2.586ns{1} (Maximum frequency: 386.698MHz)
--- End code ---
--- End quote ---
No idea what optimisations you're using in implementation but that binary counter is a full width, when we have repeatedly said it could be divided up or pipelined. If you're not making any effort to improve upon an inferred single cycle counter then its not surprising it implemented slower.
Just to settle this for my own knowledge I threw three versions into a few different devices and consistently had a pipelined counter slower than either an LFSR or partitioned counter. The partitioned counter was consistently the fastest, using a few extra LUTs and control sets compared to the LFSR but fewer flops. But they all surpassed the switching limits of the clock nets, so its past the point of worrying unless you want to get into clocks routed on the general fabric (at which point there are usually better ways to reframe the problem).
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version