A uniform pseudo-random number generator.

[hamster_nz]

I'm doing something similar to this paper: "A Hardware Gaussian Noise Generator Using
the Box-Muller Method and Its Error Analysis" ( https://escholarship.org/content/qt5073r31q/qt5073r31q.pdf ).

The PRNG used, the Tausworthe URNG, caught my interest. It looks to be three LFSRs of different periods, XORed together to improve the RNG's performance:

Code: [Select]

uint32_t tausworthe(void) {
   static uint32_t s0=0xFFFFFFFFU, s1=0xFFFFFFFFU, s2=0xFFFFFFFFU;

   s0 = ((s0 & 0xFFFFFFFE) << 12) ^ (((s0 <<13)  ^  s0) >> 19);
   s1 = ((s1 & 0xFFFFFFF8) <<  4) ^ (((s1 << 2)  ^  s1) >> 25);
   s2 = ((s2 & 0xFFFFFFF0) << 17) ^ (((s2 << 3)  ^  s2) >> 11);
   return s0 ^ s1 ^ s2;
}

Converting the C code to HDL was mind bending for me due to the bit-shifts followed with masks, where HDL is usually bit slices followed by shifts.

Here is my VHDL implementation, verified to generate the same numbers as the original C code image in the PDF:

Code: [Select]

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
entity prng is
    Port (
        clk    : in  STD_LOGIC;
        random : out STD_LOGIC_VECTOR(31 downto 0) := (others => '0')
    );
end prng;

architecture Behavioral of prng is
    constant zero : STD_LOGIC_VECTOR(31 downto 0) := (others => '0');
    signal s0     : STD_LOGIC_VECTOR(31 downto 0) := (others => '1');
    signal s1     : STD_LOGIC_VECTOR(31 downto 0) := (others => '1');
    signal s2     : STD_LOGIC_VECTOR(31 downto 0) := (others => '1');
begin

process(clk)
    begin
        if rising_edge(clk) then
            random <= s0 XOR s1 XOR s2;
            s0 <= (s0(19 downto 1) & s0(31 downto 19)) XOR (zero(31 downto 13) & s0(18 downto  6));
            s1 <= (s1(27 downto 3) & s1(31 downto 25)) XOR (zero(31 downto  7) & s1(29 downto 23));           
            s2 <= (s2(14 downto 4) & s2(31 downto 11)) XOR (zero(31 downto 21) & s2(28 downto  8));   
        end if;
    end process;

end Behavioral;

Anyhow, maybe this 32-bit PRNG will be just what somebody needs.

[SiliconWizard]

You could generate a sequence and submit it to: http://cacert.at/random/
to see how well it fares compared to many other RNGs.

The latest PRNG I've used was the xoshiro256++ which is pretty good while being fast in software: https://prng.di.unimi.it/
I submitted it to the above and it got very good results for almost all tests they use. I'm using it, among other things, to generate UUIDs.

I haven't implemented it in VHDL yet, but it should not be difficult.

[hamster_nz]

You could generate a sequence and submit it to: http://cacert.at/random/
to see how well it fares compared to many other RNGs.

The latest PRNG I've used was the xoshiro256++ which is pretty good while being fast in software: https://prng.di.unimi.it/
I submitted it to the above and it got very good results for almost all tests they use. I'm using it, among other things, to generate UUIDs.

I haven't implemented it in VHDL yet, but it should not be difficult.

Submitted, and results are:

Code: [Select]

Generator:        Tausworthe URNG VHDL
Vendor:           Hamsterworks
Speed:            800000000 B/s
Price:            $0 USD
Upload Size:      38 MiB
Entropy (→8)      7.999995
Birthday Spacing  0.386248
Matrix Ranks      0.281
6x8 Matrix Ranks  0.286
Minimum Distance  0.875483
Random Spheres    0.593999
The Sqeeze        0.660390
Overlapping Sums  0.054484
Submission date   2022-06

All tests passed 

Even after reading https://en.wikipedia.org/wiki/Diehard_tests I still have no ideas of what these numbers actually mean, other than the results do not indicate a problem. 

[emece67]

.

[RoGeorge]

Yep.  Pseudo random is advantageous in a software/algorithmic generator.  In an FPGA, it's easy to get true randomness.  Once you have a true random of whatever distribution (biased TRNG), those numbers can be turned into an uniform distribution (mathematically guaranteed unbiased TRNG) by applying Von Neumann's debiasing algorithm
https://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor
https://mathoverflow.net/questions/152107/proof-of-von-neumanns-debiasing-algorithm

