Looking for good 32 bit pseudo RNG in SystemVerilog.

[BrianHG]

Well, open cores failed as their verilog 32bit pseudo random number gen is garbagely written and only makes a half repeating pattern with 0s coming up in regular patterns as seen using is to generate video white noise on a 2048x1080.  So much for their claim of being really random.

I need a good 150 million random 32 bit numbers a second.

Google has failed me to find something clean unless I will need to test everything I find.
Does anyone have anything good laying around.

[SMB784]

Why not a 32 bit LFSR pseudorandom number generator?  This will provide 2³²=4.3 billion random numbers, with a cycling time of that many clocks.  At 4 GHz it would take more than 1 second to run through all of the values

e.g.

Code: [Select]

module LFSR_rng
#(
)
(
    input logic clk,

    output logic [31:0] rand_out
);

logic [31:0] rand_ff=$urandom();

        always_ff @(posedge clk)
        begin
           rand_ff<={(rand_ff[31]^rand_ff[30]^rand_ff[10]^rand_ff[0]),rand_ff[31:1]};
           rand_out<=rand_ff
        end
endmodule

*** EDIT *** made clocked module

[BrianHG]

Testing... damn 10minute compile time for the project.

I have a dead LFSR 42bit one with bad xor coefficients and a 32 bit one like yours, but with different coefficients.
Let's see what yours produces.

[BrianHG]

Why not a 32 bit LFSR pseudorandom number generator?  This will provide 2³²=4.3 billion random numbers, with a cycling time of that many clocks.  At 4 GHz it would take more than 1 second to run through all of the values

Not possible with this formula.  It will repeat very rapidly.  Especially if the result is ever 0, it will always return 0 from that point on.  A good 32 bit random number generator needs to have at least 64 bits or 128 bits at it's core.

[BrianHG]

Your RND produces a greenish snow, meaning since I'm using the 32 bit output as 8bit A,R,G,B, bits 15 to 8, most likely 15 and 14 prefer to be high most of the time.  Random snow should average grey.

[SiliconWizard]

I haven't had to implement this in HDL so far. But I have in software on several occasions, and I have always used the same ever since I read about it and tested it: taken from the Art of Computer Programming (Knuth). Various statistical tests show this one has very good "randomness", despite its being extremely simple.

It only requires one adder (width same as the generated numbers.)
But it does require a memory of the 55 last generated numbers. It's not a lot, but see if it's OK in your case.
Those 55 values need to be initialized, so whereas a basic RNG requires only 1 seed number, this one requires 55. If you don't care about the sequence being always the same from reset, you can of course fill it with 55 pre-generated random values.

Should be pretty simple to implement in HDL.

The algorithm is described in Volume 2 (Seminumerical algorithms), "3.2.2. Other methods", Algorithm A (Additive number generator). If you don't have the book handy, I can post the algorithm. It's very simple.

[daqq]

How many resources do you have available? Look for common hash functions (MD5, SHA256...), take one or more round out of them and just feed them back into itself - loop the pipe. Then try tapping into the output. Ignore the 96 or more extra bits, just feed them into the loop. It'll be some time till that loops. Total overkill, but will work.

[BrianHG]

  This guy hasn't a clue how verilog or FPGAs work, he has a good formula, but, screwed up the implementation.  He didn't do proper testing of the individual components, otherwise he would have seen his LFSR section generates nothing but a tiny repetitive string of 1s and 0s every few hundred iterations in the same spot of bits.

https://opencores.org/projects/systemc_rng

This is his code: rng.v

Code: [Select]

