Random numbers have many applications in digital systems.
Noise generation in digital signal processing is an obvious example.
Other common uses of random numbers are games and Monte Carlo simulations.
(One may also think of generating cryptographic keys, but the methods discussed in this article are **not** suitable for cryptography.)

Software implementations of pseudo-random number generators (PRNGs) are widely available.
Nearly all programming languages have a standard library function such as `rand()`

in C.
Specialized libraries provide modern, fast, high-quality algorithms such as the ever popular Mersenne Twister [1].

The situation appears to be different in the FPGA world.
The IP core library supplied by Xilinx does not provide a random number generator at all.
The VHDL standard library package `ieee.math_real`

contains a pseudo random number generator, but it is not synthesizable.

This article considers 4 pseudo-random number generators and compares them in terms of quality, speed and FPGA resources. Portable, synthesizable VHDL code for 3 of these generators is available on GitHub:

https://github.com/jorisvr/vhdl_prng |

### Linear feedback shift registers

Linear feedback shift registers (LFSRs) [2] are a well-known method for generating pseudo-random bits in digital circuits. Unfortunately the output of an LFSR is not very random, especially if the LFSR has a small number of tap positions [3].

A straightforward implementation of an LFSR produces 1 bit per clock cycle.
One way to obtain an *m*-bit word per clock cycle is to implement the LFSR such that it shifts through *m* positions per clock cycle, thus producing groups of *m* bits.
(An incorrect method is to extract *m* bits while shifting the LFSR by only 1 bit per clock cycle; this causes strong correlations in the output sequence.)

I used a 64-bit, maximum-length LFSR with tap positions (64, 63, 61, 60) from the table in [4]. Based on this LFSR, I defined a PRNG which shifts the LFSR over 32 positions to generate each 32-bit output word. I did not write VHDL code for this generator, only a C implementation to test its quality.

### Mersenne Twister

The Mersenne Twister [5] is a popular PRNG in software applications. It produces high-quality random number sequences that pass many statistical tests.

I implemented the MT19937 Mersenne Twister in VHDL. The VHDL code produces a new random 32-bit word on each clock cycle. A 32x1024-bit dual-port RAM block is used in the FPGA to store the internal state of the generator.

### Xoroshiro128+

Xoroshiro128+ [6] is a new PRNG developed in 2016. It is designed to be very fast (in software) while still passing common statistical tests for random number generators.

I implemented Xoroshiro128+ in VHDL. The VHDL code produces a new random 64-bit word on each clock cycle. The FPGA implementation is quite compact, but it does require a 64-bit adder.

Note that the least significant output bit of Xoroshiro128+ is known to be less random. If a subset of the 64 output bits is needed, it should be taken from the most significant side of the output word.

### Trivium

Trivium [7] is a stream cipher designed to be fast and efficient in hardware implementations. The key stream of the cipher can be used as a general-purpose random number sequence, as suggested by the author of PractRand [8].

I implemented Trivium in VHDL. The VHDL code produces a new random 32-bit word on each clock cycle (the output word length can be adjusted via a design parameter). The FPGA implementation is quite efficient and requires only general logic and registers.

### TestU01

TestU01 [9][10] is a software library for empirical statistical testing of random number generators.

Each test draws a sequence of numbers from a generator, computes a *statistic* over the sequence, then maps the obtained statistic to a corresponding *p*-value.
For a true random number generator, such *p*-values are uniformly distributed between 0 and 1.
But a pseudo-random number generator with a defect that affects the statistic, tends to produce *p*-values very close to 0 or 1. In this case, TestU01 will report the test as a *possible* failure (not a certain failure, because even a true random number generator has a small probability of hitting *p*-values close to 0 or 1).

TestU01 contains a predefined battery of 96 statistical tests, called *Crush*.
I used the Crush battery to determine the quality of the 4 PRNGs described above.
Each PRNG was tested 8 times with different *seed* values.
In the case of Xoroshiro128+, only the 32 most significant bits of the output were tested (TestU01 requires 32-bit data).

### Results

The table below summarizes for each of the 4 PRNGs: basic properties, test results with TestU01 and FPGA synthesis results.

The listed *nr of failed tests* is the total number of suspicious results out of 8 runs through the 96 tests of the TestU01-Crush battery.
A different seed is used for each of the 8 runs.
A result is considered suspicious when it has *p*-value less than 0.001 or greater than 0.999.
The listed *nr of systematic failures* is the number of tests that produced suspicious results for at least 3 of the 8 seeds (out of the 96 tests of the Crush battery).

FPGA resources and clock frequency were determined for Xilinx Spartan-6 LX45-3, synthesis with ISE 14.6.

LFSR-64 | Mersenne Twister |
Xoroshiro128+ | Trivium | |
---|---|---|---|---|

Output width | 32 bits | 32 bits | 64 bits | 32 bits |

Period | 2^{64} - 1 |
2^{19937} - 1 |
2^{128} - 1 |
unknown |

TestU01 Nr failed tests |
335 | 18 | 5 | 2 |

Nr systematic failures | 42 | 2 | 0 | 0 |

FPGA resources | ?? | 279 LUTs 297 registers 2x 16kbit RAM |
194 LUTs 192 registers 64-bit adder |
202 LUTs 332 registers |

FPGA clock | ?? | 300 MHz | 333 MHz | 380 MHz |

### Conclusion

Plain LFSRs are not suitable as high-quality PRNGs.

The Mersenne Twister is a well-known and popular PRNG with huge period and good equidistribution properties. It passes many statistical tests but does show a few systematic weaknesses. The FPGA implementation requires significant resources, including RAM blocks.

Xoroshiro128+ and Trivium are high-quality PRNGs with efficient FPGA implementations. Both pass TestU01-Crush without revealing systematic weaknesses. Trivium is slightly faster, has a larger internal state and was designed to be cryptographically strong. However Trivium provides no guarantees about the period of its output sequence.

*Disclaimer:* I am not an expert on random number generators.
Although I tried to provide accurate information and a fair comparison, this article may contain mistakes.
Please take my conclusion with a grain of salt and consult a real expert if you need one.

*Disclaimer 2:* This article does **not** consider cryptographic applications.
Most of the PRNGs discussed here are fundamentally unsuitable for cryptography, and in any case cryptography requires a much more thorough analysis.

### References

- [1] "Mersenne Twister" from Wikipedia.
- [2] "Linear feedback shift register" from Wikipedia.
- [3] P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe Generators",
*Math. Comb.*, vol. 65, no. 213, Jan. 1996. - [4] Maria George, Peter Alfke, "Linear Feedback Shift Registers in Virtex Devices", Xilinx XAPP210, Jan. 2001.
- [5] M. Matsumoto, T. Nishimura, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator",
*ACM TOMACS*, vol. 8, no. 1, Jan. 1998. - [6] Sebastiano Vigna, David Blackman, "Xoroshiro", PRNG Shootout, 2016.
- [7] C. De Cannière, B. Preneel, “Trivium”, eCRYPT Stream Cipher Project, 2005.
- [8] C. Doty-Humphrey, "PractRand: Practically Random", Sourceforge project.
- [9] P. L'Ecuyer, "TestU01", project website.
- [10] P. L'Ecuyer, R. Simard, "TestU01: A C library for emperical testing of random number generators",
*ACM Trans. Math. Softw.*, vol. 33, no. 4, Aug. 2007.