Sunday, 10 February 2013

Random Number Generator in Verilog | FPGA

In verilog a random number can be generated by using the $random keyword but that works only for simulation purposes and cannot be implemented. So when we need a random number for implementation i.e. in hardware it can be achieved using an LFSR (Liner Feedback Shift Register). An LFSR is simply a shift register with some of its bits (known as taps) XOR'd with themselves to create a feedback term.

When implementing an LFSR it's width and it's repeatability must be kept under consideration .An N-bit LFSR will be able to generate (2**N) - 1 random bits before it starts repeating. For example a 30 bit LFSR will have 1073741823 random states before repeating, so for most practical purposes this can be considered true random.

In an LFSR the MSB will always be the feedback point also the main thing to take care of while coding an LFSR is to know which bits are the taps (to be selected for XOR). This is confusing as the taps are different for different size registers. For example an 8 bit LFSR will have its 8th, 6th, 5th and 4th bits XOR'd with each other whereas a 10 bit LFSR will have its 10th and 7th bits XOR'd to create the random numbers. So clearly there is no pattern to this, but thankfully Xilinx has calculated all of this and made it available to us in its online documentation. The table below shows the tap locations for LFSR's upto 168 bits.

LFSR random number tap locations

An LFSR is good for generating a stream of random bits. It does not generate a random number by itself but only the feedback bit is random. However that does not mean that we cannot use this fact to generate a random number. In my code below I have an output of 13 bits and a 13 bit random number is accomplished by shifting the feedback bit enough times to equal the desired output size. In my case when it has shifted 13 times it will be assigned to the output. This way every bit is random thus making the whole number pretty random if you ask me.

Below is a code for a 13 bit LFSR. Notice my selection of taps is taken from the table above:

module LFSR (
    input clock,
    input reset,
    output [12:0] rnd 

wire feedback = random[12] ^ random[3] ^ random[2] ^ random[0]; 

reg [12:0] random, random_next, random_done;
reg [3:0] count, count_next; //to keep track of the shifts

always @ (posedge clock or posedge reset)
 if (reset)
  random <= 13'hF; //An LFSR cannot have an all 0 state, thus reset to FF
  count <= 0;
  random <= random_next;
  count <= count_next;

always @ (*)
 random_next = random; //default state stays the same
 count_next = count;
  random_next = {random[11:0], feedback}; //shift left the xor'd every posedge clock
  count_next = count + 1;

 if (count == 13)
  count = 0;
  random_done = random; //assign the random number to output after 13 shifts

assign rnd = random_done;


As requested, below is the test bench for the above code, not much stimulus in it, its just a simple reset.
module test;

 // Inputs
 reg clock;
 reg reset;

 // Outputs
 wire [12:0] rnd;

 // Instantiate the Unit Under Test (UUT)
 LFSR uut (
 initial begin
  clock = 0;
   #50 clock = ~clock;
 initial begin
  // Initialize Inputs
  reset = 0;

  // Wait 100 ns for global reset to finish
      reset = 1;
  reset = 0;
  // Add stimulus here

 initial begin
 $display("clock rnd");
 $monitor("%b,%b", clock, rnd);

Do note that this is not pure random, this number can be predicted if the algorithm is known. Thus don't use this for security purposes ;)