LFSR in an FPGA - VHDL & Verilog Code

How a Linear Feedback Shift Register works inside of an FPGA

LFSR stands for Linear Feedback Shift Register and it is a design that is useful inside of FPGAs. LFSRs are simple to synthesize, meaning that they take relatively few resources and can be run at very high clock rates inside of an FPGA. There are many applications that benefit from using an LFSR including:

The linear feedback shift register is implemented as a series of Flip-Flops inside of an FPGA that are wired together as a shift register. Several taps off of the shift register chain are used as inputs to either an XOR or XNOR gate. The output of this gate is then used as feedback to the beginning of the shift register chain, hence the Feedback in LFSR.

5-Bit LFSR using XNOR gates

When an LFSR is running, the pattern that is being generated by the individual Flip-Flops is pseudo-random, meaning that it's close to random. It's not completely random because from any state of the LFSR pattern, you can predict the next state. There are a few properties of shift registers that are important to note:

Longer LFSRs will take longer to run through all iterations. The longest possible number of iterations for an LFSR of N-bits is 2N-1. If you think about it, all possible patterns of something that is N-bits long is 2N. Therefore there is only one pattern that cannot be expressed using an LFSR. That pattern is all 0's when using XOR gates, or all 1's when using XNOR gates as your feedback gate.

The VHDL and Verilog code creates any N-Bit wide LFSR that you desire. It uses polynomials (which is the math behind the LFSR) to create the maximum possible LFSR length for each bit width. Therefore, for 3 bits, it takes 23-1=7 clocks to run through all possible combinations, for 4 bits: 24-1=15, for 5 bits: 25-1=31, etc. I based this on an XNOR implementation to allow the FPGA to start up in an all-zero state on the LFSR. Here is the full table of all LFSR patterns published by Xilinx.


VHDL Implementation:

LFSR.vhd

-------------------------------------------------------------------------------
-- File downloaded from http://www.nandland.com
-------------------------------------------------------------------------------
-- Description:
-- A LFSR or Linear Feedback Shift Register is a quick and easy
-- way to generate pseudo-random data inside of an FPGA.  The LFSR can be used
-- for things like counters, test patterns, scrambling of data, and others.
-- This module creates an LFSR whose width gets set by a generic.  The
-- o_LFSR_Done will pulse once all combinations of the LFSR are complete.  The
-- number of clock cycles that it takes o_LFSR_Done to pulse is equal to
-- 2^g_Num_Bits-1.  For example, setting g_Num_Bits to 5 means that o_LFSR_Done
-- will pulse every 2^5-1 = 31 clock cycles.  o_LFSR_Data will change on each
-- clock cycle that the module is enabled, which can be used if desired.
--
-- Generics:
-- g_Num_Bits - Set to the integer number of bits wide to create your LFSR.
-------------------------------------------------------------------------------

library ieee;
use ieee.std_logic_1164.all;

entity LFSR is
  generic (
    g_Num_Bits : integer := 5
    );
  port (
    i_Clk    : in std_logic;
    i_Enable : in std_logic;

    -- Optional Seed Value
    i_Seed_DV   : in std_logic;
    i_Seed_Data : in std_logic_vector(g_Num_Bits-1 downto 0);
    
    o_LFSR_Data : out std_logic_vector(g_Num_Bits-1 downto 0);
    o_LFSR_Done : out std_logic
    );
end entity LFSR;

architecture RTL of LFSR is

  signal r_LFSR : std_logic_vector(g_Num_Bits downto 1) := (others => '0');
  signal w_XNOR : std_logic;
  
