6
\$\begingroup\$

I'm building an FPGA feed handler and one of the problems is I want to do Monte-Carlo simulations which require a high-quality entropy source, i.e. a pseudo-random LSR implementation won't do. I've read that one can try using metastability as a source of randomness, does anyone do this, is this a viable option?

Also, since FPGAs have external clock inputs, can those be leveraged by some hardware "true RNG" solution? Do such solutions exist on the market?

\$\endgroup\$
  • 1
    \$\begingroup\$ Atmel have a range of HRNG chips, "ATSHA204A" is one such device. If you want a high frequency stream of such random data then you'll probably have to look into "avalanche noise". \$\endgroup\$ – Wossname Oct 15 '16 at 11:31
  • 3
    \$\begingroup\$ It's easy to put enough degrees of freedom into an LSR based PRN to make it suitable for Monte Carlo (of course not for crypto), and the benefit of being able to replay it makes fault-finding unexpected results possible. Don't use a single LSR, but multiple ones of different mutually prime lengths, and XOR the results. You can put a lot of LSR stages on an FPGA. \$\endgroup\$ – Neil_UK Oct 15 '16 at 12:14
  • \$\begingroup\$ You can make oscillators out of inverter rings in FPGAs, frequency depends on the layout and temperature. Maybe by combining many such oscillators as sources for a more tranditional pseudorandom generator. \$\endgroup\$ – TEMLIB Oct 16 '16 at 22:15
4
\$\begingroup\$

Metastability is really not a viable option in a modern FPGA technology because the metastable timing window is tiny - many orders of magnitude smaller than the setup/hold timing uncertainty window, which is dominated by things like clock skew, routing delays and variations with voltage and temperature.

Unfortunately there's a lot of confusion about metastability and this timing window is sometimes called the metastable timing window, as other (sometimes unexpected) sources of uncertainty in an output due to clock timings are loosely lumped together and incorrectly called metastability.

While this wider window generates uncertainty in the output, it's highly correlated with the above causes, not entropic (outside the tiny true metastable window).

If you need the mathematical and practical details, search the Usenet comp.arch.fpga newsgroup for "metastability" and "Peter Alfke".

TL/DR : look elsewhere for entropy : an avalanche diode, (i.e. a zener well above 6V, say 12V) amplified, sliced to logic levels, fed to an input pin would be one good choice.

\$\endgroup\$
  • 1
    \$\begingroup\$ Regarding avalanche noise sources: EMC testing facilities use devices based on the amplification of avalanche diode noise to generate extremely wide-band noise signals without frequency sweeping. Such devices are used for immunity testing. In any other guise this is simply a very high quality RNG. It is not at all difficult to build one, a decent high frequency opamp, and a few discrete parts. Schematics abound on the intarwebz. \$\endgroup\$ – Wossname Oct 15 '16 at 16:28
1
\$\begingroup\$

One option could be to use a higher quality random number generator such as mersenne twister and then seed that from something external. Other options may not be able to provide enough bandwidth for running a simulation.

Here is one such implementation: https://github.com/alexforencich/verilog-mersenne/blob/master/rtl/axis_mt19937.v

Another advantage to using this type of generator is that it's relatively easy to seed with a known value for debugging - i.e. it makes it straightforward to seed the hardware exactly the same as the functional simulation to ensure you're getting the same result.

\$\endgroup\$
1
\$\begingroup\$

You can get some randomness from an unstable combinatorial circuit like a ring oscillator. One way to do it is to have as many XOR gates as bits you want in the output, where each gate is the XOR of itself and its two neighbours. An odd number of the XOR gates should be inverted at the output to prevent it falling into a stable pattern. This generates a non-uniformly distributed set of random numbers (some bits will be 1 significantly more/less than 50% of the time). By feeding this into a pseudo-random generator like a LHCA you can generate high quality random numbers. There is much more information here: http://forums.xilinx.com/xlnx/attachments/xlnx/EDK/27322/1/HighSpeedTrueRandomNumberGeneratorsinXilinxFPGAs.pdf

With their implementation you can get arbitrarily wide random numbers, at a high clock rate, that pass the diehard tests for randomness for the price of 2 LUTs and 2 registers per output bit.

Code for 8 bit random numbers, output in rnd:

(* ALLOW_COMBINATORIAL_LOOPS = "TRUE", KEEP = "TRUE" *) wire [7:0] ring;
(* ASYNC_REG = "TRUE" *) reg [7:0] ring_reg;

assign ring = {ring, ring[7]} ^ ring ^ ({ring[0], ring}>>1) ^ {3{2'b01}};

always  @(posedge clk) begin
    ring_reg <= ring;
    rnd <= {rnd, 1'b0} ^ ring_reg ^ (rnd & 8'h06) ^ ({1'b0, rnd}>>1);
end

the 8'h06 is the diagonal elements of the LHCA from the paper. You might need to change the attributes to stop your synthesis tool screwing it up by 'optimising' the logic. This works for me on Vivado 2016.3, and generates what appear to be uniformly distributed random numbers (I haven't run proper statistical tests).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.