How to generate pseudorandom bit sequence in FPGA?

[matrixofdynamism]

I am trying to understand a Xilinx application note XAPP052 "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators". It shows a method on how to use LFSRs to get random bit sequence of maximum length.
There are few things that I am trying to understand here:

I expected this document to show shift register chains with XOR or XNOR gate in feedback as it happens with CRC circuits. However, this is not the case an I am totally confused what they are really getting to.

1. What is the purpose of the "address counter" that keeps popping up in the whole document, even in Figures 3, 4 and 5!
2. The figure 5 shows Taps that exactly match the Table 3. The DFF and synchronous RAM blocks make up a 63-bit shift register with taps at bits 62 and 63. But, why do the RAM blocks have input from the address counter??? Shift registers don't need address input.
3. The figure 5 shows a 100x8 shift register. Why is it 100x8 and not just 100x1, we can still get the random sequnce that way right?
Also, if this is shift register then why do we need this address counter made up of 4 DFFs at the bottom? The taps for location 100 and 63 (going into XNOR gate) is not shown at all!? The input into the RAM blocks is DIN ( 8 ) for the first and also the last RAM block!?
4. In Figure 3 I do not see taps at locations 32, 22, 2, 1 which should happen for a 32-bit sequence. Why are they not making a 32x8 or 32x16 block here but they did something like this in Figue 4?

Finally,
5. What exactly is relationship between Tables 1 & 2 and the Table 3? I think the Tables 1 and 2 are merely about the address counter while the Table 3 is about the circuit used to generate the random bit sequence.

[ataradov]

This appnote uses SRAM instead of a bank of DFFs.  This generator generates a byte stream (1 byte each cycle), so the RAM topology is 100x8. RAM contents can't be shifted, so they use counters to shift the beginning of the data.

This basically describes a heavy optimization technique specific to Xilinx FPGAs. If you just want a generic shift register-based generator, look for more generic documents.

[Bassman59]

That app note is from 1996 and it targeted the XC4000-series FPGAs!   It uses RAM because it is building a very long LFSR. I don't think the 4000-series parts could configure the LUT as an SRL.

This should be a lot easier to implement in a modern FPGA which has shift registers and a ton of flip-flops.

[BrianHG]

I think the OP may just be looking for a high fidelity random number generator.  Here is a good fast one:

Here is a code I jumbled together from other online examples, I named it 'white_noise.v'.  It xor combines 2 different types of random number generators together.

Code: [Select]

module white_noise ( clk, rst, ena, out );
input           clk, rst, ena;
output [31:0] out ;

wire    [31:0] out = number_o[31:0] ;
reg [31:0] number_o;
reg [42:0] LFSR_reg;
reg [36:0] CASR_reg;

