Mersenne Twister MT32 is a pseudo Random Number Generator (RNG) with a uniform distribution and a large prime period of 219937-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.
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>mt2coemt2coe Ver 0.1 HT-LAB 2006 (-h for usage)Init values :00000123 00000234 00000345 00000456Generating Xilinx coe files......doneYou 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 re-customise 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.txtComparing files modelsim_result.txt and mt19937ar_result.txtFC: no differences encountered4) Synthesize and Place&RouteSynthesis file order:•dprams/dpram624x1.vhd•dprams/dpram624x31.vhd•dprams/dpram624x32.vhd•src/counters.vhd•src/mt.vhdPlace 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)
PinDescriptionresetnActive Low ResetclkClockenaActive High Enable Signalrandom32bits Randum Number Output
Top level diagram from Mentor Graphics HDL Designer
•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.