Diseño Eficiente de LFSR en FPGA con VHDL y Verilog

LFSR en un FPGA – Código VHDL y Verilog

Cómo Funciona un Registro de Desplazamiento con Retroalimentación Lineal dentro de un FPGA

LFSR significa Linear Feedback Shift Register (Registro de Desplazamiento con Retroalimentación Lineal) y es un diseño útil dentro de FPGAs. Los LFSR son simples de sintetizar, consumen pocos recursos y pueden ejecutarse a tasas de reloj muy altas. Hay muchas aplicaciones que se benefician del uso de un LFSR:

• Contadores
• Generadores de Patrones de Prueba
• Scrambling de Datos
• Criptografía

El LFSR se implementa como una serie de Flip-Flops dentro del FPGA cableados como un registro de desplazamiento. Varios "taps" (tomas) de la cadena se usan como entradas a una compuerta XOR o XNOR. La salida de esta compuerta se usa como retroalimentación al inicio de la cadena, de ahí el "Feedback" en LFSR.

LFSR de 5 bits usando compuertas XNOR

Cuando un LFSR funciona, el patrón generado por los Flip-Flops individuales es pseudo-aleatorio, es decir, cercano a aleatorio. No es completamente aleatorio porque desde cualquier estado del patrón LFSR se puede predecir el siguiente. Propiedades importantes:

• Los patrones LFSR son pseudo-aleatorios.
• Los patrones de salida son deterministas. Puede averiguar el siguiente estado conociendo la posición de las compuertas XOR y el patrón actual.
• Un patrón de todos 0's no puede aparecer cuando los taps usan compuertas XOR. Como 0 XOR 0 siempre produce 0, el LFSR se detendría.
• Un patrón de todos 1's no puede aparecer cuando los taps usan compuertas XNOR. Como 1 XNOR 1 siempre produce 1, el LFSR se detendría.
• El máximo número posible de iteraciones de cualquier LFSR = 2^Bits - 1

LFSRs más largos tardan más en recorrer todas las iteraciones. El máximo para N bits es 2^N - 1. Si lo piensa, todos los patrones posibles de N bits es 2^N. Por tanto, solo hay un patrón que no puede expresarse con un LFSR: todos 0's con XOR, o todos 1's con XNOR.

El código VHDL y Verilog crea cualquier LFSR de N bits. Usa polinomios (la matemática detrás del LFSR) para crear la longitud máxima posible para cada ancho de bits. Para 3 bits: 2^3-1=7 ciclos; 4 bits: 15; 5 bits: 31, etc. Está basado en implementación XNOR para permitir que el FPGA inicie en estado todo-ceros. Aquí la tabla completa de patrones LFSR publicada por Xilinx.

Implementación VHDL:

LFSR.vhd

