Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
18 years ago

LFSR as counter in VHDL

I am running a bit low on gates in a VHDL design, and I am replacing a counter implemented by addition with a counter implemented as an LFSR. The main crystal is 3.6864 MHz and the counter needs to have a period of roughly 0.5 seconds, so I figured that a 20-bit LFSR giving a maximum period of 1048575 (taps 3 and 17) would be close enough.

However, I am pretty new to LFSRs, and I keep getting conflicting explanations about how they work... is bit 20 or bit 1 always considered a tap? Do I use XOR or XNOR? Which direction do I shift? Ordinarily I'd write some C code to test it quickly but I am at work and software is restricted (can't SSH to my server at home either).

I am using the following VHDL code right now, but it never reaches the given combination (so whatever I am doing, it is clearly not a max-length LFSR). Other attempts have given things like a period 1/10 what it should be.

(hb_lfsr is a 20-bit vector; hb_init is a 20-bit constant vector, with all 0s except bit 1 which is 1)

heartbeat_process: process (clk, reset_n, hb_lfsr, heartbeat)

begin

if (reset_n = '0') then

hb_lfsr <= hb_init;

heartbeat <= '0';

elsif (rising_edge(clk)) then

hb_lfsr <= hb_lfsr(19 downto 1) & (hb_lfsr(3) xor hb_lfsr(17));

if(hb_lfsr = hb_init) then

heartbeat <= not(heartbeat);

end if;

end if;

end process;

Can anyone shed some light on this?

9 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    18 years ago

    Why is an LFSR going to save you gates? A counter should use the carry-chain, and probably be the optimal size, i.e if you need 2^20 count, then it should only be 20 logic cells. You really can't store that much information with fewer bits, unless I'm missing something. Is there anything else that has a counter running, because resource sharing might be your best bet.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    18 years ago

    --- Quote Start ---

    Why is an LFSR going to save you gates? A counter should use the carry-chain, and probably be the optimal size, i.e if you need 2^20 count, then it should only be 20 logic cells. You really can't store that much information with fewer bits, unless I'm missing something. Is there anything else that has a counter running, because resource sharing might be your best bet.

    --- Quote End ---

    I'm not disputing that N states will take ceil(log2(N)) bits to store. But I've seen it in many references that LFSRs can be implemented much more cheaply than counters by using one flip-flop per bit and one XOR for each tap.

    In any case, according to the fitter report, the design with an LFSR produces 82% cell usage, and 90% usage for the counter; if I recall, without either present, it's at about 60% usage. It's not huge, but it might make the difference between the design fitting or not once I have added some more things and done pin constraints.

    Ben - Wikipedia is the first reference I looked at, and it's the source of some of my confusion. It says, "The first and last bits are always connected as an input and tap respectively," and it also says that the number of taps must be even for the LFSR to be maximal. Does the last bit count as a tap? If so, how could an LFSR with taps 3,17 be maximal (as a table I'm looking at claims)?

    (Later edit: I added xor bit(20) because it makes sense that I should. Unfortunately this results in a period of about 130, which makes less sense.)
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    18 years ago

    The last bit should always be a tap but I think for a 20 bit lfsr you want taps from from bits 17 & 20 and not from bit (3). I think there is some kind of mirror effect for maximal length taps so you can have either 3 & 20 or 17 & 20, I'm 100% about that last bit though.

    eg

    hb_lfsr <= hb_lfsr(19 downto 1) & (hb_lfsr(17) xor hb_lfsr(20));
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    18 years ago

    Ben - thank you; that either worked properly, or it generated a sequence long enough that it doesn't matter. Perhaps someday I will even understand why.

    You're right about mirror sequences; looks like, for tap sequence [n,A,0] there is a mirror at [n,n-A,0]; I guess n=20, A=3 here.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    18 years ago

    What device are you targeting? My concern is that the books are talking about "number of gates", i.e. an ASIC architecture, in which case they are absolutely correct because the building block is so granular. But an FPGA has pre-done building blocks. For example, if it's a 4-input LUT, and you have a 4-input function, you don't save anything by recoding to make the function 3-inputs or 2-inputs, you still use the whole LUT. I just wanted to make sure you didn't waste time on it to get the same results. (If this is CPLD, then this may be off since I don't think the counter logic is as "dedicated" as in the FPGAs. And Stratix II/III's ALM is adaptive, to get around this inefficiency) It sounds like your number of cells is going down though, so you should be on the right track.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    16 years ago

    Hi,

    It is interesting but I believe it is purely academic.

    In practice, flexible counters are too easy to design. Resource is too small to spare. It may help when using lots of counters but I used memory to implement 120 x 12 bit counters in one occasion to avoid using as many registers.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    16 years ago

    Flexible counters are easy to design and for small counters there is no noticeable advantage in speed and logic size comparing to LFSR counters. I agree, you can use memory to implement larger counters. However, memory output delay might be too large to meet timing.

    Also, it's less portable if your design has to run on different FPGA and ASIC families.

    - Evgeni