Once you have an unbiased (uniform distributed) TRNG, you can generate true random numbers in any desired distribution (custom TRNG), something like this:
https://programming.guide/generate-random-value-with-distribution.html
https://programming.guide/random-point-within-circle.html

That's very cool, one day I'll build one, though no idea what for to use that.   

[DiTBho]

no matter what algorithm you try to implement, if you believe in "super determinism", there will always be a break in the distribution of numbers, which means that the Universe itself is a pseudo-random generator.

So why not just put in an antenna to hear its breath?

[radiolistener]

Inside an FPGA it is even possible to implement true RNG. See:

• Majzoobi, M., Koushanfar, F., Devadas, S. (2011). FPGA-Based True Random Number Generation Using Circuit Metastability with Adaptive Feedback Control. In: Preneel, B., Takagi, T. (eds) Cryptographic Hardware and Embedded Systems – CHES 2011. CHES 2011. Lecture Notes in Computer Science, vol 6917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23951-9_2
  
• X. Xu and Y. Wang, "High Speed True Random Number Generator Based on FPGA," 2016 International Conference on Information Systems Engineering (ICISE), 2016, pp. 18-21, doi: 10.1109/ICISE.2016.14

Tested both methods and, well, both work.

Cannot open link, can you share code example?

[RoGeorge]

no matter what algorithm you try to implement, if you believe in "super determinism", there will always be a break in the distribution of numbers, which means that the Universe itself is a pseudo-random generator.

Could be, but I don't believe in Superdeterminism.  However, I suspect that the Bell's Theorem is flawed, because one can get a curved shape distribution instead of straight lines shape (triangle) distribution if we admit there is a hidden variable + noise.

The whole reasoning in the Bell's theorem is we see curved and not straight line probability distribution, therefore there couldn't be any hidden variable (when talking about quantum entanglement).  But there is yet another possibility, that we see the curved distribution because of noise.

I think this paper is a hint that the curved shape we measure might be on the contrary, because of the existing hidden variable plus some measuring noise, while the the Bell's theorem implies the curve means there can be no hidden variable:

Robert H. McEachern, September 2016:  A Classical System for Producing “Quantum Correlations”
https://vixra.org/pdf/1609.0129v1.pdf

(Note that the paper is hosted on viXra, not to be confused with arXiv.)

McEachern is an astrophysicist, sometimes commenting in online discussions about quantum mechanics.  That's how I found out about his papers.  I'm not a physicist, but his papers seem to me more plausible than the mainstream. 
https://vixra.org/author/robert_h_mceachern

[RoGeorge]

Cannot open link

Try searching the DOI (or the title) on sci-hub.

[radiolistener]

Try searching the DOI (or the title) on sci-hub.

Digital Object Identifier? I have no idea what is relation with hardware noise generator?

can you please share verilog code?

Currently I'm using this one, but this is a classic LFSR noise generator with very good but synthetic noise.
It will be very interesting to try a real noise generator

Code: [Select]

module LFSR(clk, reset, data);
parameter SEED = 32'b10101011101010111010101110101011;// LFSR starting state
parameter TAPS = 31'b0000000000000000000000001100010;// LFSR feedback taps

input clk;
input reset;
output data;

reg [31:0] shift_register;
initial shift_register = SEED;

always @(posedge clk) begin
if(!reset) begin
// feedback 1,5,6
if(shift_register[31])
shift_register[31:1] <= shift_register[30:0]^TAPS;
else
shift_register[31:1] <= shift_register[30:0];

// feedback 31
shift_register[0] <= shift_register[31];
end else begin
// reset seed
shift_register <= SEED;
end
end

        // clock out random bits from the end of the register
assign data = shift_register[31];
endmodule


With a small mod, I'm using it to produce 14 bit noise in one cycle for testing my DSP chain:

Code: [Select]

module ADC_LFSR(clk, reset, data, data14);
...
    output [13:0] data14;
    reg [13:0] accu14;

    always @(posedge clk) begin
        case (shift_register[31:30])
            0: accu14 <= accu14 ^ shift_register[31:18] ^ (shift_register[18:5]) ^ (shift_register[20:7]) ^ 14'h2a57;
            1: accu14 <= accu14 ^ shift_register[31:18] ^ (shift_register[26:13]) ^ (shift_register[29:16]) ^ 14'h1391;
            2: accu14 <= accu14 ^ shift_register[31:18] ^ (shift_register[13:0]) ^ (shift_register[18:5]) ^ 14'h0628;
            3: accu14 <= accu14 ^ shift_register[31:18] ^ (shift_register[15:2]) ^ (shift_register[21:8]) ^ 14'h3f42;
        endcase
    end
    assign data14 = accu14;

