随机数的 LSFR 计数器

Question

module LSFR_counter 
#(parameter BITS = 5)
(
  input             clk,
  input             rst_n,

  output reg [4:0] data
);
reg [4:0] data_next;

always @* begin
  data_next[4] = data[4]^data[1];
  data_next[3] = data[3]^data[0];
  data_next[2] = data[2]^data_next[4];
  data_next[1] = data[1]^data_next[3];
  data_next[0] = data[0]^data_next[2];
end

always_ff @(posedge clk or negedge rst_n) begin
  if(!rst_n)
    data <= 5'h1f;
  else
    data <= data_next;
end
endmodule

这是 4 位数 LSFR 的代码。我想为 FPGA 板实现 N 位随机数生成器。

Answer 1

如果你想实现一个 N 位 LFSR，那么因为 LFSR 的每个长度都有不同的多项式，因此需要一组不同的 XOR 抽头来产生下一个 LFSR 值，你将需要有常量或根据 'BITS'.

描述不同抽头点的查找 table，然后设计可以使用这些点

一个更简单的方法可能是实现一个 32 位 LFSR，然后使用它的最低有效 N 位作为输出。这具有增加除最大长度 LFSR 之外的任何内容的重复周期的额外好处，在这些情况下提供更好的随机性。

如果您选择第一个选项，请查看使用 Fibonacci 形式而不是 Galois 形式是否会使设计更有利于以这种方式进行参数化。我不太明白您在 5 位示例中使用的是哪种形式。

我是 VHDL 专家*，所以我无法提供 Verilog 代码，但类似 VHDL 的伪代码（未经测试）可能如下所示：

constant TAPS_TABLE : TAPS_TABLE_type := (
    "00000011",
    "00000110",
    ...
);

for i in 0 to BITS-2 loop
    if (TAPS_TABLE(BITS-2)(i) = '1') then
        data_next(i) <= data(0) xor data(i+1)
    else
        data_next(i) <= data(i+1)
    end if;
end for;

假设 table 已完成，这将支持 BITS 在 2 到 8 之间（含）。常量 TAPS_TABLE 会在综合过程中被优化掉，留给您的资源消耗不亚于手动编码的 LFSR。

* 这个问题原来有一个 'VHDL' 标签。

Answer 2

N 通常保留用于 LFSR 的状态，M 可用于我们希望生成的随机位数。

标准LFSR生成1位随机数据，如果使用LFSR的连续位，它们可以高度相关，特别是如果每个时钟周期取一个多位值。为了消除这种相关性，我们可以对 lfsr 进行超频，比如说 4 次以生成 4 位。对此的替代方法是计算您将为每个位获得的方程式（反馈多项式）。对于每个时钟，其内部状态（由 LFSR 的 N 位表示）将向前移动 4 个步骤。超频或创建反馈抽头以将状态向前移动超过 1 步的技术都被称为跃进。

问题中的代码示例取自a previous question and answer，这是一个为飞跃式lfsr手动创建额外反馈的示例。

执行此操作的数学运算可以通过生成转换矩阵并乘以我们希望前进的步数的幂来完成。

快速 4 位 LFRS 示例：使用转换矩阵 a:

a =

     0     1     0     0
     0     0     1     0
     0     0     0     1
     1     0     0     1

反馈是矩阵最后一行第一位和最后一位的异或。所有其他行只是一个班次。这个 LFSR 的输出对一个位来说是好的。两位会受到高相关性的影响，除非超频。

>> a^2

ans =

     0     0     1     0
     0     0     0     1
     1     0     0     1
     1     1     0     1

如果我们想要两位，我们需要对转换矩阵进行平方。可以看出，前两行是两个位置的移位，我们需要两个位置的反馈，即我们为每个时钟将 LFSR 向前移动两个状态。

只是为了确认我们是否需要三位：

a^3

ans =

     0     0     0     1
     1     0     0     1
     1     1     0     1
     1     1     1     1

上一个问题中的第二个代码示例继续对代码进行参数化，因此不必手动创建跳跃式计算，跳过所有可爱的数学运算！然而，所使用的方法意味着它无法完全参数化。因此，我想重新审视我为该问题给出的示例：

module fibonacci_lfsr(
  input  clk,
  input  rst_n,

  output [4:0] data
);

wire feedback = data[4] ^ data[1] ;

always @(posedge clk or negedge rst_n)
  if (~rst_n) 
    data <= 4'hf;
  else
    data <= {data[3:0], feedback} ;

endmodule

现在我们要对其进行参数化：

module fibonacci_lfsr#(
  parameter POLYNOMIAL = 4'h9
)(
  input  clk,
  input  rst_n,

  output [4:0] data
);

//AND data with POLYNOMIAL this 
// selects only the taps in the polynomial to be used.
// ^(  ) performs a XOR reduction to 1 bit
always @* begin
  feedback  = ^( POLYNOMIAL & data);
end

//Reseting to 0 is easier
// Invert feedback, all 1's state is banned instead of all 0's
always @(posedge clk or negedge rst_n)
  if (~rst_n) 
    data <= 'b0;
  else
    data <= {data[3:0], ~feedback};

endmodule

现在是一小步，只需将移位带到同步循环之外以帮助完成后面的步骤。

always @* begin
  data_next = data;
  feedback  = ^( POLYNOMIAL & data);
  data_next = {data_next[3:0], ~feedback} ; //<- Shift and feedback
end

always @(posedge clk or negedge rst_n)
  if (~rst_n) 
    data <= 'b0;
  else
    data <= data_next;

TL;DR

现在要控制跳跃式迭代，让工具完成乘以转移矩阵的繁重工作。

module fibonacci_lfsr#(
  parameter POLYNOMIAL = 4'h9,
  parameter N = 4,
  parameter BITS = 2
)(
  input  clk,
  input  rst_n,

  output [BITS-1:0] random
);
reg [N-1:0] data;
reg [N-1:0] data_next;
reg feedback;

assign random = data[N-1:N-BITS];

always @* begin
  data_next = data;
  // Compiler unrolls the loop, calculating the transition matrix
  for (int i=0; i<BITS; i++) begin
    feedback  = ^( POLYNOMIAL & data_next);
    data_next = {data_next[N-2:0], ~feedback} ; 
  end
end

always @(posedge clk or negedge rst_n)
  if (~rst_n) 
    data <= 'b0;
  else
    data <= data_next;
endmodule

示例 EDA Playground.

i++ 是 SystemVerilog 的一部分。如果您只能合成普通（2009 年之前）Verilog，那么您需要将 i 声明为整数并在 for 循环中使用 i =i+1。

Answer 3

除了前面的回答：

多年前，Xilinx 就如何实现 'pseudo random number generators' (PRNG) 写了一篇很好的 AppNote。 AppNote 对于 n = 3..168 有一个 TAP table。 TAP table 已优化以允许使用移位寄存器。所以 n=32 的 PRNG 不使用 32 个单个 FF。

Efficient Shift Registers, LFSR Counters, and Long PseudoRandom Sequence GeneratorsXilinx [XAPP 052][1996.07.07]

随机数的 LSFR 计数器

LSFR counter for random number

random

verilog

TL;DR