Up/down counter with LFSR technique ?
S. Dubach
maybe this has been discussed before:
We have troubles getting a 24 bit (synchronous) counter running at 30MHz
with ordinary coding.
Target technology is an FPGA from Lucent.
I know you can get a faster and smaller result for an one direction
counter in LFSR technique.
But is this also possible for an up/down counter or do I miss another
form of realisation.
Any hints, ideas and links to examples are very appreciated.
sdubach"at"hta"dot"fhz"dot"ch
S. Dubach
S. Dubach
Michael Vincze
S. Dubach wrote in message <7s9v0n$osh$1...@pollux.ip-plus.net>...
Depending upon your synthesis tool, or the settings you
have for the tool, it may not be able to translate your counter
into the most efficient circuitry. In this case you may have
to infer (sic) a more optimal counter, for the FPGA.
A common technique for this is to break up
your 24 bit counter into two 12 bit counters.
When the lower 12 bits reach their terminal
count (X"fff"), then increment the upper 12 bit
counter. You would perform a similar act
when down counting.
Good luck.
Best regards,
Michael Vincze
Stuart Clubb
(4-bits per PFU) and running in a 2C04A-2 gave me 42 MHz.
Cheers
Stuart
On Wed, 22 Sep 1999 09:03:51 +0200, "S. Dubach"
<sdu...@hta.fhz\"dot\"ch> wrote:
>Hi,
>maybe this has been discussed before:
>We have troubles getting a 24 bit (synchronous) counter running at 30MHz
>with ordinary coding.
>Target technology is an FPGA from Lucent.
>I know you can get a faster and smaller result for an one direction
>counter in LFSR technique.
>But is this also possible for an up/down counter or do I miss another
>form of realisation.
>
>
>Any hints, ideas and links to examples are very appreciated.
>
>sdubach"at"hta"dot"fhz"dot"ch
For Email remove "NOSPAM" from the address
jhir...@yahoo.com
"S. Dubach" <sdu...@hta.fhz\"dot\"ch> wrote:
> Hi,
> maybe this has been discussed before:
> We have troubles getting a 24 bit (synchronous) counter running at
30MHz
> with ordinary coding.
> Target technology is an FPGA from Lucent.
> I know you can get a faster and smaller result for an one direction
> counter in LFSR technique.
> But is this also possible for an up/down counter or do I miss another
> form of realisation.
>
> Any hints, ideas and links to examples are very appreciated.
>
One thing you can try is have one polynomial for the up direction and
another (highly dependant on the first) for the down direction; the
up/down signal would switch between the two every clock cycle (if
needed). This should synthesize efficiently; finding two polynomials
with the above restriction shouldn't be that hard.
Jacob Hirbawi.
Sent via Deja.com http://www.deja.com/
Before you buy.
David McNally
To get an up-down lfsr counter I think you need a shift register capable
of shifting in both directions plus the polynomial tap tree (for up) and
its mirror image (for down). Caveat: I haven't tried building one.
Synopsys have a nice (code encrypted) example in their DesignWare
Foundation Library, "DW03_lfsr_updn - LFSR Up/Down Counter". If you're
using Synopsys, just plug and play.
Regards,
David
--
- David McNally, Philips Semiconductors, CS-DM Southampton, SO15 0DJ, UK
- mailto:david....@soton.sc.philips.com seri:mcnally@ukpsshp1
- phone: +44 (0)1703 702 701 x6272 fax: +44 (0)1703 316 303
Richard Guerin
the desired tap and it's mirror image.
David McNally
I had a brief interest in lfsrs a couple of years ago after reading
Peter Alfke's application note on the Xilinx web site. The maximal
length sequence class lfsrs (m-sequence lfsrs) have a few caveats that I
couldn't see how to work around:
[1] The sequence is only [(2**n) - 1] long. The missing state is a
lockup state: all zeros for the xor form; all ones for the xnor form. I
couldn't work out how you'd then use the counter for things like a DRAM
refresh counter - anyone?
[2] The lockup state means you need a means of presetting the counter.
[3] Decoding a particular count is a bit painful. You have to run the
generator to find the state you're interested in and you may have to
decode the full counter width. This is likely to result in a tree with
greater depth than the tap tree and therefore be the counter's critical
path.
I'd be interested in anyone's ideas on the above.
The attachment shows an example I built last night. Seems to work over
the count of 100 - as always, no guarantee or warranty.
Richard Guerin
maximum length LFSR counter with 2^n states (instead of 2^n -1) and no
lockup state .... send $$$$ for RTL code ;-)
> ------------------------------------------------------------------------
>
> --
> -- References:
> --
> -- [1] Peter Alfke, "Efficient Shift Registers, LFSR Counters, and Long
> -- Pseudo-Random Sequence Generators", Xilinx Application Note: XAPP
> -- 052 July 7,1996 (Version 1.1), Table 3: "Taps for Maximum-Length
> -- LFSR Counters", p.5
> --
>
> LIBRARY ieee;
> USE ieee.std_logic_1164.ALL;
>
> ENTITY lfsr_updn_24 IS
> PORT (
> clk : IN std_logic;
> clr : IN std_logic;
> dn : IN std_logic;
> q : OUT std_logic_vector(24 DOWNTO 1)
> );
> END lfsr_updn_24;
>
> ARCHITECTURE rtl OF lfsr_updn_24 IS
> SIGNAL i_q : std_logic_vector(24 DOWNTO 1);
> BEGIN
> counter_reg: PROCESS
> VARIABLE feedback_up : std_logic;
> VARIABLE feedback_dn : std_logic;
> BEGIN
> WAIT UNTIL (clk'EVENT AND clk = '1');
> --
> -- feedback_up => xnor polynomial taps to generate the lfsr lsb
> -- when the counter is counting up/shifting left. The taps are
> -- from [1].
> --
> feedback_up := NOT(i_q(24) XOR i_q(23) XOR i_q(22) XOR i_q(17));
> --
> -- feedback_dn => xnor polynomial taps to (re)generate the lfsr
> -- msb when the counter is counting down/shifting right. The
> -- taps are calculated using the formula:
> --
> -- feedback_dn_tap := (feedback_up_tap mod counter_width) + 1
> --
> feedback_dn := NOT(i_q(1) XOR i_q(24) XOR i_q(23) XOR i_q(18));
> IF (clr = '1') THEN
> -- clear to non lockup state
> i_q <= (OTHERS => '0');
> ELSIF (dn = '0') THEN
> -- count up
> i_q <= i_q(23 DOWNTO 1) & feedback_up;
> ELSE
> -- count down
> i_q <= feedback_dn & i_q(24 DOWNTO 2);
> END IF;
> END PROCESS counter_reg;
> q <= i_q;
> END rtl;
>
> -- synopsys synthesis_off
> CONFIGURATION lfsr_updn_24_conf OF lfsr_updn_24 IS
> FOR rtl
> END FOR;
> END lfsr_updn_24_conf;
> -- synopsys synthesis_on
>
> ------------------------------------------------------------------------
>
> LIBRARY ieee;
> USE ieee.std_logic_1164.ALL;
>
> ENTITY lfsr_updn_24_tb1 IS
> END lfsr_updn_24_tb1;
>
> ARCHITECTURE testbench OF lfsr_updn_24_tb1 IS
>
> SIGNAL stop_sim : boolean := false;
>
> SIGNAL clk : std_logic := '0';
> SIGNAL clr : std_logic := '1';
> SIGNAL dn : std_logic := '0';
> SIGNAL q : std_logic_vector(24 DOWNTO 1);
>
> COMPONENT lfsr_updn_24
> PORT (
> clk : IN std_logic;
> clr : IN std_logic;
> dn : IN std_logic;
> q : OUT std_logic_vector(24 DOWNTO 1)
> );
> END COMPONENT; -- lfsr_updn_24
>
> BEGIN
>
> clk_driver: PROCESS
> BEGIN
> WHILE (NOT stop_sim) LOOP
> WAIT FOR 50 ns;
> clk <= NOT clk;
> END LOOP;
> WAIT;
> END PROCESS clk_driver;
>
> main: PROCESS
> BEGIN
> -- test clear
> clr <= '1';
> FOR i IN 1 TO 5 LOOP
> WAIT UNTIL (clk = '0');
> END LOOP;
> clr <= '0';
> -- test count up
> dn <= '0';
> FOR i IN 1 TO 100 LOOP
> WAIT UNTIL (clk = '0');
> END LOOP;
> -- test count down
> dn <= '1';
> FOR i IN 1 TO 100 LOOP
> WAIT UNTIL (clk = '0');
> END LOOP;
> -- retest count up
> dn <= '0';
> FOR i IN 1 TO 100 LOOP
> WAIT UNTIL (clk = '0');
> END LOOP;
> stop_sim <= true;
> ASSERT (false)
> REPORT "simulation complete"
> SEVERITY failure;
> WAIT;
> END PROCESS main;
>
> lfsr_updn_24_i0: lfsr_updn_24
> PORT MAP (
> clk => clk,
> clr => clr,
> dn => dn,
> q => q
> ); -- lfsr_updn_24_i0: lfsr_updn_24
>
> END testbench;
>
> CONFIGURATION lfsr_updn_24_tb1_conf OF lfsr_updn_24_tb1 IS
> FOR testbench
> FOR ALL: lfsr_updn_24
> USE CONFIGURATION work.lfsr_updn_24_conf;
> END FOR;
> END FOR;
> END lfsr_updn_24_tb1_conf;
Allan Herriman
<david....@soton.sc.philips.com> wrote:
>S.Dubach,
>
>I had a brief interest in lfsrs a couple of years ago after reading
>Peter Alfke's application note on the Xilinx web site. The maximal
>length sequence class lfsrs (m-sequence lfsrs) have a few caveats that I
>couldn't see how to work around:
>
>[1] The sequence is only [(2**n) - 1] long. The missing state is a
>lockup state: all zeros for the xor form; all ones for the xnor form. I
>couldn't work out how you'd then use the counter for things like a DRAM
>refresh counter - anyone?
The Xilinx application note (Xapp052) you quoted says how to convert a
2^N - 1 LFSR into a 2^N "LFSR". (Actually the feedback is now
non-linear, so I guess it's a NLFSR.)
The feedback is inverted when N-1 of the flip flops are all 1. You
need a wide and gate for this.
>[2] The lockup state means you need a means of presetting the counter.
You don't get a lockup state with the modified counter.
>[3] Decoding a particular count is a bit painful. You have to run the
>generator to find the state you're interested in and you may have to
>decode the full counter width. This is likely to result in a tree with
>greater depth than the tap tree and therefore be the counter's critical
>path.
>
>I'd be interested in anyone's ideas on the above.
I've found that LFSRs that have been modified to have 2^N states
aren't any more efficient than binary counters in FPGA architectures
because the built-in carry chains make the binary counters quite
efficient.
There may be many "counter"-examples though. (sorry about the pun!)
Allan.
>The attachment shows an example I built last night. Seems to work over
>the count of 100 - as always, no guarantee or warranty.
>
>Regards,
>
>David
>
>--
>- David McNally, Philips Semiconductors, CS-DM Southampton, SO15 0DJ, UK
>- mailto:david....@soton.sc.philips.com seri:mcnally@ukpsshp1
>- phone: +44 (0)1703 702 701 x6272 fax: +44 (0)1703 316 303
>
>--------------A3B27AF115
>Content-Type: text/plain; charset=us-ascii; name="lfsr_updn_24.vhdl"
>Content-Transfer-Encoding: 7bit
>Content-Disposition: inline; filename="lfsr_updn_24.vhdl"
>--------------A3B27AF115
>Content-Type: text/plain; charset=us-ascii; name="lfsr_updn_24_tb1.vhdl"
>Content-Transfer-Encoding: 7bit
>Content-Disposition: inline; filename="lfsr_updn_24_tb1.vhdl"
>--------------A3B27AF115--
>
Jonathan Bromley
>
> With a little imagination and resourcefulness it is possible to design a
> maximum length LFSR counter with 2^n states (instead of 2^n -1) and no
> lockup state
Yes. Do these tweaked LFSRs have the same statistical properties
though? (I don't know, the maths is too hard for me - just asking)
> .... send $$$$ for RTL code ;-)
tsk, tsk, I thought we were all friends here :-)
Jonathan Bromley
Kevin Jennings
opposite direction (i.e. if your LFSR normally shifts towards the right then
just shift it towards the left). That may be a bit of a ballsy general
statement but it seemed like it should work so I tried it for the particular
LFSR that I was using and it did work so I went with it.
Since normally a particular bit in an LFSR is connected to it's nearest
neighboring bit, an up/down version of an LFSR as I described would need to
connect to it's neighboring bit on both sides which isn't so terrible. That
way you don't have to try to find a 'mirror image' tap tree (is there really
such a thing?).
To get 2^n states on an 'up' LFSR counter you simply need something like...
if reset then
LFSR = "0000...0"
else
if LFSR = "0000...0"
LFSR = "0000...1"
else
LFSR = tap tree xor LFSR...
end if
end if;
On reset you go to the all zeros (normally bad for an LFSR) state; if you're
in the all zeros state than you go to any of the other 2^n-1 states that are
OK for an LFSR otherwise do the normal LFSR xor'ing.
Decoding the all zeros state obviously requires access to all the bits in an
LFSR like a normal binary counter would which in some applications would
probably defeat the whole point of using an LFSR over a binary counter. If
you can spare the extra prop delay you could implement the all zeros state
detector once then distribute just that one signal to each bit in the LFSR
which wouldn't seem to be too much overhead.
me...@mench.com
wrote in article <37F420B8...@IEEE.org>:
> With a little imagination and resourcefulness it is possible to
> design a maximum length LFSR counter with 2^n states (instead of 2^n
> -1) and no lockup state .... send $$$$ for RTL code ;-)
Ok, here's my $$$$:
$$$$
Now, where's the code?
P
--
Paul Menchini | me...@mench.com |"The last thing I want to do is
Cadence Design Systems | www.orcad.com | spread fear, uncertainty and
P.O. Box 71767 | 919-479-1670[v] | doubt in the users' minds."
Durham, NC 27722-1767 | 919-479-1671[f] | --Don Jones, MS's Y2K Product Mgr
Richard Guerin
> Ok, here's my $$$$:
>
> $$$$
>
> Now, where's the code?
Hmmm ... you know, $$$$ just doesn't go as far as it used to
... tell you what I'm gonna do ... here's the special of the week:
A handy-dandy 4 bit LFSR with no lockup state. Knock yourselves out ;-)
library ieee;
use ieee.std_logic_1164.all;
entity LFSR4 is
port ( RST_N, CLK : in std_logic;
COUNT : buffer std_logic_vector(0 to 3));
end LFSR4;
architecture RTL of LFSR4 is
constant ZERO : std_logic_vector(0 to 2) := (others => '0');
signal NOR3 : std_logic;
begin
NOR3 <= '1' when (COUNT(0 to 2) = ZERO) else '0';
SHIFT : process ( RST_N, CLK ) is
begin
if (RST_N = '0') then
-- Hey ^%$^%$@#^% you're not supposed
-- to do this in an xor based LFSR !!!!!
COUNT <= (others => '0');
elsif ( CLK'event and CLK = '1') then
-- Oh that's the trick ... cool, dude ;-)
COUNT <= ((COUNT(0) xor COUNT(3)) xor NOR3) & COUNT(0 to 2);
end if;
end process;
end RTL;
John Janusson
thread)
Richard Guerin wrote in message <37F5707B...@IEEE.org>...