//CASR:
reg[36:0] CASR_varCASR,CASR_outCASR;
always @(posedge clk )

   begin
   if ( rst )
      begin
      CASR_reg  = (1);
      end
   else
      begin

      //if (loadseed_i )
        // begin
         //CASR_varCASR [36:32]=0;
         //CASR_varCASR [31:0]=seed_i ;
         //CASR_reg  = (CASR_varCASR );
         //end
      //else

         if (ena) begin

         CASR_varCASR =CASR_reg ;

         CASR_outCASR [36]=CASR_varCASR [35]^CASR_varCASR [0];
         CASR_outCASR [35]=CASR_varCASR [34]^CASR_varCASR [36];
         CASR_outCASR [34]=CASR_varCASR [33]^CASR_varCASR [35];
         CASR_outCASR [33]=CASR_varCASR [32]^CASR_varCASR [34];
         CASR_outCASR [32]=CASR_varCASR [31]^CASR_varCASR [33];
         CASR_outCASR [31]=CASR_varCASR [30]^CASR_varCASR [32];
         CASR_outCASR [30]=CASR_varCASR [29]^CASR_varCASR [31];
         CASR_outCASR [29]=CASR_varCASR [28]^CASR_varCASR [30];
         CASR_outCASR [28]=CASR_varCASR [27]^CASR_varCASR [29];
         CASR_outCASR [27]=CASR_varCASR [26]^CASR_varCASR [27]^CASR_varCASR [28];
         CASR_outCASR [26]=CASR_varCASR [25]^CASR_varCASR [27];
         CASR_outCASR [25]=CASR_varCASR [24]^CASR_varCASR [26];
         CASR_outCASR [24]=CASR_varCASR [23]^CASR_varCASR [25];
         CASR_outCASR [23]=CASR_varCASR [22]^CASR_varCASR [24];
         CASR_outCASR [22]=CASR_varCASR [21]^CASR_varCASR [23];
         CASR_outCASR [21]=CASR_varCASR [20]^CASR_varCASR [22];
         CASR_outCASR [20]=CASR_varCASR [19]^CASR_varCASR [21];
         CASR_outCASR [19]=CASR_varCASR [18]^CASR_varCASR [20];
         CASR_outCASR [18]=CASR_varCASR [17]^CASR_varCASR [19];
         CASR_outCASR [17]=CASR_varCASR [16]^CASR_varCASR [18];
         CASR_outCASR [16]=CASR_varCASR [15]^CASR_varCASR [17];
         CASR_outCASR [15]=CASR_varCASR [14]^CASR_varCASR [16];
         CASR_outCASR [14]=CASR_varCASR [13]^CASR_varCASR [15];
         CASR_outCASR [13]=CASR_varCASR [12]^CASR_varCASR [14];
         CASR_outCASR [12]=CASR_varCASR [11]^CASR_varCASR [13];
         CASR_outCASR [11]=CASR_varCASR [10]^CASR_varCASR [12];
         CASR_outCASR [10]=CASR_varCASR [9]^CASR_varCASR [11];
         CASR_outCASR [9]=CASR_varCASR [8]^CASR_varCASR [10];
         CASR_outCASR [8]=CASR_varCASR [7]^CASR_varCASR [9];
         CASR_outCASR [7]=CASR_varCASR [6]^CASR_varCASR [8];
         CASR_outCASR [6]=CASR_varCASR [5]^CASR_varCASR [7];
         CASR_outCASR [5]=CASR_varCASR [4]^CASR_varCASR [6];
         CASR_outCASR [4]=CASR_varCASR [3]^CASR_varCASR [5];
         CASR_outCASR [3]=CASR_varCASR [2]^CASR_varCASR [4];
         CASR_outCASR [2]=CASR_varCASR [1]^CASR_varCASR [3];
         CASR_outCASR [1]=CASR_varCASR [0]^CASR_varCASR [2];
         CASR_outCASR [0]=CASR_varCASR [36]^CASR_varCASR [1];

         CASR_reg  = (CASR_outCASR );

         end
      end
   end
//LFSR:

