.. _module_lfsr: 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 .. math:: 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: .. figure:: lfsr_fibonacci_13.png 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.lfsr_fibonacci_multi: lfsr_fibonacci_multi.vhd ------------------------ `View source code on GitHub `__. .. symbolator:: component lfsr_fibonacci_multi is generic ( output_width : positive; minimum_lfsr_length : positive; seed : std_ulogic_vector ); port ( clk : in std_ulogic; --# {{}} enable : in std_ulogic; output : out std_ulogic_vector ); end component; This entity implements a maximum-length linear feedback shift register (LFSR) with the Fibonacci structure and multiple output bits. See :ref:`lfsr.lfsr_fibonacci_single` 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 :ref:`lfsr.lfsr_fibonacci_single`. 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 :math:`x^{15} + x^{14} + 1`. With a Fibonacci XOR structure, it is implemented like this: .. figure:: lfsr_fibonacci_15.png Maximum-length Fibonacci LFSR. When this LFSR is stepped once, its next state will be .. code:: none 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 .. code:: none 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 .. code:: none 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. .. _lfsr.lfsr_fibonacci_multi.resource_utilization: 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. .. list-table:: Resource utilization for **lfsr_fibonacci_multi** netlist builds. :header-rows: 1 * - Generics - Total LUTs - FFs - Maximum logic level * - output_width = 12 - 8 - 13 - 2 * - output_width = 16 - 10 - 19 - 2 .. _lfsr.lfsr_fibonacci_single: lfsr_fibonacci_single.vhd ------------------------- `View source code on GitHub `__. .. symbolator:: component lfsr_fibonacci_single is generic ( lfsr_length : positive range non_zero_tap_table'range; seed : std_ulogic_vector ); port ( clk : in std_ulogic; --# {{}} enable : in std_ulogic; output : out std_ulogic ); end component; 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 :ref:`lfsr.lfsr_fibonacci_single.resource_utilization` table below. The ``seed`` generic can be used to alter the initial state of the LFSR. .. _lfsr.lfsr_fibonacci_single.resource_utilization: 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. .. list-table:: Resource utilization for **lfsr_fibonacci_single** netlist builds. :header-rows: 1 * - 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.lfsr_pkg: lfsr_pkg.vhd ------------ `View source code on GitHub `__. Package with constants/types/functions for the LFSR ecosystem.