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 (Formal testing), 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 2^n. 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.
So let's see our first version of a pseudo-random generator written in VHDL.
For this first example, the polynomial order is very low, i.e. 3 (4 bits), which generates a sequence consisting of 16 values. If we keep running the simulation, these 16-values pseudo-random 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 are not a trivial sequence, they always will be the same sequence. After the number '3' in this specific sequence, we will always get the number '7'. Of course a real random number generator does not behave in this way. But we will later see that even with this limitation, pseudo-random number sequences can approximate quite well the behavior of white noise.
 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
library ieee;
  use ieee.std_logic_1164.all;

entity lfsr1 is
  port (
    reset  : in  std_logic;
    clk    : in  std_logic; 
    count  : out std_logic_vector (3 downto 0)    -- lfsr output
  );
end entity;

architecture rtl of lfsr1 is
  signal count_i    : std_logic_vector (3 downto 0);
  signal feedback   : std_logic;

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

  sr_pr : process (clk) 
    begin
      if (rising_edge(clk)) then
        if (reset = '1') then
          count_i <= (others=>'0');
        else
          count_i <= count_i(2 downto 0) & feedback;
        end if;  
      end if;
    end process sr_pr;
  count <= count_i;
  
end architecture;
Early VHDL versions didn't support reading back outputs, that's why I use count_i as a working signal, which at the end of the block is copied to the output count.

I always use this convention (suffix '_i' for internal signals) and you may want to adopt these and other conventions (like using the '_n' suffix for active low signals) for code clarity and standardization.

The process starting at line 20 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 number 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
entity tb_lfsr1 is
end entity;

architecture test of tb_lfsr1 is

  constant PERIOD  : time   := 20 ns;

  signal clk       : std_logic := '0';
  signal reset     : std_logic := '1';
  signal count     : std_logic_vector (3 downto 0);
  signal endSim    : boolean   := false;

  component lfsr1 is
    port (
      reset     : in  std_logic;                       
      clk       : in  std_logic;               
      count     : out std_logic_vector (3 downto 0)   
    );
  end component;

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

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

  DUT : lfsr1
    port map (
      clk      => clk,
      reset    => reset,
      count    => count
    );

end architecture;

A test-bench is an entity with no ports (see lines 1-2), 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 6-8. The reset signal is asserted at the beginning of the simulation (see line 9) 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 process starting at line 44 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.
Let's see two screenshots of the simulation:

The signal looks (remotely) as a noise signal. It doesn't look so well since the sequence we used, of only fifteen steps, is very short. We can see that the signal repeats itself each 15 clock cycles. On next entries of the blog we will see how to improve the signal.

On the following diagram we can see with more clarity a single cycle with all 15 values of the output signal. Note that the count output is shown in two formats, 'analog' and 'digital'.


The release on Github for Chapter 2 includes the VHDL source code, test bench code and waveform file for Vivado simuator.



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

Post a Comment

Popular posts from this blog

VHDL or Verilog?

High Speed Serial I/O - free book