New Generator: Linear-Feedback Shift Registers

Building on our vision to offer a comprehensive, web-based code generator for FPGA and ASIC developers, we are thrilled to announce the initial rollout of our Linear-Feedback Shift Register (LFSR) generator.

LFSRs are a class of pseudo-random number generators that can be implemented very efficiently in FPGA or ASIC technologies. As you can see in the figure below, a 7-bit LFSR is just a chain of 7 register stages with two XNOR feedback taps at positions 6 and 7. When initialized to zero, and provided with a clock signal, this marvelous little circuit will almost magically cycle through every possible state (except one) of the 7-bit word in a defined sequence that repeats itself every 127 cycles.

LFSRs have a single invalid state which—like a beetle stuck on its back—they cannot exit on their own. For XNOR feedback types LFSRs, the invalid state is all ones. Fortunately, the invalid word is not part of the LFSR’s natural sequence whose length is thus 2^N-1 instead of 2^N, N being the LFSR length in bits.

In digital electronics, LFSRs are often used to generate Pseudorandom Binary Sequences (PRBS) for testing serial or parallel communication links. PRBS-7 and PRBS-31 are two common kinds of Pseudorandom Binary Sequences, which can be generated respectively with 7-bit and 31-bit LFSRs. In the case of a serial communication link, the bit sequence is obtained from the MSB of the shift register (e.g. Q7 in the diagram above).

Implementing LFSRs in hardware is no rocket science. Still, since it’s not something that developers do every day, it can easily take an hour or two until the proper feedback taps and feedback type have been figured out and the circuit is finally working in simulation and in synthesis.

Using the new LFSR generator in airhdl, you can now design an LFSR in minutes and immediately download the VHDL or SystemVerilog implementation.

For your convenience, airhdl also provides C and Python models of the LFSR so that you can easily display the sequence of numbers that the LFSR will cycle through. This can be super convenient when it comes to comparing numbers recorded with a logic analyzer with the expected sequence.

By default, the Python model outputs the first 16 words of the LFSR sequence in hexadecimal format:

$ python .\prbs7_lfsr.py
00
01
03
07
0F
1F
3F
7E
7D
7B
77
6F
5F
3E
7C
79

Using the optional count argument, you can tell the script how many output words to generate:

$ python .\prbs7_lfsr.py 4
00
01
03
07

The -i option allows you to start the sequence on an arbitrary initial value:

$ python .\prbs7_lfsr.py -i 0x3F 8
3F
7E
7D
7B
77
6F
5F
3E

This way you can easily convince yourself that it’s a very bad idea to initialize the LFSR to all ones (that’s the beetle stuck on its back):

$ python .\prbs7_lfsr.py -i 0x7F 8
7F
7F
7F
7F
7F
7F
7F
7F

We hope you’ll find the new LFSR generator useful and as always, make sure to let us know what you think!

Update (30-AUG-2023): Philip Abbey has generic VHDL implementation of LFSRs, which is described on his blog: Swapping Synchronous and LFSR Counters