Effizientes LFSR-Design im FPGA mit VHDL & Verilog

LFSR im FPGA – VHDL & Verilog Code

Funktionsweise eines Linear Feedback Shift Register im FPGA

LFSR steht für Linear Feedback Shift Register – ein Design, das sich im FPGA als nützlich erweist. LFSR lassen sich einfach synthetisieren, benötigen also relativ wenige Ressourcen und können im FPGA mit sehr hohen Taktraten betrieben werden. Viele Anwendungen profitieren vom Einsatz eines LFSR:

• Zähler
• Testmuster-Generatoren
• Data Scrambling
• Kryptografie

Das Linear Feedback Shift Register wird im FPGA als Reihe von Flip-Flops implementiert, die als Schieberegister verschaltet sind. Mehrere Abgriffe (Taps) der Schieberegisterkette dienen als Eingänge für ein XOR- oder XNOR-Gatter. Der Ausgang dieses Gatters wird als Feedback an den Anfang der Schieberegisterkette zurückgeführt – daher der Name LFSR.

5-Bit LFSR mit XNOR-Gattern

Während der Laufzeit erzeugt das LFSR ein Pseudo-Zufallsmuster – es ist nah an echtem Zufall, aber nicht vollständig zufällig, da man aus jedem Zustand den nächsten vorhersagen kann. Wichtige Eigenschaften von Schieberegistern:

• LFSR-Muster sind pseudo-zufällig.
• Ausgangsmuster sind deterministisch. Der nächste Zustand lässt sich aus der Position der XOR-Gatter und dem aktuellen Muster berechnen.
• Ein Muster aus lauter 0ern kann nicht auftreten, wenn XOR-Gatter als Taps verwendet werden. Da 0 XOR 0 immer 0 ergibt, würde das LFSR stoppen.
• Ein Muster aus lauter 1ern kann nicht auftreten, wenn XNOR-Gatter als Taps verwendet werden. Da 1 XNOR 1 immer 1 ergibt, würde das LFSR stoppen.
• Die maximal mögliche Anzahl an Iterationen eines LFSR = 2^Bits - 1

Längere LFSRs benötigen mehr Zeit, um alle Iterationen zu durchlaufen. Die längste mögliche Iterationsanzahl für ein N-Bit-LFSR beträgt 2^N - 1. Bedenkt man, dass alle möglichen Muster einer N-Bit-Folge 2^N betragen, gibt es genau ein Muster, das ein LFSR nicht darstellen kann: alle 0er bei XOR-Feedback, alle 1er bei XNOR-Feedback.

Der VHDL- und Verilog-Code erstellt ein beliebig breit konfigurierbares N-Bit-LFSR. Er nutzt Polynome (die Mathematik hinter dem LFSR), um für jede Bitbreite die maximal mögliche LFSR-Länge zu erzeugen. Für 3 Bit dauert es 2³-1=7 Takte, für 4 Bit: 2⁴-1=15, für 5 Bit: 2⁵-1=31 etc. Die Implementierung basiert auf XNOR, damit das FPGA im LFSR mit einem All-Null-Zustand starten kann. Hier ist die vollständige Tabelle aller LFSR-Muster, veröffentlicht von Xilinx.

VHDL-Implementierung:

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

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
  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-Implementierung:

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

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(}), // Replication
    .o_LFSR_Data(w_LFSR_Data),
    .o_LFSR_Done(w_LFSR_Done)
  );
  always @(*) #10 r_Clk