How to implement a (pseudo) hardware random number generator

How do you implement a hardware random number generator in an HDL (verilog)?

What options need to be considered?

This question is following the self-answer format. Addition answers and updates are encouraged.

Solution

An LFSR is often the first port of call. Implementation is relatively simple, a shift register with a number of terms XORd together to create the feedback term.

When considering the implementation of the LFSR, the bit width of the random number and the repeatability of the number need to be considered. With N bits a Maximal LFSR will have (2**N) - 1 states. All zero state can not be used with out additional hardware.

An example 4 bit LFSR with taps a 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

Choosing tap points and finding out the sequence length (number of numbers before it repeats) can be found from this table.

For example a sequence of 17,820,000, 30 bits wide could use taps of :

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

The first would have a feedback term of:

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

If you are unsure of the order of the taps, remember that the MSB will always be a feedback point. The Last (tap) feedback point defines the effective length of the LFSR, after that it would just be a shift register and have no bearing on the feedback sequence.

If you needed a sequence of 69,273,666 you would have to implement a 31 bit LFSR and choose 30 bits for your random number.

LFSRs are a great way to create a 1-bit random number stream but if you are taking multiple consecutive bits that there is a correlation between values, it is the same number shifted plus dither bit. If the number is being used as a dither stream you may want to introduce a mapping layer, for example swap every other bit. Alternatively use an LFSR of different length or tap points for each bit.

How to implement a (pseudo) hardware random number generator

Further Reading