Pseudo random generator Tutorial – Part 3

On the first two chapters of this Tutorial we started with a simple LFSR module and added a test bench. Then, on chapters three and four we upgraded our module with some features and learned to export the test bench data to files.

Chapter 5 – Matlab Formal Verification

Our VHDL block implements an algorithm that generates pseudo-random numbers. If the register is large enough, the output of the block will be hundreds or thousands of different numbers. How can we be sure that our block is working OK?

For algorithms validation, Matlab comes as a very handy tool. First, we will generate an LFSR in Matlab which also creates a results file. Then we can just simply compare both files, if they are equal, we have an additional degree of confidence in our VHDL block.

This is what the following Matlab code does:

lfsr_matlab1

The block is semi-configurable. It supports any register size up to 32. But you have to manually update lines 14, 15 and 16, which represent the feedback function to the LFSR and whose values can be taken from Xilinx’s application note, page 5.

If you are like me, you may be asking yourself if this is enough. If we use the Matlab code to verify the LFSR, how can we know that it is OK? And how can we know that Xilinx’s table is OK? After all, it could have a typo… Or maybe WE made a typo while copying from Xilinx table…

Being a little paranoid is good if you want to be a good design engineer. Doubt about everything. It is the way to find the bugs before your clients do that!

Well, in this case, I wrote some additional Matlab code to check the results. A good, or optimal, LFSR design, generates each and every number within its range (0 to 2^order – 1) just once.

So I wrote a little program to calculate how many times each LFSR generated number appears. If the block works well, each number will appear just once.

lfsr_matlab2

So, the maximum and the minimum of the ‘y’ vector will be one.

Let’s put our tester’ tester file to test. Suppose I copied the feedback function wrong and instead of ‘4’ I wrote ‘6’. This is a sub-optimal LFSR that doesn’t generate all possible values. When I ran the Matlab code between lines 22 and 31 I found that max(y)= 3 and min(y) = 0. Checking further, I found that, for example, value zero never happens, and value 1 happens three times:

lfsr_matlab3

Imagine trying to find those three values of ‘1’ by looking into the file! There is no doubt that we must use tools (like co-simulation with Modelsim and Matlab) to find these kind of perky bugs.


stratix_disc_grp2


Chapter 6 – Matlab Data analysis

On Chapter 5 we did a great forward leap. We generated ‘golden’ data for our algorithm using Matlab (using a description of the algorithm and checking that the algorithm produces all the values for the order of our LFSR). Then we can compare the VHDL generated data with the ‘golden’ data and be sure that our VHDL algorithm performs well.

Matlab gives us many more advantages. It is a powerful tool that enables us to analyze data in many ways.

As we have said, the LFSR is a pseudo-random generator. So, how random is pseudo-random? Well, a really random generator will produce white noise. So let’s make an FFT analysis of the LFSR produced data for different register sizes and see how close to pure noise they are.

For this purpose, I used the code below (Notice that the code analyzes ‘res.log’, i.e., the VHDL simulator output):

lfsr_matlab4

And these are the results of running this Matlab code over the outputs for various LFSR sizes (5, 7, 9 and 11(. The code graphs normalized amplitude vs. normalized frequency. It can be clearly seen that for small LFSR sizes the output is quite not random, while for LFSR=11, the output looks very close to white noise.

matlab_ana1matlab_ana2matlab_ana3matlab_ana4

This is the last chapter of this tutorial. I hope that you enjoyed it and that it has given new ideas to improve your code and its verification.

The source code for chapters 5 and 6 can be found here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s