begin

  -- Purpose: Load up LFSR with Seed if Data Valid (DV) pulse is detected.
  -- Othewise just run LFSR when enabled.
  p_LFSR : process (i_Clk) is
  begin
    if rising_edge(i_Clk) then
      if i_Enable = '1' then
        if i_Seed_DV = '1' then
          r_LFSR <= i_Seed_Data;
        else
          r_LFSR <= r_LFSR(r_LFSR'left-1 downto 1) & w_XNOR;
        end if;
      end if;
    end if;
  end process p_LFSR; 

  -- Create Feedback Polynomials.  Based on Application Note:
  -- http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
  g_LFSR_3 : if g_Num_Bits = 3 generate
    w_XNOR <= r_LFSR(3) xnor r_LFSR(2);
  end generate g_LFSR_3;

  g_LFSR_4 : if g_Num_Bits = 4 generate
    w_XNOR <= r_LFSR(4) xnor r_LFSR(3);
  end generate g_LFSR_4;

  g_LFSR_5 : if g_Num_Bits = 5 generate
    w_XNOR <= r_LFSR(5) xnor r_LFSR(3);
  end generate g_LFSR_5;

  g_LFSR_6 : if g_Num_Bits = 6 generate
    w_XNOR <= r_LFSR(6) xnor r_LFSR(5);
  end generate g_LFSR_6;

  g_LFSR_7 : if g_Num_Bits = 7 generate
    w_XNOR <= r_LFSR(7) xnor r_LFSR(6);
  end generate g_LFSR_7;

  g_LFSR_8 : if g_Num_Bits = 8 generate
    w_XNOR <= r_LFSR(8) xnor r_LFSR(6) xnor r_LFSR(5) xnor r_LFSR(4);
  end generate g_LFSR_8;

  g_LFSR_9 : if g_Num_Bits = 9 generate
    w_XNOR <= r_LFSR(9) xnor r_LFSR(5);
  end generate g_LFSR_9;

  g_LFSR_10 : if g_Num_Bits = 10 generate
    w_XNOR <= r_LFSR(10) xnor r_LFSR(7);
  end generate g_LFSR_10;

  g_LFSR_11 : if g_Num_Bits = 11 generate
    w_XNOR <= r_LFSR(11) xnor r_LFSR(9);
  end generate g_LFSR_11;

  g_LFSR_12 : if g_Num_Bits = 12 generate
    w_XNOR <= r_LFSR(12) xnor r_LFSR(6) xnor r_LFSR(4) xnor r_LFSR(1);
  end generate g_LFSR_12;

  g_LFSR_13 : if g_Num_Bits = 13 generate
    w_XNOR <= r_LFSR(13) xnor r_LFSR(4) xnor r_LFSR(3) xnor r_LFSR(1);
  end generate g_LFSR_13;

  g_LFSR_14 : if g_Num_Bits = 14 generate
    w_XNOR <= r_LFSR(14) xnor r_LFSR(5) xnor r_LFSR(3) xnor r_LFSR(1);
  end generate g_LFSR_14;

  g_LFSR_15 : if g_Num_Bits = 15 generate
    w_XNOR <= r_LFSR(15) xnor r_LFSR(14);
  end generate g_LFSR_15;

  g_LFSR_16 : if g_Num_Bits = 16 generate
    w_XNOR <= r_LFSR(16) xnor r_LFSR(15) xnor r_LFSR(13) xnor r_LFSR(4);
  end generate g_LFSR_16;

  g_LFSR_17 : if g_Num_Bits = 17 generate
    w_XNOR <= r_LFSR(17) xnor r_LFSR(14);
  end generate g_LFSR_17;

  g_LFSR_18 : if g_Num_Bits = 18 generate
    w_XNOR <= r_LFSR(18) xnor r_LFSR(11);
  end generate g_LFSR_18;

  g_LFSR_19 : if g_Num_Bits = 19 generate
    w_XNOR <= r_LFSR(19) xnor r_LFSR(6) xnor r_LFSR(2) xnor r_LFSR(1);
  end generate g_LFSR_19;

  g_LFSR_20 : if g_Num_Bits = 20 generate
    w_XNOR <= r_LFSR(20) xnor r_LFSR(17);
  end generate g_LFSR_20;

  g_LFSR_21 : if g_Num_Bits = 21 generate
    w_XNOR <= r_LFSR(21) xnor r_LFSR(19);
  end generate g_LFSR_21;

  g_LFSR_22 : if g_Num_Bits = 22 generate
    w_XNOR <= r_LFSR(22) xnor r_LFSR(21);
  end generate g_LFSR_22;

  g_LFSR_23 : if g_Num_Bits = 23 generate
    w_XNOR <= r_LFSR(23) xnor r_LFSR(18);
  end generate g_LFSR_23;

  g_LFSR_24 : if g_Num_Bits = 24 generate
    w_XNOR <= r_LFSR(24) xnor r_LFSR(23) xnor r_LFSR(22) xnor r_LFSR(17);
  end generate g_LFSR_24;

  g_LFSR_25 : if g_Num_Bits = 25 generate
    w_XNOR <= r_LFSR(25) xnor r_LFSR(22);
  end generate g_LFSR_25;

  g_LFSR_26 : if g_Num_Bits = 26 generate
    w_XNOR <= r_LFSR(26) xnor r_LFSR(6) xnor r_LFSR(2) xnor r_LFSR(1);
  end generate g_LFSR_26;

  g_LFSR_27 : if g_Num_Bits = 27 generate
    w_XNOR <= r_LFSR(27) xnor r_LFSR(5) xnor r_LFSR(2) xnor r_LFSR(1);
  end generate g_LFSR_27;

  g_LFSR_28 : if g_Num_Bits = 28 generate
    w_XNOR <= r_LFSR(28) xnor r_LFSR(25);
  end generate g_LFSR_28;

  g_LFSR_29 : if g_Num_Bits = 29 generate
    w_XNOR <= r_LFSR(29) xnor r_LFSR(27);
  end generate g_LFSR_29;

  g_LFSR_30 : if g_Num_Bits = 30 generate
    w_XNOR <= r_LFSR(30) xnor r_LFSR(6) xnor r_LFSR(4) xnor r_LFSR(1);
  end generate g_LFSR_30;

  g_LFSR_31 : if g_Num_Bits = 31 generate
    w_XNOR <= r_LFSR(31) xnor r_LFSR(28);
  end generate g_LFSR_31;

  g_LFSR_32 : if g_Num_Bits = 32 generate
    w_XNOR <= r_LFSR(32) xnor r_LFSR(22) xnor r_LFSR(2) xnor r_LFSR(1);
  end generate g_LFSR_32;
  
  
  o_LFSR_Data <= r_LFSR(r_LFSR'left downto 1);
  o_LFSR_Done <= '1' when r_LFSR(r_LFSR'left downto 1) = i_Seed_Data else '0';
  
end architecture RTL;

Testbench (LFSR_TB.vhd)

-------------------------------------------------------------------------------
-- File downloaded from http://www.nandland.com
-------------------------------------------------------------------------------
-- Description: Simple Testbench for LFSR.vhd.  Set c_NUM_BITS to different
-- values to verify operation of LFSR
-------------------------------------------------------------------------------
library ieee;
use ieee.std_logic_1164.all;

entity LFSR_TB is
end entity LFSR_TB;

architecture behave of LFSR_TB is

  constant c_NUM_BITS : integer := 5;
  constant c_CLK_PERIOD : time := 40 ns;  -- 25 MHz
  
  signal r_Clk : std_logic := '0';
  signal w_LFSR_Data : std_logic_vector(c_NUM_BITS-1 downto 0);
  signal w_LFSR_Done : std_logic;
  
begin

  r_Clk <= not r_Clk after c_CLK_PERIOD/2;
  
  LFSR_1 : entity work.LFSR
    generic map (
      g_Num_Bits => c_NUM_BITS)
    port map (
      i_Clk       => r_Clk,
      i_Enable    => '1',
      i_Seed_DV   => '0',
      i_Seed_Data => (others => '0'),
      o_LFSR_Data => w_LFSR_Data,
      o_LFSR_Done => w_LFSR_Done
      );
  

end architecture behave;


Verilog Implementation:

LFSR.v

///////////////////////////////////////////////////////////////////////////////
// File downloaded from http://www.nandland.com
///////////////////////////////////////////////////////////////////////////////
// Description: 
// A LFSR or Linear Feedback Shift Register is a quick and easy way to generate
// pseudo-random data inside of an FPGA.  The LFSR can be used for things like
// counters, test patterns, scrambling of data, and others.  This module
// creates an LFSR whose width gets set by a parameter.  The o_LFSR_Done will
// pulse once all combinations of the LFSR are complete.  The number of clock
// cycles that it takes o_LFSR_Done to pulse is equal to 2^g_Num_Bits-1.  For
// example setting g_Num_Bits to 5 means that o_LFSR_Done will pulse every
// 2^5-1 = 31 clock cycles.  o_LFSR_Data will change on each clock cycle that
// the module is enabled, which can be used if desired.
//
// Parameters:
// NUM_BITS - Set to the integer number of bits wide to create your LFSR.
///////////////////////////////////////////////////////////////////////////////
module LFSR #(parameter NUM_BITS)
  (
   input i_Clk,
   input i_Enable,

   // Optional Seed Value
   input i_Seed_DV,
   input [NUM_BITS-1:0] i_Seed_Data,

   output [NUM_BITS-1:0] o_LFSR_Data,
   output o_LFSR_Done
   );

  reg [NUM_BITS:1] r_LFSR = 0;
  reg              r_XNOR;


  // Purpose: Load up LFSR with Seed if Data Valid (DV) pulse is detected.
  // Othewise just run LFSR when enabled.
  always @(posedge i_Clk)
    begin
      if (i_Enable == 1'b1)
        begin
          if (i_Seed_DV == 1'b1)
            r_LFSR <= i_Seed_Data;
          else
            r_LFSR <= {r_LFSR[NUM_BITS-1:1], r_XNOR};
        end
    end

  // Create Feedback Polynomials.  Based on Application Note:
  // http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
  always @(*)
    begin
      case (NUM_BITS)
        3: begin
          r_XNOR = r_LFSR[3] ^~ r_LFSR[2];
        end
        4: begin
          r_XNOR = r_LFSR[4] ^~ r_LFSR[3];
        end
        5: begin
          r_XNOR = r_LFSR[5] ^~ r_LFSR[3];
        end
        6: begin
          r_XNOR = r_LFSR[6] ^~ r_LFSR[5];
        end
        7: begin
          r_XNOR = r_LFSR[7] ^~ r_LFSR[6];
        end
        8: begin
          r_XNOR = r_LFSR[8] ^~ r_LFSR[6] ^~ r_LFSR[5] ^~ r_LFSR[4];
        end
        9: begin
          r_XNOR = r_LFSR[9] ^~ r_LFSR[5];
        end
        10: begin
          r_XNOR = r_LFSR[10] ^~ r_LFSR[7];
        end
        11: begin
          r_XNOR = r_LFSR[11] ^~ r_LFSR[9];
        end
        12: begin
          r_XNOR = r_LFSR[12] ^~ r_LFSR[6] ^~ r_LFSR[4] ^~ r_LFSR[1];
        end
        13: begin
          r_XNOR = r_LFSR[13] ^~ r_LFSR[4] ^~ r_LFSR[3] ^~ r_LFSR[1];
        end
        14: begin
          r_XNOR = r_LFSR[14] ^~ r_LFSR[5] ^~ r_LFSR[3] ^~ r_LFSR[1];
        end
        15: begin
          r_XNOR = r_LFSR[15] ^~ r_LFSR[14];
        end
        16: begin
          r_XNOR = r_LFSR[16] ^~ r_LFSR[15] ^~ r_LFSR[13] ^~ r_LFSR[4];
          end
        17: begin
          r_XNOR = r_LFSR[17] ^~ r_LFSR[14];
        end
        18: begin
          r_XNOR = r_LFSR[18] ^~ r_LFSR[11];
        end
        19: begin
          r_XNOR = r_LFSR[19] ^~ r_LFSR[6] ^~ r_LFSR[2] ^~ r_LFSR[1];
        end
        20: begin
          r_XNOR = r_LFSR[20] ^~ r_LFSR[17];
        end
        21: begin
          r_XNOR = r_LFSR[21] ^~ r_LFSR[19];
        end
        22: begin
          r_XNOR = r_LFSR[22] ^~ r_LFSR[21];
        end
        23: begin
          r_XNOR = r_LFSR[23] ^~ r_LFSR[18];
        end
        24: begin
          r_XNOR = r_LFSR[24] ^~ r_LFSR[23] ^~ r_LFSR[22] ^~ r_LFSR[17];
        end
        25: begin
          r_XNOR = r_LFSR[25] ^~ r_LFSR[22];
        end
        26: begin
          r_XNOR = r_LFSR[26] ^~ r_LFSR[6] ^~ r_LFSR[2] ^~ r_LFSR[1];
        end
        27: begin
          r_XNOR = r_LFSR[27] ^~ r_LFSR[5] ^~ r_LFSR[2] ^~ r_LFSR[1];
        end
        28: begin
          r_XNOR = r_LFSR[28] ^~ r_LFSR[25];
        end
        29: begin
          r_XNOR = r_LFSR[29] ^~ r_LFSR[27];
        end
        30: begin
          r_XNOR = r_LFSR[30] ^~ r_LFSR[6] ^~ r_LFSR[4] ^~ r_LFSR[1];
        end
        31: begin
          r_XNOR = r_LFSR[31] ^~ r_LFSR[28];
        end
        32: begin
          r_XNOR = r_LFSR[32] ^~ r_LFSR[22] ^~ r_LFSR[2] ^~ r_LFSR[1];
        end

      endcase // case (NUM_BITS)
    end // always @ (*)


  assign o_LFSR_Data = r_LFSR[NUM_BITS:1];

  // Conditional Assignment (?)
  assign o_LFSR_Done = (r_LFSR[NUM_BITS:1] == i_Seed_Data) ? 1'b1 : 1'b0;

endmodule // LFSR

Testbench (LFSR_TB.v)

///////////////////////////////////////////////////////////////////////////////
// File downloaded from http://www.nandland.com
///////////////////////////////////////////////////////////////////////////////
// Description: Simple Testbench for LFSR.v.  Set c_NUM_BITS to different
// values to verify operation of LFSR
///////////////////////////////////////////////////////////////////////////////
module LFSR_TB ();

  parameter c_NUM_BITS = 4;
  
  reg r_Clk = 1'b0;
  
  wire [c_NUM_BITS-1:0] w_LFSR_Data;
  wire w_LFSR_Done;
  
  LFSR #(.NUM_BITS(c_NUM_BITS)) LFSR_inst
         (.i_Clk(r_Clk),
          .i_Enable(1'b1),
          .i_Seed_DV(1'b0),
          .i_Seed_Data({c_NUM_BITS{1'b0}}), // Replication
          .o_LFSR_Data(w_LFSR_Data),
          .o_LFSR_Done(w_LFSR_Done)
          );
 
  always @(*)
    #10 r_Clk <= ~r_Clk; 
  
endmodule // LFSR_TB


Help Me Make Great Content!     Support me on Patreon!     Buy a Go Board!