-------------------------------------------------------------------------------
-- File downloaded from https://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(g_Num_Bits downto 1);
        else
          r_LFSR <= r_LFSR(g_Num_Bits-1 downto 1) & w_XNOR;
        end if;
      end if;
    end if;
  end process p_LFSR;

  -- XNOR feedback logic based on g_Num_Bits
  -- Using known maximal length polynomials (XNOR form)
  w_XNOR <= '1' when g_Num_Bits = 1 else
            r_LFSR(1) xnor r_LFSR(2) when g_Num_Bits = 2 else
            r_LFSR(2) xnor r_LFSR(3) when g_Num_Bits = 3 else
            r_LFSR(3) xnor r_LFSR(4) when g_Num_Bits = 4 else
            r_LFSR(3) xnor r_LFSR(5) when g_Num_Bits = 5 else
            r_LFSR(5) xnor r_LFSR(7) when g_Num_Bits = 6 else
            r_LFSR(6) xnor r_LFSR(7) when g_Num_Bits = 7 else
            r_LFSR(4) xnor r_LFSR(5) xnor r_LFSR(6) xnor r_LFSR(8) when g_Num_Bits = 8 else
            r_LFSR(5) xnor r_LFSR(9) when g_Num_Bits = 9 else
            r_LFSR(7) xnor r_LFSR(10) when g_Num_Bits = 10 else
            r_LFSR(9) xnor r_LFSR(11) when g_Num_Bits = 11 else
            r_LFSR(6) xnor r_LFSR(7) xnor r_LFSR(9) xnor r_LFSR(12) when g_Num_Bits = 12 else
            r_LFSR(4) xnor r_LFSR(5) xnor r_LFSR(6) xnor r_LFSR(13) when g_Num_Bits = 13 else
            r_LFSR(5) xnor r_LFSR(7) xnor r_LFSR(9) xnor r_LFSR(14) when g_Num_Bits = 14 else
            r_LFSR(14) xnor r_LFSR(15) when g_Num_Bits = 15 else
            r_LFSR(5) xnor r_LFSR(7) xnor r_LFSR(12) xnor r_LFSR(16) when g_Num_Bits = 16 else
            '0';

  o_LFSR_Data <= r_LFSR(g_Num_Bits downto 1);
  o_LFSR_Done <= '1' when (r_LFSR = (r_LFSR'range => '1')) else '0';
end RTL;

Testbench (LFSR_TB.vhd)

-------------------------------------------------------------------------------
-- File downloaded from https://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_inst : 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;

Implementación Verilog:

LFSR.v

///////////////////////////////////////////////////////////////////////////////
// File downloaded from https://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[NUM_BITS:1];
      else
        r_LFSR <= {r_LFSR[NUM_BITS-1:1], r_XNOR};
    end
  end

  // XNOR feedback logic based on NUM_BITS
  always @(*) begin
    case (NUM_BITS)
      1: r_XNOR = 1'b1;
      2: r_XNOR = r_LFSR[1] ~^ r_LFSR[2];
      3: r_XNOR = r_LFSR[2] ~^ r_LFSR[3];
      4: r_XNOR = r_LFSR[3] ~^ r_LFSR[4];
      5: r_XNOR = r_LFSR[3] ~^ r_LFSR[5];
      6: r_XNOR = r_LFSR[5] ~^ r_LFSR[7];
      7: r_XNOR = r_LFSR[6] ~^ r_LFSR[7];
      8: r_XNOR = r_LFSR[4] ~^ r_LFSR[5] ~^ r_LFSR[6] ~^ r_LFSR[8];
      9: r_XNOR = r_LFSR[5] ~^ r_LFSR[9];
      10: r_XNOR = r_LFSR[7] ~^ r_LFSR[10];
      11: r_XNOR = r_LFSR[9] ~^ r_LFSR[11];
      12: r_XNOR = r_LFSR[6] ~^ r_LFSR[7] ~^ r_LFSR[9] ~^ r_LFSR[12];
      13: r_XNOR = r_LFSR[4] ~^ r_LFSR[5] ~^ r_LFSR[6] ~^ r_LFSR[13];
      14: r_XNOR = r_LFSR[5] ~^ r_LFSR[7] ~^ r_LFSR[9] ~^ r_LFSR[14];
      15: r_XNOR = r_LFSR[14] ~^ r_LFSR[15];
      16: r_XNOR = r_LFSR[5] ~^ r_LFSR[7] ~^ r_LFSR[12] ~^ r_LFSR[16];
      default: r_XNOR = 1'b0;
    endcase
  end

  assign o_LFSR_Data = r_LFSR[NUM_BITS:1];
  assign o_LFSR_Done = (r_LFSR == {NUM_BITS{1'b1}});
endmodule

Testbench (LFSR_TB.v)

///////////////////////////////////////////////////////////////////////////////
// File downloaded from https://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}}),
    .o_LFSR_Data(w_LFSR_Data),
    .o_LFSR_Done(w_LFSR_Done)
  );
  always @(*) #10 r_Clk = ~r_Clk;
endmodule