//////////////////////////////////////////////////////////////////////
////                                                              ////
////  Random Number Generator                                     ////
////                                                              ////
////  This file is part of the SystemC RNG                        ////
////                                                              ////
////  Description:                                                ////
////                                                              ////
////  Implementation of random number generator                   ////
////                                                              ////
////  To Do:                                                      ////
////   - done                                                     ////
////                                                              ////
////  Author(s):                                                  ////
////      - Javier Castillo, javier.castillo@urjc.es              ////
////                                                              ////
////  This core is provided by Universidad Rey Juan Carlos        ////
////  [url]http://www.escet.urjc.es/~jmartine[/url]                          ////
////                                                              ////
//////////////////////////////////////////////////////////////////////
////                                                              ////
//// Copyright (C) 2000 Authors and OPENCORES.ORG                 ////
////                                                              ////
//// This source file may be used and distributed without         ////
//// restriction provided that this copyright statement is not    ////
//// removed from the file and that any derivative work contains  ////
//// the original copyright notice and the associated disclaimer. ////
////                                                              ////
//// This source file is free software; you can redistribute it   ////
//// and/or modify it under the terms of the GNU Lesser General   ////
//// Public License as published by the Free Software Foundation; ////
//// either version 2.1 of the License, or (at your option) any   ////
//// later version.                                               ////
////                                                              ////
//// This source is distributed in the hope that it will be       ////
//// useful, but WITHOUT ANY WARRANTY; without even the implied   ////
//// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      ////
//// PURPOSE.  See the GNU Lesser General Public License for more ////
//// details.                                                     ////
////                                                              ////
//// You should have received a copy of the GNU Lesser General    ////
//// Public License along with this source; if not, download it   ////
//// from [url]http://www.opencores.org/lgpl.shtml[/url]                     ////
////                                                              ////
//////////////////////////////////////////////////////////////////////
//
// CVS Revision History
//
// $Log: not supported by cvs2svn $
// Revision 1.3  2005/07/30 20:07:26  jcastillo
// Correct bit 28. Correct assignation to bit 31
//
// Revision 1.2  2005/07/29 09:13:06  jcastillo
// Correct bit 28 of CASR
//
// Revision 1.1  2004/09/23 09:43:06  jcastillo
// Verilog first import
//