there is nothing special, I just added some random shifts and xors to generate additional 14 bits.

The first picture is a spectrum for 1-bit noise used to select min and max value of 14 bit.
The second picture is a spectrum with noise all 14 bits.

By the way, does anyone knows what is theoretical maximum noise floor level for discrete signal? I never seen such info in literature...

If you see on spectrum plots, it's about -36 dBFS for the second picture which corresponds with processing gain for FFT size 8192 = 1-*log10(8192/2) = 36 dB. But the first picture shows -30 dBFS noise for the same FFT size...

[RoGeorge]

Inside an FPGA it is even possible to implement true RNG. See:

• Majzoobi, M., Koushanfar, F., Devadas, S. (2011). FPGA-Based True Random Number Generation Using Circuit Metastability with Adaptive Feedback Control. In: Preneel, B., Takagi, T. (eds) Cryptographic Hardware and Embedded Systems – CHES 2011. CHES 2011. Lecture Notes in Computer Science, vol 6917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23951-9_2
  
• X. Xu and Y. Wang, "High Speed True Random Number Generator Based on FPGA," 2016 International Conference on Information Systems Engineering (ICISE), 2016, pp. 18-21, doi: 10.1109/ICISE.2016.14

Tested both methods and, well, both work.

Cannot open link, can you share code example?

Digital Object Identifier? I have no idea what is relation with hardware noise generator?

I thought you can not open the link present in the paragraph you quoted:  https://doi.org/10.1007/978-3-642-23951-9_2

That link is to a paper, usually behind a paywall.  However, most of the papers can be reached if you open any sci-hub mirror, for example https://sci-hub.se/ and inside the sci-hub webpage, search the DOI of that paper from the link:  10.1007/978-3-642-23951-9_2 (the part coming after doi.org in the original link, that's the DOI id of that published article), and you'll get this pdf paper:  https://sci-hub.se/10.1007/978-3-642-23951-9_2 same paper you couldn't open from the original link, https://doi.org/10.1007/978-3-642-23951-9_2

If that paper has code inside or not, I don't know.  The paper is about a hardware noise generator.

[radiolistener]

That link is to a paper, usually behind a paywall.  However, most of the papers can be reached if you open any sci-hub mirror, for example https://sci-hub.se/ and inside the sci-hub webpage, search the DOI of that paper from the link:  10.1007/978-3-642-23951-9_2 (the part coming after doi.org in the original link, that's the DOI id of that published article), and you'll get this pdf paper

Thanks, I didn't know that way to obtain pdf with research papers. It works, I downloaded it.

[rstofer]

So why not just put in an antenna to hear its breath?

It has already been done and it was started a long time ago with the US DOD.  There's a bunch of replies to a Google search but here's just one:

https://www.zdnet.com/article/start-up-generates-random-numbers-from-space-5000150584/

[radiolistener]

I think TDC (Time-to-Digital Converter) approach with a long delay chain on FPGA can be also used to capture self-jitter noise of FPGA gates.

[RoGeorge]

So why not just put in an antenna to hear its breath?

It has already been done...

Say no more, I forgot I did something similar once, just that it was a thermal "antenna"  .  Discovered it accidentally, while I was testing a very sensitive thermometer chip from TI (TMP112, 0.0625°C resolution).  Turned out it can detect if one is still breathing only by the air temperature:  https://hackaday.io/project/2823-how-are-you-errr-are-you-alive

https://www.zdnet.com/article/start-up-generates-random-numbers-from-space-5000150584/

The linked article reminds me of this hypnotic TRNG with lava lamps:


Though, the OP method can generate way more faster. 

[BrianHG]

