# 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

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:

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:

## lfsr_fibonacci_multi.vhd

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:

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.

Generics |
Total LUTs |
FFs |
Maximum logic level |
---|---|---|---|

output_width = 12 |
8 |
13 |
2 |

output_width = 16 |
10 |
19 |
2 |

## lfsr_fibonacci_single.vhd

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.

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

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