How to implement a random number generator (pseudo)
How to implement hardware random number generator in HDL (verilog)?
What options do you need to consider?
This question follows self-answer . Additional answers and updates are recommended.
source to share
LFSR is often the first port of call. The implementation is relatively simple, a shift register with a number of XORd terms together to create a feedback term.
When considering an LFSR implementation, consider the bit width of the random number and number repeatability. With N bits, the maximum LFSR will have states (2**N) - 1
. All zero states cannot be used without additional equipment.
An example of a 4 bit LFSR with taps bit 0 and bit 4:
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
The selection of connection points and the search for the length of the sequence (the number of numbers before it is repeated) can be found from this table.
For example, a sequence of 17,820,000, 30 bits wide might use taps:
0x20000029 => bits "100000000000000000000000101001"
0x2000005E => bits "100000000000000000000001011110"
0x20000089 => bits "100000000000000000000010001001"
The first has a feedback member:
feedback = data[29] ^ data[5] ^ data[3] ^ data[0];
If you are not sure about the order of the taps, remember that the MSB will always be the feedback point. The last point (feedback) feedback determines the effective length of the LFSR, after which it will be just a shift register and will not affect the feedback sequence.
If you want a sequence of 69,273,666, you will need to implement a 31-bit LFSR and choose 30 bits for your random number.
LFSR is a great way to create a 1-bit stream of random numbers, but if you take multiple consecutive bits, i.e. the correlation between values, it is the same number shifted plus an aliasing bit. If this number is used as an anti-aliasing stream, you can introduce a display layer, for example, replace each bit. Alternatively, use LFSRs of different lengths or tap points for each bit.
additional literature
Linear Feedback Shift Registers in Virtex Devices,
Xilinx App by Maria George and Peter Alfke .
source to share
As noted in Morgan's answer, this will only create one random bit. The number of bits in the LFSR only determines how many values you get before repeating the sequence. If you want to get N bits of a random number, you need to run LFSR for N cycles. However, if you want the new number of each measure to be a different one, you need to unroll the loop and predict what number will be in N cycles. Repeating Morgan's example below, but to get the 5-bit number of each loop:
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
Edit: Added a new version below which no math is required. Just put it in a loop and let the synthesis tool compute the logic:
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
I would also like to make the LFSR parameter parameterizable, but this is much more complicated since the backlabels do not follow a simple pattern.
source to share
It is a TRNG (True Random Number Generator) that runs on FPGA. It is basically an LFSR type structure with no flip flops, so it is a combinatorial loop that runs continuously. The signal fluctuates chaotically, when you combine multiple of these modules and the XOR bit, you get a truly random bit as the jitter of each one is combined. The maximum clock speed you can run depends on your FPGA, you should check the randomness with a test suite like diehard, dieharder, STS or TestU01.
They are called Galois Ring Oscillators (GARO). There are other TRNGs that use less power and area, but they cheat to work and write, usually relying on tuning delays to make the flipflop metastable.
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
source to share