random - （疑似）ハードウェア乱数ジェネレーターを実装する方法

Question

HDL（verilog）にハードウェア乱数ジェネレーターをどのように実装しますか？

どのようなオプションを検討する必要がありますか？

---

この質問は、自己回答形式に従っています。追加の回答と更新をお勧めします。

Answer 1

モーガンの回答に記載されているように、これは単一のランダムビットのみを生成します。LFSRのビット数は、シーケンスが繰り返される前に取得する値の数のみを設定します。Nビットの乱数が必要な場合は、LFSRをNサイクル実行する必要があります。ただし、クロックサイクルごとに新しい数値が必要な場合、他のオプションは、ループを展開して、Nサイクルでの数値を予測することです。以下のモーガンの例を繰り返しますが、各サイクルで5ビットの数値を取得するには：

module fibonacci_lfsr_5bit(
  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 @(posedge clk or negedge rst_n)
  if(!rst_n)
    data <= 5'h1f;
  else
    data <= data_next;

endmodule

編集：計算を行う必要のない新しいバージョンを以下に追加しました。それをループに入れて、合成ツールにロジックを理解させます。

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

    output reg [4:0] data
    );

   reg [4:0] data_next;
   always_comb begin
      data_next = data;
      repeat(BITS) begin
         data_next = {(data_next[4]^data_next[1]), data_next[4:1]};
      end
   end

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

endmodule

LFSRの長さもパラメーター化できるようにしたいのですが、フィードバックタップが単純なパターンに従わないため、これははるかに困難です。

Answer 2

これは、FPGAで動作するTRNG（真の乱数ジェネレーター）です。基本的にはフリップフロップのないLFSRタイプの構造であるため、連続して動作する組み合わせループです。信号は無秩序に振動します。これらのモジュールのいくつかとXORビットを組み合わせると、それぞれからのジッターが組み合わされるため、真にランダムなビットが得られます。これを実行できる最大クロックレートはFPGAによって異なります。ランダム性は、diehard、dieharder、STS、TestU01などのテストスイートでテストする必要があります。

これらはガロアリングオシレータ（GARO）と呼ばれます。消費電力と面積が少ない他のTRNGもありますが、操作と書き込みが難しく、通常、フリップフロップを準安定にするためにチューニング遅延に依存しています。

module GARO (input stop,clk, reset, output random);

(* OPTIMIZE="OFF" *)                    //stop *xilinx* tools optimizing this away
wire [31:1] stage /* synthesis keep */; //stop *altera* tools optimizing this away
reg meta1, meta2;

assign random = meta2;

always@(posedge clk or negedge reset)
if(!reset)
  begin
    meta1 <= 1'b0;
    meta2 <= 1'b0;
  end
else if(clk)
  begin
    meta1 <= stage[1];
    meta2 <= meta1;
  end

assign stage[1] = ~&{stage[2] ^ stage[1],stop};
assign stage[2] = !stage[3];
assign stage[3] = !stage[4] ^ stage[1];
assign stage[4] = !stage[5] ^ stage[1];
assign stage[5] = !stage[6] ^ stage[1];
assign stage[6] = !stage[7] ^ stage[1];
assign stage[7] = !stage[8];
assign stage[8] = !stage[9] ^ stage[1];
assign stage[9] = !stage[10] ^ stage[1];
assign stage[10] = !stage[11];
assign stage[11] = !stage[12];
assign stage[12] = !stage[13] ^ stage[1];
assign stage[13] = !stage[14];
assign stage[14] = !stage[15] ^ stage[1];
assign stage[15] = !stage[16] ^ stage[1];
assign stage[16] = !stage[17] ^ stage[1];
assign stage[17] = !stage[18];
assign stage[18] = !stage[19];
assign stage[19] = !stage[20] ^ stage[1];
assign stage[20] = !stage[21] ^ stage[1];
assign stage[21] = !stage[22];
assign stage[22] = !stage[23];
assign stage[23] = !stage[24];
assign stage[24] = !stage[25];
assign stage[25] = !stage[26];
assign stage[26] = !stage[27] ^ stage[1];
assign stage[27] = !stage[28];
assign stage[28] = !stage[29];
assign stage[29] = !stage[30];
assign stage[30] = !stage[31];
assign stage[31] = !stage[1];

endmodule

Answer 3

多くの場合、 LFSRが最初の呼び出しポートです。実装は比較的簡単で、フィードバック項を作成するためにいくつかの項がXORされたシフトレジスタです。

LFSRの実装を検討する際には、乱数のビット幅と数値の再現性を考慮する必要があります。Nビットの場合、MaximalLFSRには(2**N) - 1状態があります。すべてのゼロ状態は、追加のハードウェアなしでは使用できません。

ビット0とビット4をタップする4ビットLFSRの例。

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

タップポイントを選択し、シーケンスの長さ（繰り返される前の数）を見つけることは、この表から見つけることができます。

たとえば、17,820,000、30ビット幅のシーケンスでは、次のタップを使用できます。

0x20000029 => bits "100000000000000000000000101001"   
0x2000005E => bits "100000000000000000000001011110"
0x20000089 => bits "100000000000000000000010001001"

最初のフィードバック用語は次のとおりです。

feedback = data[29] ^ data[5] ^ data[3] ^ data[0];

タップの順序がわからない場合は、MSBが常にフィードバックポイントになることに注意してください。最後の（タップ）フィードバックポイントは、LFSRの有効長を定義します。その後は、シフトレジスタになり、フィードバックシーケンスには影響しません。

69,273,666のシーケンスが必要な場合は、31ビットのLFSRを実装し、乱数に30ビットを選択する必要があります。

LFSRは、1ビットの乱数ストリームを作成するための優れた方法ですが、値の間に相関関係がある複数の連続するビットを取得している場合は、同じ番号をシフトしてディザービットを加えたものになります。番号がディザストリームとして使用されている場合は、マッピングレイヤーを導入することをお勧めします。たとえば、1ビットおきにスワップします。または、ビットごとに異なる長さまたはタップポイントのLFSRを使用します。

参考文献

効率的なシフトレジスタ、LFSRカウンター、および長い疑似ランダムシーケンスジェネレーター、
PeterAlfkeによるザイリンクスアプリノート。

Virtexデバイスの線形フィードバックシフトレジスタ、
MariaGeorgeとPeterAlfkeによるザイリンクスアプリノート。