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:
- 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 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
Leave A Comment