`timescale 10ns/1ns

module rng(clk,reset,loadseed_i,seed_i,number_o);
input clk;
input reset;
input loadseed_i;
input [31:0] seed_i;
output [31:0] number_o;

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 or negedge reset)

   begin




   if (!reset )

      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

         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 or negedge reset)

   begin


   if (!reset )

      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

         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 or negedge reset)

   begin

   if (!reset )

      begin

      number_o  = (0);

      end

   else

      begin

      number_o  = (LFSR_reg [31:0]^CASR_reg[31:0]);

      end


   end

endmodule


I've changed his 'LFSR' portion to this:

Code: [Select]

         if (ena) begin

         LFSR_varLFSR [42]<=LFSR_varLFSR [41];
         LFSR_varLFSR [41]<=LFSR_varLFSR [40]^LFSR_varLFSR [42] ;
         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]^LFSR_varLFSR [42] ;
         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]^LFSR_varLFSR [42] ;
         LFSR_varLFSR [0] <=LFSR_varLFSR [42];

         end


At least now it generates a close to average grey semi fine snow instead of a scrolling blue weird tree pattern.  It's like he is confusing part C code with verilog parallel registers and he didn't bother to verify his results were truly non-pattern generating over millions of itterations.

I'm now debugging his CASR random number generator part.

It already looks far more random and balanced compared to SMB784's greenish chunky with circular waves scrolling through:

Code: [Select]

rand_ff<={(rand_ff[31]^rand_ff[30]^rand_ff[10]^rand_ff[0]),rand_ff[31:1]};

[BrianHG]

Wow, after patching his CASR section, it truly creates a fine snow.
Now to merge the 2 with the final XOR.

[BrianHG]

Ok, I can officially call this snow:

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;
always @(posedge clk ) begin

   if ( rst ) CASR_varCASR  <= (37'h21616D3EA9);
   else begin

         if (ena) begin
         CASR_varCASR [36]<=CASR_varCASR [35]^CASR_varCASR [0];
         CASR_varCASR [35]<=CASR_varCASR [34]^CASR_varCASR [36];
         CASR_varCASR [34]<=CASR_varCASR [33]^CASR_varCASR [35];
         CASR_varCASR [33]<=CASR_varCASR [32]^CASR_varCASR [34];
         CASR_varCASR [32]<=CASR_varCASR [31]^CASR_varCASR [33];
         CASR_varCASR [31]<=CASR_varCASR [30]^CASR_varCASR [32];
         CASR_varCASR [30]<=CASR_varCASR [29]^CASR_varCASR [31];
         CASR_varCASR [29]<=CASR_varCASR [28]^CASR_varCASR [30];
         CASR_varCASR [28]<=CASR_varCASR [27]^CASR_varCASR [29];
         CASR_varCASR [27]<=CASR_varCASR [26]^CASR_varCASR [27]^CASR_varCASR [28];
         CASR_varCASR [26]<=CASR_varCASR [25]^CASR_varCASR [27];
         CASR_varCASR [25]<=CASR_varCASR [24]^CASR_varCASR [26];
         CASR_varCASR [24]<=CASR_varCASR [23]^CASR_varCASR [25];
         CASR_varCASR [23]<=CASR_varCASR [22]^CASR_varCASR [24];
         CASR_varCASR [22]<=CASR_varCASR [21]^CASR_varCASR [23];
         CASR_varCASR [21]<=CASR_varCASR [20]^CASR_varCASR [22];
         CASR_varCASR [20]<=CASR_varCASR [19]^CASR_varCASR [21];
         CASR_varCASR [19]<=CASR_varCASR [18]^CASR_varCASR [20];
         CASR_varCASR [18]<=CASR_varCASR [17]^CASR_varCASR [19];
         CASR_varCASR [17]<=CASR_varCASR [16]^CASR_varCASR [18];
         CASR_varCASR [16]<=CASR_varCASR [15]^CASR_varCASR [17];
         CASR_varCASR [15]<=CASR_varCASR [14]^CASR_varCASR [16];
         CASR_varCASR [14]<=CASR_varCASR [13]^CASR_varCASR [15];
         CASR_varCASR [13]<=CASR_varCASR [12]^CASR_varCASR [14];
         CASR_varCASR [12]<=CASR_varCASR [11]^CASR_varCASR [13];
         CASR_varCASR [11]<=CASR_varCASR [10]^CASR_varCASR [12];
         CASR_varCASR [10]<=CASR_varCASR [9] ^CASR_varCASR [11];
         CASR_varCASR [9] <=CASR_varCASR [8] ^CASR_varCASR [10];
         CASR_varCASR [8] <=CASR_varCASR [7] ^CASR_varCASR [9];
         CASR_varCASR [7] <=CASR_varCASR [6] ^CASR_varCASR [8];
         CASR_varCASR [6] <=CASR_varCASR [5] ^CASR_varCASR [7];
         CASR_varCASR [5] <=CASR_varCASR [4] ^CASR_varCASR [6];
         CASR_varCASR [4] <=CASR_varCASR [3] ^CASR_varCASR [5];
         CASR_varCASR [3] <=CASR_varCASR [2] ^CASR_varCASR [4];
         CASR_varCASR [2] <=CASR_varCASR [1] ^CASR_varCASR [3];
         CASR_varCASR [1] <=CASR_varCASR [0] ^CASR_varCASR [2];
         CASR_varCASR [0] <=CASR_varCASR [36]^CASR_varCASR [1];
         end
      end
   end
//LFSR:
reg[42:0] LFSR_varLFSR;
always @(posedge clk) begin

   if ( rst ) LFSR_varLFSR  <= (43'h2264311BAA6);
   else begin

         if (ena) begin

         LFSR_varLFSR [42]<=LFSR_varLFSR [41];
         LFSR_varLFSR [41]<=LFSR_varLFSR [40]^LFSR_varLFSR [42] ;
         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]^LFSR_varLFSR [42] ;
         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]^LFSR_varLFSR [42] ;
         LFSR_varLFSR [0] <=LFSR_varLFSR [42];

         end
      end
   end

//combinate:
always @(posedge clk) begin
   if ( rst )    number_o  <= (0);
   else if (ena) number_o  <= (LFSR_varLFSR [31:0]^CASR_varCASR[31:0]);
end
endmodule


It's basically a corrected interpretation of the code given on open-cores:
https://opencores.org/projects/systemc_rng

(I do realize I could have simplified the to generators down to a single line...)

[SMB784]

Why not a 32 bit LFSR pseudorandom number generator?  This will provide 2³²=4.3 billion random numbers, with a cycling time of that many clocks.  At 4 GHz it would take more than 1 second to run through all of the values

Not possible with this formula.  It will repeat very rapidly.  Especially if the result is ever 0, it will always return 0 from that point on.  A good 32 bit random number generator needs to have at least 64 bits or 128 bits at it's core.

This sequence of taps should correspond to a maximum length LFSR sequence, i.e. 2³²-1 numbers, assuming the seed number isn't 0. See just above example C in this Wikipedia article:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register#%3A%7E%3Atext%3DA_maximum-length_LFSR_produces%2Ccase_it_will_never_change.?wprov=sfla1

Perhaps I have implemented the taps wrong though.

[BrianHG]

Why not a 32 bit LFSR pseudorandom number generator?  This will provide 2³²=4.3 billion random numbers, with a cycling time of that many clocks.  At 4 GHz it would take more than 1 second to run through all of the values

Not possible with this formula.  It will repeat very rapidly.  Especially if the result is ever 0, it will always return 0 from that point on.  A good 32 bit random number generator needs to have at least 64 bits or 128 bits at it's core.

This sequence of taps should correspond to a maximum length LFSR sequence, i.e. 2³²-1 numbers, assuming the seed number isn't 0. See just above example C in this Wikipedia article:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register#%3A%7E%3Atext%3DA_maximum-length_LFSR_produces%2Ccase_it_will_never_change.?wprov=sfla1

Perhaps I have implemented the taps wrong though.

Not even close.  0 is a possible random number, and it the generator cannot produce it, it's not random.
If 0 is hit, your generator will get stuck.

Your generator clearly made fat blobbish green like pixels though it was kinda grainy.
the video had an angular pattern scrolling through it showing a pattern and degree of repeatability.

Tanking the bottom 32 bits of the above posted 43 bit LFSR, once I corrected the coding, generated an average gray white noise with twice as fine pixels as yours.  Though there was a hint of repeatability.  The bottom 32 bits of the 37 bit CASR generator made a really fine, super sharp average white snow, but you could tell there was a faint background pattern scrolling to the left through the video.  The combo XOR of the LFSR and CASR really made a random snow with no discernible pattern in the video.

[BrianHG]

I'm happy with the combo 43 LFSR & 37 bit CASR generator.  I'll have my DDR3 ram controller up in a day or two using the generator to drive a 1080p 32 bit color HDMI out demo with 2D drawing effects on Arrow's Deca board.

[RoGeorge]

How about a true random generator:

This paper will present a solution to this  problem  that  uses  only  digital  logic  and  does  not  rely  on  any  external  analog  components that could become subject to an attack and compromise the security of the  generated  numbers.  A  very  efficient  implementation  in  Xilinx  FPGAs  that  can  produce 32-bit random numbers at rates of up to 500MHz is presented

Source:  http://forums.xilinx.com/xlnx/attachments/xlnx/EDK/27322/1/HighSpeedTrueRandomNumberGeneratorsinXilinxFPGAs.pdf

[SMB784]

Not even close.  0 is a possible random number, and it the generator cannot produce it, it's not random.
If 0 is hit, your generator will get stuck.

Your generator clearly made fat blobbish green like pixels though it was kinda grainy.
the video had an angular pattern scrolling through it showing a pattern and degree of repeatability.

Tanking the bottom 32 bits of the above posted 43 bit LFSR, once I corrected the coding, generated an average gray white noise with twice as fine pixels as yours.  Though there was a hint of repeatability.  The bottom 32 bits of the 37 bit CASR generator made a really fine, super sharp average white snow, but you could tell there was a faint background pattern scrolling to the left through the video.  The combo XOR of the LFSR and CASR really made a random snow with no discernible pattern in the video.

I don't know the exact implementation you are using the 32bit LFSR for, and I'm also not familiar with the green blobs that you mention, but I'm glad that you have discovered a solution that will work.

The LFSR not generating 0 is just a fact of LFSRs. (https://en.wikipedia.org/wiki/Maximum_length_sequence?wprov=sfla1). A 43bit LFSR is no different in this regard. This is why it is a pseudorandom number generator - it doesn't generate truly random numbers, which would naturally include 0. However, for large LFSRs, this basically doesn't matter, given that 0 is just one number in a field of billions to trillions for large LFSRs

On a different note, what seed number are you using? I have found that $urandom() doesn't always work correctly, so you may have to give it an explicitl random seed.

[hamster_nz]

Obvious:

Just invert the output to get pseudo random numbers between 0 and 2^n-2.

Maybe less obvious:

The raw output of a LFSR-based PRNG can't be even close to random - each output value is only generated once during the entire cycle.  So for a maximal 16-bit LFSR if you have generated the number "1235" you can be sure that any of the next 65534 iterations you will not see 1235 . The more numbers you generate, the more you know about the pool of numbers that is left to be generated, and when the numbers will next appear.

Even less obvious answer:

Take the DFT of the output of a maximal LFSR bitstream (where a '0' is taken as y=-1 and a '1' is taken as y=1) and see if that looks at all random.

This is also why the DC / 0Hz value of 0.5*(2^n-1)  (or -0.5*(2^n-1)) is 'correct' if using the LFSR as a noise source.

[BrianHG]

The LFSR not generating 0 is just a fact of LFSRs. (https://en.wikipedia.org/wiki/Maximum_length_sequence?wprov=sfla1). A 43bit LFSR is no different in this regard. This is why it is a pseudorandom number generator - it doesn't generate truly random numbers, which would naturally include 0. However, for large LFSRs, this basically doesn't matter, given that 0 is just one number in a field of billions to trillions for large LFSRs

I never asked for true randomness, just that the result should be random like.
The 43bit LFSR allows 0 as a result on the 32 bit LSBs since the upper hidden bits do not need to be at the same time, so 0 on bits 31:0 wont kill the generator.

Rotating 32 bits with 4 xor points isn't enough and seems to favor strings of '011's or '110's between bits 10 & 29 as the color of my snow was tinted green.

Your LFSR just wasn't wide enough and alone, even the 42bit one I has also has a characteristic to the snow, though it's average color was gray.  Xor-ing it with the CASR make the result truly like an old analog TV tuned to an empty station, except the snow was colored.

Again, using the CASR alone would look like as if an analog HDTV would have been tuned into some high frequency snow, but just artificially overkill on it's own.


If you arent going to plot these generators continuously on 8mgabyte graphic display, just picking 2 adjacent numbers from the generator will look random.


Also, for your 32bit number generator, whatever number goes in, the next one is always guaranteed to be the same.  So, at 4GHz, in theory I should see every 32 bit number, right?

This wont happen as the LFSR generators do not achieve 100% coverage.  Also randomness means with only 1 pass, there should be a good percentage of repeats.  The extra bits with a 42bit LFSR allow for some of these circumstances when operating with only the first 32 bits, though it is still not enough.

[BrianHG]

Obvious:

Just invert the output to get pseudo random numbers between 0 and 2^n-2.

Maybe less obvious:

The raw output of a LFSR-based PRNG can't be even close to random - each output value is only generated once during the entire cycle.  So for a maximal 16-bit LFSR if you have generated the number "1235" you can be sure that any of the next 65534 iterations you will not see 1235 . The more numbers you generate, the more you know about the pool of numbers that is left to be generated, and when the numbers will next appear.

Even less obvious answer:

Take the DFT of the output of a maximal LFSR bitstream (where a '0' is taken as y=-1 and a '1' is taken as y=1) and see if that looks at all random.

This is also why the value of 0.5*(2^n-1)  (or -0.5*(2^n-1)) is 'correct' if using the LFSR as a noise source.

Thanks.

[emece67]

.

[filssavi]

Apparently the OP has fulfilled his need, but I want to note that it is possible to build true RNGs in FPGAs. I've used them to simulate noise (not on images, though) and they worked and were also capable to pass the Dieharder and NIST tests.

Regards.

Just out of curiosity what type or TRNG implementation have you used?

I assume you used free running oscillators as a source of entropy, maybe seeding something like a mersenne twister for throughput…

Are my guess correct (if you can speak about it of course)

[Canis Dirus Leidy]

Speaking about LFSR and randomness. There are methods using multiple LFSRs (1), such as "stop-and-go generator", Hollmann's cascade or just several parallel LFSRs, like in this Gaussian noise generator.

1. In Russian, but I think that the skeleton diagrams are obvious.

[FenTiger]

I'm coming in late to this thread, perhaps, but I've had some success with this one: https://www.alexforencich.com/wiki/en/\verilog/mersenne/readme

I did have to make a couple of fixes to it; I'll dig them out if anyone's interested.

(Edit: fixed the link; thanks rstofer!)

[emece67]

.

[rstofer]

I'm coming in late to this thread, perhaps, but I've had some success with this one: https://www.alexforencich.com/wiki/en/\erilog/mersenne/readme

I did have to make a couple of fixes to it; I'll dig them out if anyone's interested.

That link is missing a 'v' in \verilog

https://www.alexforencich.com/wiki/en/\verilog/mersenne/readme

[BrianHG]

For whoever is interested, I've cleaned up the random code, here it is:

The pipeline for the random numbers is 2 unless you make the 'out <= ... ' into an always_comb.

Code: [Select]

module rnd ( clk, rst, ena, load, seed, out );

input             clk, rst, ena, load;
input      [31:0] seed ;
output reg [31:0] out ;

reg[36:0] CASR;
reg[42:0] LFSR;
always @(posedge clk ) begin

   if ( rst ) begin

                    CASR  <= (37'h1);  // Random starting point.
                    LFSR  <= (43'h1); // Random starting point.

   end else if (load) begin

                    CASR  <= 37'(seed) | 33'h100000000 ; // Load seed, protect from a seed of 0.
                    LFSR  <= 43'(seed) | 33'h100000000 ; // Load seed, protect from a seed of 0.

   end else if (ena) begin

                    CASR[36:0] <= ( {CASR[35:0],CASR[36]} ^ {CASR[0],CASR[36:1]} ^ CASR[27]<<27 ) ;
                    LFSR[42:0] <= ( {LFSR[41:0],LFSR[42]} ^ LFSR[42]<<41 ^ LFSR[42]<<20 ^ LFSR[42]<<1 ) ;

                    out [31:0] <= ( LFSR [31:0] ^ CASR[31:0] );

    end
end
endmodule