FPGAにおける効率的なLFSR設計：VHDLとVerilogによる実装

FPGA内部でのLFSR（線形フィードバックシフトレジスタ） - VHDL & Verilogコード

FPGA内部での線形フィードバックシフトレジスタの動作原理

LFSRはLinear Feedback Shift Registerの略で、FPGA内部で有用な設計手法です。LFSRは合成が容易で、比較的少ないリソースでFPGA内部에서非常に高いクロックレートで動作可能です。LFSRの恩恵を受けるアプリケーションは多岐にわたります。

• カウンタ
• テストパターン生成器
• データスクランブリング
• 暗号技術

線形フィードバックシフトレジスタは、FPGA内部でシフトレジスタとして配線された一連のフリップフロップとして実装されます。シフトレジスタチェーンのいくつかのタップ（取り出し点）をXORまたはXNORゲートの入力として使用し、その出力をシフトレジスタチェーンの先頭にフィードバックします。これがLFSRの「Feedback」の由来です。

5ビットLFSR（XNORゲート使用）

LFSRが動作しているとき、個々のフリップフロップが生成するパターンは疑似ランダム、つまりランダムに近いものです。完全なランダムではないのは、LFSRパターンの任意の状態から次の状態を予測できるためです。シフトレジスタの重要な特性は以下の通りです。

• LFSRパターンは疑似ランダムである
• 出力パターンは決定論的。XORゲートの位置と現在のパターンを知っていれば次の状態が分かる
• タップにXORゲートを使用する場合、すべて0のパターンは出現しない。0 XOR 0は常に0になるため、LFSRが停止してしまう
• タップにXNORゲートを使用する場合、すべて1のパターンは出現しない。1 XNOR 1は常に1になるため、LFSRが停止してしまう
• 任意のLFSRの最大反復回数 = 2^Bits-1

より長いLFSRは全反復を完了するのにより多くの時間を要します。NビットLFSRの最長可能反復回数は2^N-1です。Nビット長のすべてのパターンの組み合わせは2^N通りなので、LFSRで表現できないパターンは1つだけ存在します。XORゲートをフィードバックに使用する場合は全0、XNORゲートを使用する場合は全1のパターンです。

ここに示すVHDLとVerilogのコードは、任意のNビット幅のLFSRを作成します。LFSRの背後にある数学である多項式を用いて、各ビット幅での最大可能LFSR長を実現しています。したがって、3ビットなら2³-1=7クロック、4ビットなら2⁴-1=15、5ビットなら2⁵-1=31クロックで全組み合わせを巡回します。FPGAがLFSRを全0状態で起動できるよう、XNOR実装をベースにしています。Xilinxが公開している全LFSRパターンの完全なテーブルはこちらです。

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 

テストベンチ (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実装:

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 

テストベンチ (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