Home > Logic Design > LFSR Counters

LFSR Counters


  Most of the EE or CS graduates know or at least have heard about different types of hardware counters: prescaled, Johnson, ripple carry, linear feedback shift register (LFSR), and others.
The majority of logic designers use the first two types, because they’re simple to implement in Verilog or VHDL. However, for some applications LFSR counters offer a significant advantage in terms of logic utilization and maximum frequency.
The other day I run into Xilinx LFSR Counter core and decided to explore its advantages. I was so impressed with its area saving comparing with regular counters that I decided to write an online tool that generates a Verilog code for an LFSR counter of an arbitrary value.
This LFSR Counter Generator tool is running on the server. The time it takes to generate the code depends exponentially on the counter size. It takes several seconds to generate a 20-bit counter. But bigger counters cause the server to timeout with the current tool implementation.
I’m planning to tweak the implementation to be able to generate counters up to ~30 bits. More than that would take too long no matter what approach is taken.

The Art of Error Correcting Coding

Please post you comments about the experience with the tool, features you’d like to add, and the issues you’ve seen.


References:

  1. Peter Alfke, Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators,
    Xilinx application note  Xapp052
  2. Maria George and Peter Alfke, Linear Feedback Shift Registers in Virtex Devices, Xilinx application note  Xapp210
  3. Xilinx Linear Feedback Shift Register (LFSR) Logic Core


  1. Yulya
    May 6th, 2009 at 18:21 | #1

    Are you planning to add VHDL support as well

  2. May 6th, 2009 at 19:23 | #2

    Hi Yulya.
    I’ve added VHDL support. Please give it a try and let me know if that’s what you wanted.

  3. June 29th, 2009 at 02:51 | #3

    Hi
    i am a engineering student who likes verilog and vhdl coding a much….. i have one international papers published….. Now i need to know how to give constraints to a verilog model ….. i need both area and timing constraints…. i am using xylinx sparten 2 xst200 pq208..

    thank’s and regards
    yajnesh padiyar

  4. June 29th, 2009 at 13:36 | #4

    Hi Yajnesh,

    The best source to understand timing and area constraints is Xilinx Constraints Guide document.

    Thanks,
    Evgeni

  5. July 5th, 2009 at 22:49 | #5

    Hi Evgeni
    thank you very much for your advice

  6. Cliff Lin
    February 3rd, 2010 at 18:28 | #6

    Evgeni,

    I like it very much. Good stuff.
    Now, we can have only one count #. Can you generate lfsr_done for each count # ?
    Let’s say I want to have output of count = 8, 16 and 64.
    If the code can generate, lfsr_done0 (count =8), lfsr_done1 (count =16) and lfsr_done2(count =64), that would be very helpful. Of course, count numbers would be user defined.

    //Cliff

  7. February 3rd, 2010 at 21:43 | #7

    Hi Cliff,

    Because an LFSR counter is using a pseudo-random sequence to count, it wouldn’t be possible to “embed” multiple count values in one.
    A potential solution would be to chain multiple counters, so that lfsr_done triggers the next one up in the chain.

    In your case you might chain three counters – 8,8, and 48 – to achieve counting 8, 16, and 64.
    But for small counters the advantage of LFSR over a regular counter in terms of space is less significant.

    Thanks,
    Evgeni

  8. Alex
    April 23rd, 2010 at 01:34 | #8

    Hi Cliff,

    With the LFSR Counter Gen I can generate a LFSR with loadable input ?

    Best regards,
    Alex

  9. policeman
    May 5th, 2010 at 06:27 | #9

    hi, the LFSR counter generator that i downloaded can’t be install, can i know what is the problem and can tell me the way to install?

  10. May 5th, 2010 at 13:09 | #10

    Hi,

    It doesn’t require any installation – it’s just an executable. Do you have any error message? Can you try compiling the program yourself and run it?

    Thanks,
    Evgeni

  11. policeman
    May 6th, 2010 at 01:24 | #11

    when i click on the .exe, the small black windows disappear immediately. So, what is the problem?

  12. May 6th, 2010 at 11:57 | #12

    Hi,

    It’s a command-line, not GUI application. You need to open it from shell/command line prompt.

    Thanks,
    Evgeni

  13. policeman
    May 12th, 2010 at 23:02 | #13

    Hi,
    assign lfsr_equal = (lfsr == 14’h2000)
    Is it the lfsr value can be any number?
    What will happen if the lfsr is not 14’h2000, for exp: lfsr == 14h’600?

    Best regards,
    Policeman

  14. May 12th, 2010 at 23:56 | #14

    Hi,

    No, a generic LFSR cannot reach any value. Only those LFSRs with so called “maximum length” property can. The LFSRs I use to generate counters do have this property.

    LFSR sequence is pseudo-random. So (lfsr == 14′h2000) doesn’t mean that the next value is h2001 or h1FFF. The same goes with 14h’600. What is guaranteed is that each value LFSR visits is unique, but not the sequence.

    Thanks,
    Evgeni

  15. May 11th, 2011 at 11:06 | #15

    Hi Evgeni,

    I tried the LFSR counter generator. The verilog/VHDL file it genereted has the LFSR initialized to 0 and reloaded with 0 when lfsr_equal going high. The original code does not run because of the 0 value of the LSFR.
    Are you planning to change the initial value to none-zero value?
    Thank you.

    Hugh

  16. May 11th, 2011 at 11:08 | #16

    Hi Hugh,

    Can you tell me what counter value have you been using ?
    I’ll take a look.

    Thanks,
    Evgeni

  17. May 11th, 2011 at 11:15 | #17

    Hi Evgeni,

    Sorry for the last question.
    I made a mistake in my sim and it caused problem.
    Please ignore my previous email.
    The LFSR counter works perfectly.
    Thank you.

    Hugh

  18. June 18th, 2011 at 07:48 | #18

    You guys certainly have some kick-as* web apps. Love your CRC generator too. Use them all the time! Thanks a bunch!

  19. Hi
    July 3rd, 2011 at 13:59 | #19

    Hello, there is a problem about LFSR program generated?
    After reset, all bits of lfsr is ZERO?
    It will always be ALL ZERO?

  20. July 3rd, 2011 at 15:03 | #20

    Hi,

    The LFSR bits are zero when the counter is at reset.

    Thanks,
    Evgeni

  21. Sunil
    August 18th, 2011 at 23:16 | #21

    Can you help me how to start the learning process to know the programming in verilog.

  22. August 19th, 2011 at 04:11 | #22

    That depends on your background. In my opinion, it’s more important to know the principles of digital design. Verilog is just a language that describes digital circuit.

    Thanks,
    Evgeni

  23. August 30th, 2011 at 01:03 | #23

    Great piece! 🙂

    I look forward to the next one.

  24. rajesh
    December 6th, 2011 at 09:02 | #24

    sir ,i have a project of vhdl ”Power Optimization of Linear feedback shift register using Low Power BIST” so i am looking for vhdl codes of LFSR without BIST and LFSR with BIST please help me to get these codes.

  25. saas
    December 8th, 2011 at 00:32 | #25

    Sir,
    Iam doing my project in VLSI.Iam in need of a verilog program for lfsr,can u plz help me?

  26. December 8th, 2011 at 03:00 | #26

    Sure, what’s your specific question ?

  27. roja
    December 18th, 2011 at 02:36 | #27

    sir, i want a lfsr program in vhdl module plz help me?

  28. January 23rd, 2012 at 02:27 | #28

    sir,
    i want to write a vhdl code for counting bloom filter , in that
    one of the basic block is up/down LFSR;
    AM TRYING 1ST WITH 3 BIT LFSR USING BEHAVIORAL
    PROBLEM GETTING IN GENERATING THE SEQUENCE I NEED, PLZ
    GIVE ME THE CODE FOR 3 BIT LFSR USING X NOR GATES

    THANKING YOU SIR;
    FROM
    MALLIKA
    PURSUING MASTERS DEGREE

  29. January 23rd, 2012 at 08:23 | #29

    Hi Mallika,

    LFSR counter generation tool doesn’t generate 3-bit counters using LFSR approach. But you can take a look at this paper to understand how to generate a 3-bit LFSR. It’s basically putting a feedback XNOR gate connected to 2’nd and 3’rd taps.

    Thanks,
    Evgeni

  30. February 5th, 2012 at 05:49 | #30

    Hi,
    i am very much interested in LFSR Counter Generator but i am quite new to this field.so can you please tell me or suggest me some source where i can acquire some information and then start working in this field.

    Thanks and Regards,

    Gaurav

  31. shweta
    October 5th, 2012 at 03:34 | #31

    hello sir,
    i need some help.i am implementing a system on fpga which requires code for 3 bit linear feedback shift register and pseudo random binary sequence detector.
    could u please provide me the required.
    hoping for ur great help, soon.
    bye.

  32. fatima
    March 26th, 2014 at 09:55 | #32

    hiii
    plz send me Vhdl code for bipartite LFSR circuit for 32 bits

  33. Eduard
    January 8th, 2015 at 07:10 | #33

    hi Evgeni

    your LFSR counter generation tool is a very interessting thing.

    What i would like to now is: how do you calculate the value, when lfsr_equal is set to 1 ?

    Code example:
    process(lfsr) begin
    if(lfsr = x”8″) then {I MEAN THE VALUE x”8″}
    lfsr_equal <= '1';
    else
    lfsr_equal <= '0';
    end if;
    end process;

    i hope you can answer my question as soon as possible.

    Kind regards
    Eduard

  34. January 8th, 2015 at 08:38 | #34

    @Eduard
    Hi Eduard,

    That value is calculated by the tool running in the background when you generate the code.

    Thanks,
    Evgeni

  35. Joseph Whitehead
    March 4th, 2016 at 16:18 | #35

    @Evgeni
    Well, a few thoughts here:

    A) You can make something like a NAND gate (think of how address decoders work) setup where only a certain pattern of 1’s and 0’s will trigger it. This would then pause the currently used counter and start the next one (or reconfigure the taps to get same effect). Chain 3+ LFSR’s and you can get different ‘pairs’ of consecutive numbers, depending on which counter is currently active. This obviously has limited applications, at least by itself.

    B) You can combine the outputs of counters with different lengths using XOR (for example). If counter A has a period of 2, and counter B has a period of 3, then there’s 6 unique possible states. This idea leads to part C… hidden states.

    C) You can make a counter with a second set of states (besides the ‘taps’ or output number in other words). This would be used to change the behavior so that there’s effectively hidden states, that reconfigure say, a NAND to an AND, or an XOR to an X-NOR, or invert single inputs of NAND gates (same as how NOR/NAND/OR/AND can be equivalent with inverted inputs and outputs). This method does not suffer from any change in timing (in theory!) since the gates take roughly the same time rather a given input is 0 or 1.

    The goal being to still be pretty basic logic, that runs with low latency, while providing less trivial sequences. An insane implementation (lots of bits needed to store the states) that is pretty ‘random’ has the name Mersenne Twister. See the Wikipedia article for references and notes on advantages/disadvantages.

  36. March 4th, 2016 at 16:29 | #36

    Thanks Joseph, good suggestions.

  37. Umang Rastogi
    October 6th, 2017 at 23:45 | #37

    I tried running your Verilog code, for a data of 8-bit using CRC-5 used in USB 2.0, on my Xilinx ISE Design Suite 14.5 but the synthesize-process fails every time. Please help me out asap.

  1. No trackbacks yet.