Pseudo random generator Tutorial

lfsr_mod
Modelsim Altera running an LFSR simulation

In this tutorial we will see how to design a block. 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 the VHDL block
  • Saving the block data output to files (from simulation)
  • Importing the files to Matlab in order to:
    • Verify the results (Formal testing), and
    • Analyze the results (in this case, using FFT)

For this tutorial it is assumed that you already have basic knowledge of the VHDL language and know how to use simulation tools (Modelsim will be used, but you can easily adapt the tutorial to other tools you may be familiar with).

Chapter 1 – Simple implementation

We are going to generate random numbers by HW. One popular way of generating pseudo- random numbers by HW is by means of LFSR. LFSR stands for Linear-Feedback Shift Register.

The input bit to the shift register is a linear function of its previous value. The study to generate these 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-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.

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 15 values. If we keep running the simulation, these 15 values pseudo-random sequence repeat indefinitely.

That is the reason that 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 sequence, we will always get the number ‘7’. Of course a real random number does not behave in this way. But we will see later that even with this limitation, pseudo-number sequences can approximate quite well the behavior of white noise.

lfsr1

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 implements starting at line 27 a shift register. The feedback input to the shift register is a linear combination of some of its own bits.


stratix_disc_grp2


Chapter 2 – Adding a test-bench

Now let’s go over the test-bench for the LFSR

tb_lfsr1

Always a test-bench is an entity with no ports, 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) clock is defined on line 37. The reset signal is asserted at the beginning (see line 23) and de-asserted after some time (line 38). 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 can be run with the run -all command and will stop by itself.

Let’s see two screenshots of the simulation:

lfsr1_sim1

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 the 15 values of the output signal

lfsr1_sim2

The sources for these two chapters are available here

Go to the second part of this tutorial

Leave a Reply