reg[42:0] LFSR_varLFSR;
reg outbitLFSR;
always @(posedge clk)

   begin
   if ( rst )
      begin
      LFSR_reg  = (1);
      end
   else
      begin
      //if (loadseed_i )
         //begin
         //LFSR_varLFSR [42:32]=0;
         //LFSR_varLFSR [31:0]=seed_i ;
         //LFSR_reg  = (LFSR_varLFSR );
         //end
      //else

         if (ena) begin

         LFSR_varLFSR =LFSR_reg ;
         outbitLFSR =LFSR_varLFSR [42];
         LFSR_varLFSR [42]=LFSR_varLFSR [41];
         LFSR_varLFSR [41]=LFSR_varLFSR [40]^outbitLFSR ;
         LFSR_varLFSR [40]=LFSR_varLFSR [39];
         LFSR_varLFSR [39]=LFSR_varLFSR [38];
         LFSR_varLFSR [38]=LFSR_varLFSR [37];
         LFSR_varLFSR [37]=LFSR_varLFSR [36];
         LFSR_varLFSR [36]=LFSR_varLFSR [35];
         LFSR_varLFSR [35]=LFSR_varLFSR [34];
         LFSR_varLFSR [34]=LFSR_varLFSR [33];
         LFSR_varLFSR [33]=LFSR_varLFSR [32];
         LFSR_varLFSR [32]=LFSR_varLFSR [31];
         LFSR_varLFSR [31]=LFSR_varLFSR [30];
         LFSR_varLFSR [30]=LFSR_varLFSR [29];
         LFSR_varLFSR [29]=LFSR_varLFSR [28];
         LFSR_varLFSR [28]=LFSR_varLFSR [27];
         LFSR_varLFSR [27]=LFSR_varLFSR [26];
         LFSR_varLFSR [26]=LFSR_varLFSR [25];
         LFSR_varLFSR [25]=LFSR_varLFSR [24];
         LFSR_varLFSR [24]=LFSR_varLFSR [23];
         LFSR_varLFSR [23]=LFSR_varLFSR [22];
         LFSR_varLFSR [22]=LFSR_varLFSR [21];
         LFSR_varLFSR [21]=LFSR_varLFSR [20];
         LFSR_varLFSR [20]=LFSR_varLFSR [19]^outbitLFSR ;
         LFSR_varLFSR [19]=LFSR_varLFSR [18];
         LFSR_varLFSR [18]=LFSR_varLFSR [17];
         LFSR_varLFSR [17]=LFSR_varLFSR [16];
         LFSR_varLFSR [16]=LFSR_varLFSR [15];
         LFSR_varLFSR [15]=LFSR_varLFSR [14];
         LFSR_varLFSR [14]=LFSR_varLFSR [13];
         LFSR_varLFSR [13]=LFSR_varLFSR [12];
         LFSR_varLFSR [12]=LFSR_varLFSR [11];
         LFSR_varLFSR [11]=LFSR_varLFSR [10];
         LFSR_varLFSR [10]=LFSR_varLFSR [9];
         LFSR_varLFSR [9]=LFSR_varLFSR [8];
         LFSR_varLFSR [8]=LFSR_varLFSR [7];
         LFSR_varLFSR [7]=LFSR_varLFSR [6];
         LFSR_varLFSR [6]=LFSR_varLFSR [5];
         LFSR_varLFSR [5]=LFSR_varLFSR [4];
         LFSR_varLFSR [4]=LFSR_varLFSR [3];
         LFSR_varLFSR [3]=LFSR_varLFSR [2];
         LFSR_varLFSR [2]=LFSR_varLFSR [1];
         LFSR_varLFSR [1]=LFSR_varLFSR [0]^outbitLFSR ;
         LFSR_varLFSR [0]=LFSR_varLFSR [42];

         LFSR_reg  = (LFSR_varLFSR );
         end
      end
   end
//combinate:
always @(posedge clk)

   begin
   if ( rst )
      begin
      number_o  = (0);
      end
   else
      if (ena) begin
      number_o  = (LFSR_reg [31:0]^CASR_reg[31:0]);
      end
   end

endmodule



[miken]

Yeah, modern tools/architecture will infer the shift registers and pack them into LUTs. No need to laboriously build clever resource-saving from the ground up.

OP might find XAPP884 more useful, but most useful is writing your own code and figuring out how you managed to bug up such a simple seeming thing

[Unixon]

This little document [ www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf ] describes few pretty good and simple PRNGs I would use on a PC or even a microcontroller.
Would it be a huge overkill to put them into FPGA ?
I guess this would take many many more logic blocks than a LFSR approach.
How do these PRNGs from Xilinx appnote compare statistically to arithmetic PRNGs I'm referring to ?

[NorthGuy]

If you have a free DSP block, it's very easy to setup multiplicative RNG which are commonly used in software.

There are also hardware related methods. For example, Xilinx has BRAM blocks which can be turned on and off through reconfiguration. If you turn it off, wait, then turn it back on, it'll be filled with random numbers. But reconfiguration is not straightforward and will probably take too much time and effort to implement.

