Module lfsr

This document contains technical documentation for the lfsr module. To browse the source code, please visit the repository on GitHub.

This module contains a compact and robust implementation of maximum-length linear feedback shift registers (LFSR) in VHDL. LFSRs are commonly used for pseudo-random number or unique counter generation in FPGA/ASIC applications.

The maximum-length LFSR has the attractive property that it cycles through

\[2^\text{lfsr_length} - 1\]

unique states before repeating. While the order of the states is completely deterministic, the output bit of the LFSR behaves like a random number. These properties are achieved using a very simple structure that is cheap to implement in FPGA:

Example of a Fibonacci LFSR.

The long shift registers are especially cheap in devices that support packing shift registers in LUTs (SRL).

Please see following sources for the mathematical background as well as details about the LFSR properties:

• https://en.wikipedia.org/wiki/Linear-feedback_shift_register

• https://en.wikipedia.org/wiki/Maximum_length_sequence

• https://docs.xilinx.com/v/u/en-US/xapp210

lfsr_fibonacci_multi.vhd

View source code on GitHub.

This entity implements a maximum-length linear feedback shift register (LFSR) with the Fibonacci structure and multiple output bits. See lfsr_fibonacci_single.vhd for a single-bit single-step variant.

This implementation will shift the LFSR state output_width times for each clock cycle, so that consecutive output words will not have a strong inter-sample correlation. The entity will automatically find a suitable LFSR length for the given output width. Since multiple bits of the LFSR state are used as output, this LFSR can in general not be implemented with SRLs, unlike lfsr_fibonacci_single.vhd.

The seed generic can be used to alter the initial state of the LFSR.

Example

Consider a 15-bit maximum-length LFSR, which is defined by the polynomial \(x^{15} + x^{14} + 1\). With a Fibonacci XOR structure, it is implemented like this:

Maximum-length Fibonacci LFSR.

When this LFSR is stepped once, its next state will be

state[15] = state[14]
state[14] = state[13]
state[13] = state[12]
state[12] = state[11]
state[11] = state[10]
state[10] = state[9]
state[9] = state[8]
state[8] = state[7]
state[7] = state[6]
state[6] = state[5]
state[5] = state[4]
state[4] = state[3]
state[3] = state[2]
state[2] = state[1]
state[1] = state[15] XOR state[14]

and the state[15] signal can be used as output. When stepped twice, the next LFSR state will be

state[15] = state[13]
state[14] = state[12]
state[13] = state[11]
state[12] = state[10]
state[11] = state[9]
state[10] = state[8]
state[9] = state[7]
state[8] = state[6]
state[7] = state[5]
state[6] = state[4]
state[5] = state[3]
state[4] = state[2]
state[3] = state[1]
state[2] = state[15] XOR state[14]
state[1] = state[14] XOR state[13]

and the state[15:14] signal can be used as output. When stepped thrice, the next LFSR state will be

state[15] = state[12]
state[14] = state[11]
state[13] = state[10]
state[12] = state[9]
state[11] = state[8]
state[10] = state[7]
state[9] = state[6]
state[8] = state[5]
state[7] = state[4]
state[6] = state[3]
state[5] = state[2]
state[4] = state[1]
state[3] = state[15] XOR state[14]
state[2] = state[14] XOR state[13]
state[1] = state[13] XOR state[12]

and the state[15:13] signal can be used as output. This is want this entity implements, in a generic fashion, by generalizing the shift operations outlined above. For any LFSR length and any step count.

Note that it is possible to use a shift count that is greater than the lowest tap index. This complicates the code, however, and yields more complicated XOR equations. Hence, this entity will always use an LFSR length where the lowest tap index is at least the output_width. In the example above, with a 15-bit LFSR, an output width of up to 14 can be supported.

Resource utilization

This entity has netlist builds set up with automatic size checkers in module_lfsr.py. The following table lists the resource utilization for the entity, depending on generic configuration.

Resource utilization for lfsr_fibonacci_multi netlist builds.

Generics	Total LUTs	FFs	Maximum logic level
output_width = 12	8	13	2
output_width = 16	10	19	2

lfsr_fibonacci_single.vhd

View source code on GitHub.

This entity implements a maximum-length linear feedback shift register (LFSR) with the Fibonacci structure. The LFSR will be shifted one step per cycle, and the output is the last bit of the LFSR. The implementation maps very efficiently to SRLs, which can be seen in the Resource utilization table below.

The seed generic can be used to alter the initial state of the LFSR.

Resource utilization

This entity has netlist builds set up with automatic size checkers in module_lfsr.py. The following table lists the resource utilization for the entity, depending on generic configuration.

Resource utilization for lfsr_fibonacci_single netlist builds.

Generics	Total LUTs	FFs	Maximum logic level
lfsr_length = 52	4	2	2
lfsr_length = 15	2	2	2
lfsr_length = 15 seed = 010101010101010	2	2	2

lfsr_pkg.vhd

View source code on GitHub.

Package with constants/types/functions for the LFSR ecosystem.