Random number generators in VHDL

published 2016-12-05 — category VHDL

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://git.jorisvr.nl/joris/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 264 - 1 219937 - 1 2128 - 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