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)
begin
 if (reset)
 begin
  random <= 13'hF; //An LFSR cannot have an all 0 state, thus reset to FF
  count <= 0;
 end
 
 else
 begin
  random <= random_next;
  count <= count_next;
 end
end

always @ (*)
begin
 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)
 begin
  count = 0;
  random_done = random; //assign the random number to output after 13 shifts
 end
 
end


assign rnd = random_done;

endmodule

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 (
  .clock(clock), 
  .reset(reset), 
  .rnd(rnd)
 );
 
 initial begin
  clock = 0;
  forever
   #50 clock = ~clock;
  end
  
 initial begin
  // Initialize Inputs
  
  reset = 0;

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

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

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 ;)