[matrixofdynamism]

Well the basic issue is when I started looking into generating random numbers inside FPGA to help in "randomly inject errors into the system during its run" I was blown away by the depth of the subject. There are so many ways to generate random numbers where some rely on real source for entropy while others just generate a pseudo-random sequence. I even found some PhD thesis on this subject and many research papers. This all was rather terrifying.

During the research I came across the Xilinx app notes XAPP052 and also the XAPP884. Now the thing is, I can see there are examples on the internet of some LFSRs and BrianHG has been kind enough to give a code for it here as well.

I can just copy paste code and try to get it work but I really want to understand how to go about doing this from scratch. In the XAPP052 there is a table at the end which gives the taps for XNOR gates for LFSR register sequence. Now when I searched on LFSR registers pseudo random sequence examples, I got confused. Sometimes the registers are named by people as R0, R1, R2 ... and another one where they name them as R1, R2, R3 .... and do not start from R0. Then some people put R0/R1 on left side and some people put it on the right side so the signal flows from left to right or from right to left. Then some people use XOR gate, the App Note talks about XNOR gate. Sometimes the taps connect into XOR gates and all the XORing result is fed into the R0/R1 registers. At other things we XOR the feeback such that there is at most 1 XOR gate between any two successive registers. Now because different people follow different conventions, I don't know how exactly to interpet the table at the end of XAPP052 to make my LFSR. Also, while I have some guess on how to make e.g 12 bit or 16 bit pseudo random sequence generating LFSR from table at end of the XAPP052, I do not know how to verify it since I do not know what its (say) first few outputs are supposed to be. If I know that my LFSR diagram is correct based on information in the end table of XAPP052, then the verification part becomes simpler.

So the basic issue is not complicated, but because people do this in different ways, looking at all the examples has confused me. 

[BrianHG]

Note that my code is 2 different types of shift register with XOR bits at strategic location for maximum 'coverage' of a 32 bit random number.  My code's final output takes the 2 random number generators and XOR's them together for the final result.

Though I have not read the Xilinx paper, my guess they are trying to maximize numerical coverage for each number of bits you wish to have generated using the minimum number of shift registers, or in other words minimum ram bits.

With my random number generator, you may only want the bottom 16 or 8 bits.  There is no problem here as the result is still random, but, a lot of excess logic cells were used to generate the 32 bits.

What you are asking for it the theory behind PRNG (pseudo random number generators).  There are many places to look like google, wiki, even youtube.

Example, a google of 'verilog PRNG' gives you this first result:
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwianPe4lOzqAhW6mHIEHW0eBzMQFjAAegQIVRAB&url=http%3A%2F%2Frdsl.csit-sun.pub.ro%2Fdocs%2FPROIECTARE%2520cu%2520FPGA%2520CURS%2Flecture6%5B1%5D.pdf&usg=AOvVaw0v4KrRuZ8K90HQEZKmKu2R

Page by page, it will tell you how and why the 'Linear Feedback Shift Register' (LFSR - 1 of the two random number generators in my provided code) generates random numbers.

[miken]

One thing you can do to check a PRBS is to write something that checks if the output is maximal length. Do it in a testbench, or dump the sim and check it offline.

If you're interested more in _how_ random the bitstream is, there's stuff you can do with autocorrelation, but I can't really speak to that. I think NIST has documents.

[mfro]

Well the basic issue is when I started looking into generating random numbers inside FPGA to help in "randomly inject errors into the system during its run" I was blown away by the depth of the subject. There are so many ways to generate random numbers where some rely on real source for entropy while others just generate a pseudo-random sequence. I even found some PhD thesis on this subject and many research papers. This all was rather terrifying.

...

Wouldn't go with a 'true' RNG when it is for testing purposes as you might never be able to reproduce test results.
Go with pseudo-random (and don't forget to save away the seed).