Pseudo random generator tutorial in VHDL (Part 3/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 consist of 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 will have an additional degree of confidence in our VHDL block.

This is what the following Matlab code is intended for:

[CODE]% Generate LFSR – Matlab script
a = uint32(0);


% Order of the polynom, up to 32
% Matlab range 1 to 32, VHDL 0 to 31
order = 16;


av = zeros(2^order-1, 1);
ii = 1;


while (ii < 2^order)
fb1 = bitxor(bitget(a, 15), bitget(a, 14));
fb2 = bitxor(bitget(a, 13), bitget(a, 4));
feedback = not( xor (fb1, fb2));

a = bitshift( a, 1, order) + uint32(feedback);
av(ii, 1) = a;
ii = ii + 1;
end
[/CODE]

The block is semi-configurable. It supports any register size up to 32. But you have to manually update the lines that calculate fb1, fb2and feedback, which calculate the feedback function to the LFSR.

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. You should doubt about everything. It is the way to find the bugs before your clients do!

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[SUP]order[/SUP]- 1) just once.
So added a few lines to the Matlab script to calculate how many times each LFSR generated number appears. If the block works well, each number will appear just once, and the maximum AND minimum of the yvector will be 1.

[CODE]y = zeros(size(av));

for ii = 1:length(av)
[rows] = find(av == (ii-1));
y(ii) = size(rows, 1);
end


max(y)
min(y)

[/CODE]

Let’s put our tester’ tester file to test. Suppose I copied the feedback function wrong and instead of ‘bitget(a, 4)‘ I wrote ‘bitget(a, 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:

[CODE]>> find (av == 0)

ans =

Empty matrix: 0-by-1

>> find (av == 1)

ans =

1
24574
49147

>>
[/CODE]

Thus we see that the code has a mistake (as we already know). If the code was OK, the maximum and minimum of yshould both be one. And each and every value we searched for, should appear, from zero to t 2[SUP]order[/SUP]-1.

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

[CODE]% Normalize the input
m = (max(y)-min(y))/2;
y1 = y/(y-m);


Y = fft(y1,NFFT)/NFFT;
f = linspace(0,1,NFFT/2+1);
subplot


% Plot single-sided amplitude spectrum.
subplot(1,2,1);
plot(f,20*log(abs(Y(1:NFFT/2+1))))
title(‘Single-Sided Amplitude Spectrum of y(t)’)
xlabel(‘Frequency (Hz)’)
ylabel(‘|Y(f)|’)


% Plot time domain
subplot(1,2,2);
plot(y1(1:250));
title(‘Time domain’)
xlabel(‘time’)
[/CODE]

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.

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.

References
Pseudo random generator tutorial part 1
Pseudo random generator tutorial part 2

My blog: FPGA Site

P.S. The files for chapters 5 and 6 are available below. Please rename the .txt extension to .m to run them under Matlab

Share this post via:

• 
• 
• 
•