Mersenne Twister, MT32

Pseudo Random Number Generator for Xilinx FPGA

web: www.ht-lab.com
Last updated: 7th January 2007

Mersenne Twister MT32 is a pseudo Random Number Generator (RNG) with a uniform distribution and a large prime period of 2¹⁹⁹³⁷-1. The large period results in long pseudo-random sequences with no repetition. The Mersenne Twister described on this page is based on the MT19937 algorithm by Makoto Matsumoto and Takuji Nishimura.

The MT19937 implementation requires no multiplications or division and hence simplifies FPGA implementation. This page describes a 32bits version of the MT19937 algorithm implemented on a Xilinx FPGA. The generator is low on resources and can generate a new 32-bits sequence every clockcycle. The seed is pre-calculated as a memory image.

The design is released under the GNU General Public License, for feedback, bug reports comments etc use the feedback form.

Download VHDL source files

MT32 (version 0.1 07-01-07, zipped 123Kbyte)

How to use it

1) Generate the required seed as a memory image using the supplied mt2coe.exe DOSbox/Cygwin utility.

For the first implementation I would use the same seed as used in mt19937ar.c:

D:\hdl_designs\rng>mt2coe

mt2coe Ver 0.1 HT-LAB 2006 (-h for usage)
Init values :00000123 00000234 00000345 00000456
Generating Xilinx coe files......done

You now have 3 Xilinx memory image (coe) files containing the original statevector values (see mt[] array in the mt19937ar.c program).

2) Generate 3 Dual Port Memories using the Xilinx CORE Generator.

Invoke Xilinx CORE Generator and create a new project.
Select the Block Memory Generator and enter dpram624x1 as the component name.
Select the Simple Dual Port RAM memory type.
The port size is 1 bit wide by 624 deep.
Tick the Load Init File (page 4) and select mt1.coe file, make sure the filename stays black (red means something is wrong)
Select finish, the core will generate dpram624x1.vhd (simulation), dpram624x1.mif (simulation), dpram624x1.ngc (place and route).

Repeat the above procedure to create dpram624x31 (31 bits wide by 624, mt31.coe file for init) and dpram624x32 (32 bits wide by 624, mt32.coe for init).

Alternative, load the CORE generator project file dprams.cgp and recustomise for the required FPGA.

3) Confirm the correct operation using simulation.

The procedure below is for Modelsim but should be similar for other simulators.

Copy the mif files to your project directory (were you invoke Modelsim from) or change the path in the dpram624x?.vhd files.
Make sure the Xilinx primitive libraries (e.g. XilinxCoreLib) are mapped in your modelsim.ini file.
Compile the design (compile.bat) and run the testbench for 100 us (run.bat). The testbench should write 1000 random numbers to the file modelsim_results.txt.
Compare the results against the output of the modified mt19937ar.c mt19937ar_results.txt file.

D:\hdl_designs\rng>fc modelsim_result.txt mt19937ar_result.txt
Comparing files modelsim_result.txt and mt19937ar_result.txt
FC: no differences encountered

4) Synthesize and Place&Route

Synthesis file order:

       dprams/dpram624x1.vhd
   dprams/dpram624x31.vhd
   dprams/dpram624x32.vhd
   src/counters.vhd
   src/mt.vhd

Place and Route:

Make sure ISE can find the ngc files. For my prototype board (Hardi HAPS-10) which uses the XC2V6000ff1517 the resources and fmax are:

# Using target part "2v6000ff1517-6"
# Device Utilization Summary:
#
#    Number of BUFGMUXs               1 out of 16      6%
#    Number of External IOBs          35 out of 1104   3%
#    Number of LOCed IOBs             0 out of 35      0%
#    Number of RAMB16s                5 out of 144     3%
#    Number of SLICEs                 83 out of 33792 1%

# Timing summary:
# ---------------
# Design statistics:
# Minimum period: 4.537ns (Maximum frequency: 220.410MHz)

Pin Out

Pin
resetn
clk
ena
random

Description
Active low Reset
Clock
Active high Enable signal
Output 32 bits Random Number

Block Diagram

Top level diagram from HDL Designer, click to enlarge

General Info

The original paper was published in the ACM Transactions on Modeling and Computer simulation:

Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator,
ACM Transactions on Modeling and Computer Simulation,
Vol. 8, No. 1, January 1998, pp. 3-30

You can target other FPGA vendors by replacing the Dual Port Memory modules dpram624x?.vhd with generic versions. You also need to pre-load the memory with the contents of the dpram624*?.coe files.
The original source file mt19937ar.c was slightly modified to produce hex output values, see the mt19937ar.c file in the utils directory.