Pseudo random number generator Tutorial



In this tutorial we will see how to design and test a VHDL component. We will start with a very simple block and gradually add features to it. We will also simulate it and test its output with Matlab. Over the process we will see:
  • How to start with a simple block and gradually add features and improvements
  • How to add a test bench (simulation)
  • Adding parameters to a VHDL component
  • Saving the component data output to files (from simulation)
  • Importing the files to Matlab in order to:
    1. Verify the results, and
    2. Analyze the results (in this case, using FFT).
The tutorial comprises three chapters, and it is divided into three entries of this blog. Make sure that you haven't missed to visit part 2 and part 3 of the tutorial!

For this tutorial it is assumed that you already have basic knowledge of the VHDL language and know how to use simulation tools (We will use the Xilinx's Vivado built in simulator, but you can easily adapt the tutorial to other tools you may be familiar with).




Chapter 1 - Simple implementation

Over the chapters of the tutorial we are going to generate random numbers by HW. One popular way of generating pseudo-random numbers by HW is by using an LFSR. LFSR stands for Linear-Feedback Shift Register.
The input bit to the shift register is a linear function of its previous value. The generation of pseudo-random sequences is based on linear algebra, where the register is interpreted as a polynomial. Each bit in the register is the coefficient or order 'n' of such a polynomial.
A register of length 'n' can generate a pseudo-random sequence of maximum length 2n-1. There are 'recipes' for the linear feedback function needed to generate maximum length sequences for any register length. For further reading you can check this application note from Xilinx.

Mike Field correctly pointed to me that an LFSR is a random BIT generator. So to generate an 'n' bit random NUMBER, we must advance the LF Shift Register by 'n' positions.
Hence, in this tutorial we will first make and test a random bit generator using an LFSR, and then, in later chapters, we will activate the LFSR 'n' times to generate a random number. 
Let's see our first version of a pseudo-random bit generator written in VHDL.
For this first example, the polynomial order is very low, i.e. 3, which generates a sequence consisting of only 15 states. The polynomial order is one less than the quantity of bits of the register. Each bit in the register is a coefficient of the polynomial, from a0 to an-1. In our first case, from a0 to a3. For each state the output will be either '0' or '1', since this is a pseudo-random bit generator. If we keep running the simulation, these 15-values pseudo-random bit sequence will repeat indefinitely.
That is the reason why these sequences are called pseudo-random. They have a certain variability, but on the other hand, they are repetitive, and even if they don't generate a trivial sequence, they always will produce the same sequence.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 library ieee;
   use ieee.std_logic_1164.all;

 entity lfsr_bit is
   port (
     reset    : in  std_logic;
     clk      : in  std_logic; 
     rbit_out : out std_logic
   );
 end entity;

 architecture rtl of lfsr_bit is
   signal lfsr       : std_logic_vector (3 downto 0);
   signal feedback  : std_logic;

 begin

   -- option for LFSR size 4
   feedback <= not(lfsr(3) xor lfsr(2));  

   sr_pr : process (clk) 
   begin
     if (rising_edge(clk)) then
       if (reset = '1') then
         lfsr <= (others => '0');
       else
         lfsr <= lfsr(2 downto 0) & feedback;
       end if; 
     end if;
   end process sr_pr;

   rbit_out <= lfsr(3);
  
 end architecture;

The process starting at line 21 implements a shift register. The feedback input to the shift register is a linear combination of some of its own bits. Since the process sensitivity only includes the clk signal, we can know that this process uses a synchronous reset.

Also please notice that the process is labeled (sr_pr). Labeling processes helps us to better understand and maintain our code.

On the next chapter of this tutorial we will add a test bench for the pseudo random bit generator.

The source file for this Chapter is released on Github here








Chapter 2 - Adding a test bench

The best way to debug an FPGA design is with a good test bench. Any bug that has to be analyzed in the target, using tools like Xilinx's Chipscope, will take much longer than it would if it was caught during simulation. 

The simulation gives you access to any signal in the design. Chipscope, a logic analyzer or PCB signal probing, on the other hand, give limited access to signals. Even using Chipscope has to be limited to a certain quantity of signals, since the tool competes for resources with the design itself. If the signals chosen for the debugging do not include key signals to find the bug source, you will need to synthesize again the design, and this is time consuming.

Of course that there are certain system features that are difficult to simulate. But ideally, at least each block of a design should be verified with simulation tools before integration.


So let's add a test-bench to our LFSR block:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 library ieee;
   use ieee.std_logic_1164.all;
    
 entity tb_lfsr_bit is
 end entity;

 architecture test of tb_lfsr_bit is
   constant PERIOD  : time   := 10 ns;
   signal clk       : std_logic := '0';
   signal reset     : std_logic := '1';
   signal endSim    : boolean   := false;

   component lfsr_bit is
     port (
       reset     : in  std_logic;
       clk       : in  std_logic; 
       rbit_out  : out std_logic
     );
   end component;

 begin
   clk     <= not clk after PERIOD/2;
   reset   <= '0' after  PERIOD*10;

   -- Main simulation process
   main_pr : process 
   begin
     wait until (reset = '0');
     for i in 0 to 31 loop
       wait until (clk = '1');
     end loop;
     endSim <= true;
   end process main_pr; 

   -- End the simulation
   stop_pr : process 
   begin
     if (endSim) then
       assert false 
         report "End of simulation." 
         severity failure; 
     end if;
     wait until (clk = '1');
   end process stop_pr; 

   DUT : lfsr_bit
     port map (
       clk         => clk,
       reset       => reset,
       rbit_out    => open
     );

end architecture;

A test-bench is an entity with no ports (see lines 4-5), that instantiates the device under test (DUT) as a component.
The test-bench has signals that are used to exercise the block under test. A 50MHz (20 nsec period) clk is defined on lines 8-9. The reset signal is asserted at the beginning of the simulation (see line 10) and de-asserted after some time (line 23). This block is so simple that it is enough to provide a clock and de-assert reset to get it going.

The main process loop just waits for 32 clocks, enough for the whole pseudo-random sequence to be output twice.
The process starting at line 36 stops the simulation after some time. In this way, the simulation will always stop by itself. Personally I find it annoying when the simulator runs forever, I prefer a self-stopping one.

A bit pseudo-random simulator output is either '1' or '0'. It could model the flipping of a coin. An ideal coin will show 'head' 50% of the time, and 'tails' the other 50%. But what happens if we throw a coin several times and we expect to get, let's say, three heads on a row? Interesting things happen when we mix time and probability. In one hand, the result of throwing a coin, for an ideal coin, should have no effect on the next toss. If I got a head, the next toss will still have 50% of probability of being head.

But if I want to know before throwing, what is the probability of getting three heads in a row, things change. If we make a table including all the possible combinations of results when flipping a coin three times (or flipping three coins together), getting three heads is only one out of eight possible outcomes. For another interesting combination of probability and time (and how one affects the other), please check the famous Monty Hall problem.
In our simulation, since we generate pseudo-random bits, we would also expect to see some results appearing more often than others. Let's see if that assumption is correct:


The sequence starts on the rising edge clock following time=100ns, when reset is de-asserted. It can be seen that the sequence repeats itself again after time=250ns.

The sequence consists of 3 zeros, 3 ones, 1 zero, 2 ones, 2 zeros, 1 one, 1 zero, 1 one, 1 zero and then it starts repeating itself with 3 zeros.

So the frequency of each event is:

EventQuantity
Three equal values2
Two equal values2
One value5

The classification was done taking into account our previous knowledge of the pseudo-random sequence, how it starts (all zeros) and when it repeats. The distribution of values somehow respects our intuition that longer 'same-value' sequences should appear less often.

We could also make a less biased classification without prior knowledge of the internals of the sequence generator, and conclude that the events appearance are as follows:

EventQuantity
Four equal values1
Three equal values1
Two equal values2
One value4

Which in any case still follows the intuition that the longer "same-value" events should appear less often. However, while for a real random generator any event can happen (like, say, twelve equal values), a pseudo-random generator will be able to generate those events in a quantity limited by its own order, and also, as we have already said, appearing always in the same exact sequence.

The release on Github for Chapters 1 & 2 includes VHDL source code, test bench and waveform file for Vivado Simulator.


Go to the second part of this tutorial

Comments

  1. I have to do a VHDL program:

    Build a generator of pseudo-random numbers with the period 15.The polynomial generating this sequence is 1 + v + v ^ 4.The display will be on digit.Use the internal clock of FPGA.

    board: basys 3 artix 7

    ReplyDelete
    Replies
    1. In the examples I did I used XNOR feedback. You may want to read the Wikipedia entry that explains how to generate the polynomial using XOR - https://en.wikipedia.org/wiki/Linear-feedback_shift_register.

      Delete
  2. Hi - nice blog.

    Just wanted to add that LFSR are not pseudo random number generators, they are pseudo random bit generators

    If you are using them to generate n-bit random numbers you should advance the LFSR 'n' times, to generate n new bits. This avoids the sequence being 'randomly' having n(x+1) = 2*n(x)+1 or n(x+1) = 2*n(x).

    Also, because of the way that LFRSs have only 2^n-1 states, (which isn't made clear in the blog) there is a slight bias in the generated bits (which may or may not be significant, depending on your use case.

    ReplyDelete
    Replies
    1. Hi Mike, thanks!

      Thanks also for your insight on how to use the LFSR to produce random numbers instead of bits. I will take this into account to improve the tutorial.

      Delete
  3. The length is a generated sequence is not 2^n, it is 2^n-1, but only if the polynomial is a generating polynomial. As you can see in your waveform, the signal 'count' never reaches x"F".

    Why are you using such a big construct to stop the simulation? 'simend' is a signal, so you can write just "wait until (simend = '1'); assert ....; wait;". Because 'simend' has no other purpose, you could also just wait for the specified time.

    Nevertheless, a good testbench should not end with an assertion, you should either terminate all processes (incl. implicit processes like the clock) or use "std.env.stop" to halt the simulation kernel.

    ReplyDelete
    Replies
    1. Hi Patrick,

      Thanks for all the comments you have left. I really appreciate the time you have invested for that. So from your and Mike's inputs I understand I have to make a major upgrade to this tutorial. I hope I will be able to make it soon.

      Regards,

      Delete
    2. Also I have corrected to 2^n-1 as you correctly pointed out.

      Delete

Post a Comment

Popular posts from this blog

VHDL or Verilog?

FPGA internal tri-state buses