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:
- Counters
- Test Pattern Generators
- Data Scrambling
- Cryptography
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:
- LFSR patterns are pseudo-random.
- Output patterns are deterministic. You can figure out the next state by knowing the position of the XOR gates as well as the current pattern.
- A pattern of all 0’s cannot appear when the taps use XOR gates. Since 0 XORed with 0 will always produce 0, the LFSR will stop running.
- A pattern of all 1’s cannot appear when the taps use XNOR gates. Since 1 XNORed with 1 will always produce 1, the LFSR will stop running.
- The maximum possible number of iterations of any LFSR = 2Bits-1
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 isend 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 // LFSRTestbench (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