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.
Please post you comments about the experience with the tool, features you’d like to add, and the issues you’ve seen.
References:
- Peter Alfke, Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators,
Xilinx application note Xapp052 - Maria George and Peter Alfke, Linear Feedback Shift Registers in Virtex Devices, Xilinx application note Xapp210
- Xilinx Linear Feedback Shift Register (LFSR) Logic Core
Are you planning to add VHDL support as well
Hi Yulya.
I’ve added VHDL support. Please give it a try and let me know if that’s what you wanted.
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
Hi Yajnesh,
The best source to understand timing and area constraints is Xilinx Constraints Guide document.
Thanks,
Evgeni
Hi Evgeni
thank you very much for your advice
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
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
Hi Cliff,
With the LFSR Counter Gen I can generate a LFSR with loadable input ?
Best regards,
Alex
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?
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
when i click on the .exe, the small black windows disappear immediately. So, what is the problem?
Hi,
It’s a command-line, not GUI application. You need to open it from shell/command line prompt.
Thanks,
Evgeni
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
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
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
Hi Hugh,
Can you tell me what counter value have you been using ?
I’ll take a look.
Thanks,
Evgeni
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
You guys certainly have some kick-as* web apps. Love your CRC generator too. Use them all the time! Thanks a bunch!
Hello, there is a problem about LFSR program generated?
After reset, all bits of lfsr is ZERO?
It will always be ALL ZERO?
Hi,
The LFSR bits are zero when the counter is at reset.
Thanks,
Evgeni
Can you help me how to start the learning process to know the programming in verilog.
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
Great piece! 🙂
I look forward to the next one.
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.
Sir,
Iam doing my project in VLSI.Iam in need of a verilog program for lfsr,can u plz help me?
Sure, what’s your specific question ?
sir, i want a lfsr program in vhdl module plz help me?
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
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
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
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.
hiii
plz send me Vhdl code for bipartite LFSR circuit for 32 bits
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
@Eduard
Hi Eduard,
That value is calculated by the tool running in the background when you generate the code.
Thanks,
Evgeni
@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.
Thanks Joseph, good suggestions.
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.