Here is the one I have been using:

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'h100000000); // Random starting point.
                    LFSR  <= (43'h100000000); // 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
It takes 2 clocks from loading the 'seed' until the first output is valid.  New 32bit number on every clock.

[radiolistener]

I want to implement TRNG noise generator based on metastable ring oscillators.
But I don't understand how to implement metastable ring oscillator in verilog for Intel/Altera Cyclone 4.

I found code for Lattice ECP5, but how to implement the same for Intel/Altera Cyclone 4?
Can someone help please?

Code: [Select]

module ringoscillator(output wire chain_out);

// ???

endmodule


[Nominal Animal]

One of the best LFSR PRNGs is the highest 32 bits of Xorshift64*.  It uses a 64-bit nonzero state.

In C:

Code: [Select]

static uint64_t  xorshift64_state = 1; /* Any nonzero 64-bit value */

uint32_t  xorshift64_u32(void)
{
    uint64_t  x = xorshift64_state;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    xorshift_state = x;
    return (x * UINT64_C(2685821657736338717)) >> 32;
}

Thus, the state update is very simple,

Code: [Select]

    state[63:52] <= state[38:27];
    state[51:37] <= state[63:49] ^ state[26:12];
    state[36:25] <= state[63:52] ^ state[48:37] ^ state[11:0];
    state[24:0]  <= state[36:12] ^ state[51:27];
and each 32-bit output value is mixed from the 32 high bits of the state via two 32×32=32-bit multiplications and one 32-bit sum, after each state update,

Code: [Select]

    output[31:0] <= state[63:32] * 0x4F6CDD1D + state[31:0] * 0x2545F491;
This passes all BigCrush tests without any failures, the period is 2⁶⁴-1, and the output contains all 32-bit values.

Personally, I'd keep the state one step advanced (i.e. when setting the seed, do one state iteration as above), then:

Code: [Select]

    output[31:0] <= state[63:32] * 0x4F6CDD1D + state[31:0] * 0x2545F491;
    state[63:52] <= state[38:27];
    state[51:37] <= state[63:49] ^ state[26:12];
    state[36:25] <= state[63:52] ^ state[48:37] ^ state[11:0];
    state[24:0]  <= state[36:12] ^ state[51:27];
for each cycle.

[MK14]

This passes all BigCrush tests without any failures

At least one source, seems to claim, that it doesn't do so well, with the MatrixRank test.

https://forum.mikrotik.com/viewtopic.php?t=100868

On the other hand, if you only take the top 32 bits of the value, maybe that changes things ?

[Nominal Animal]

This passes all BigCrush tests without any failures

At least one source, seems to claim, that it doesn't do so well, with the MatrixRank test.

https://forum.mikrotik.com/viewtopic.php?t=100868

The full 64-bit output passes all except MatrixRank in BigCrush.
Taking the top 32 bits only, makes the output pass all in BigCrush, including MatrixRank.

See e.g. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, a technical report by Melissa E. O'Neill, 2014; page 9: "Also of note, RanQ1 [ 42 ] and XorShift* 64/32 are essentially the exact same generator, yet the former fails the test suite and the latter passes. The difference is that the former markets itself as a 64-bit generator and fails because its low-order bits are weak, whereas the latter only returns the top 32 bits. The method that underlies this generator is notable because it follows a similar strategy to the one I will advocate in this paper: it uses a generator with known weaknesses (XorShift), and then applies an improvement step to the numbers it generates."
It is common for many LFSR PRNGs to have deficiencies in the least significant bits.  Since otherwise the family is well researched and its behaviour known, the advocated approach is valid.

In other words, the output of the C code in my above post does pass all tests in BigCrush, including MatrixRank.  The FPGA code I haven't verified (it's a straightforward implementation of the C code, without expanding the multiplication "mix" step; noting that the multiplication is done only on the output, not on the state itself).

[MK14]

This passes all BigCrush tests without any failures

At least one source, seems to claim, that it doesn't do so well, with the MatrixRank test.

https://forum.mikrotik.com/viewtopic.php?t=100868

The full 64-bit output passes all except MatrixRank in BigCrush.
Taking the top 32 bits only, makes the output pass all in BigCrush, including MatrixRank.

See e.g. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, a technical report by Melissa E. O'Neill, 2014; page 9: "Also of note, RanQ1 [ 42 ] and XorShift* 64/32 are essentially the exact same generator, yet the former fails the test suite and the latter passes. The difference is that the former markets itself as a 64-bit generator and fails because its low-order bits are weak, whereas the latter only returns the top 32 bits. The method that underlies this generator is notable because it follows a similar strategy to the one I will advocate in this paper: it uses a generator with known weaknesses (XorShift), and then applies an improvement step to the numbers it generates."
It is common for many LFSR PRNGs to have deficiencies in the least significant bits.  Since otherwise the family is well researched and its behaviour known, the advocated approach is valid.

In other words, the output of the C code in my above post does pass all tests in BigCrush, including MatrixRank.  The FPGA code I haven't verified (it's a straightforward implementation of the C code, without expanding the multiplication "mix" step; noting that the multiplication is done only on the output, not on the state itself).

Thanks for the update.  The report you linked to, may have a mistake in it, around your ranQ1 ideas.  I'm NOT 100% sure.  But by looking at many references, it would seem that the ranQ1, also fails that or some tests.
The possible mistake surrounding your link, is that it was not really ranQ1, they were talking about, but a slightly modified version, which DOES pass all tests.  Because it had a final step (NOT the >>32 part, but from another rnd generator), which improved its quality of output.

Sorry that I can't be more clear.  Because the main reference source, doesn't seem to have a freely available version, so I can't get it (NOT your link, but the original source, in a journal or similar).  Also, there are some slight discrepancies between different sources.

[iMo]

I want to implement TRNG noise generator based on..

Based on the paper you have to master the metastability of a single inverter (LUT based) in the FPGA first.  They also note that it is not easy in most cases, therefore they invented a new special structure for the generator to be implemented on the chip..

[MK14]

From https://github.com/blackstonep/Numerical-Recipes/blob/master/ran.h

Code: [Select]

struct Ranq1 {
Ullong v;
Ranq1(Ullong j) : v(4101842887655102017LL) {
v ^= j;
v = int64();
}
inline Ullong int64() {
v ^= v >> 21; v ^= v << 35; v ^= v >> 4;
return v * 2685821657736338717LL;
}
inline Doub doub() { return 5.42101086242752217E-20 * int64(); }
inline Uint int32() { return (Uint)int64(); }
};
That seems to be the original.

So sorry, maybe your step (Nominal_Animal), does fix it.  It has been tricky following the various internet sources I found.

I thought the >>32 bit shift, was already included in the algorithm, itself.

EDIT: My mistake, you were right all along, Nominal Animal!
It took a lot of searching on my part, to clarify the situation, with some confusing bits, here and there.

Taking just the top 32 bits, DOES fix the issues with the bigcrush.

If the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures.[10]: 7 

Source:  https://en.wikipedia.org/wiki/Xorshift

[Nominal Animal]

No worries, but let me clarify a bit:

RanQ1 is a LFSR with 64 bits of state, three multibit shifts and xors per iteration, with a multiplication mixing stage.
Xorshift64* is a LFSR with 64 bits of state, three multibit shifts and xors per iteration, with a multiplication mixing stage.
That makes them "essentially the same", although the shifts are different, and they generate different sequences.

RanQ1 originates in Numerical Recipes, and fails both MatrixRank and BirthdaySpacings test of the BigCrush suite.
Xorshift64* uses different shift counts and mixing multiplier, and fails only MatrixRank test of the BigCrush suite.
George Marsagllia described the Xorshift family of PRNGs in 2003.

What I showed above, was the Xorshift64*/32 variant, that generates 64 bits of state each iteration, of which only the 32 highest bits are used.

Note that xoshiro256+ has a similar deficiency, albeit only in the three lowest bits.
The creators' paper at arxiv describes the behaviour of the family of generators in the BigCrush test suite, and xoshiro256++ passes all BigCrush tests (in a 10¹⁵-byte test).  The xoshiro family was designed as a successor to xorshift, and unless weaknesses are found in it, I too will likely shift to it (because it is faster).  The reason I haven't shifted yet is that they xoshiro family is relatively new: xoshiro256++ from 2019, compared to xorshift64* from 2003.  Marsaglia's original xorshift family has been more thoroughly investigated; xorshift64* is the 12,25,27 variant of the 275 64-bit ones listed in the article.

It is interesting to note that these actually behave better than Mersenne Twister, often considered the gold standard for numerical simulations (my own field).  These are also fast as all hell, with cache footprints so small that other cache-heavy computations are not really affected at all (unlike MT19937/MT19937-64, which has about 2.5KiB of state, with different cachelines accessed in sequence, and entire state regenerated per cycle though the state).

It is important to realize that even though these are "random", they are not unpredictable when given a sequence of generated numbers.  Someone who knows sufficiently many sequential generated numbers can still predict new values.  The fact that xorshift64*/32 only returns the high 32 bits makes that harder, but not impossible.  Really unpredictable PRNGs are called cryptographically secure PRNGs, and are quite different beasts.  For that, I recommend something like ChaCha20.  There is a SystemVerilog implementation of ChaCha20 licensed under the permissive MIT license.  You can also find other projects and thesis works on that subject using a web search.

[MK14]

Thanks for another great, and very informative post.  The cryptographic one (ChaCha20), looks interesting.  It's much faster, later Blake3 variant, even more so.
The ChaCha20, seems (by quick observations of the code) much faster, than what I was expecting, for non-built-in-hardware (of the CPU), cryptographic generators.

Fortunately, for most applications, non-cryptographic random number generators, are fine.