research-article

High Quality Uniform Random Number Generation Using LUT Optimised State-transition Matrices

Authors:

David B. Thomas,

Wayne LukAuthors Info & Claims

The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, Volume 47, Issue 1

Pages 77 - 92

https://doi.org/10.1007/s11265-006-0014-9

Published: 01 April 2007 Publication History

Abstract

This paper presents a family of uniform random number generators designed for efficient implementation in Lookup table (LUT) based FPGA architectures. A generator with a period of 2^k − 1 can be implemented using k flip-flops and k LUTs, and provides k random output bits each cycle. Each generator is based on a binary linear recurrence, with a state-transition matrix designed to make best use of all available LUT inputs in a given FPGA architecture, and to ensure that the critical path between all registers is a single LUT. This class of generator provides a higher sample rate per area than LFSR and Combined Tausworthe generators, and operates at similar or higher clock-rates. The statistical quality of the generators increases with k, and can be used to pass all common empirical tests such as Diehard, Crush and the NIST cryptographic test suite. Theoretical properties such as global equidistribution can also be calculated, and best and average case statistics shown. Due to the large number of random bits generated per cycle these generators can be used as a basis for generators with even higher statistical quality, and an example involving combination through addition is demonstrated.

References

[1]

P. Alfke, “Efficient Shift Registers, LFSR Counters, and Long Pseudo-random Sequence Generators.” Technical Report, Xilinx, Inc., 1996.

[2]

Alpha Data, ADM-XRC SDK User Guide 4.3.1, 2003.

[3]

Altera Corporation, Stratix II Device Handbook, Volume 1, 2005.

[4]

R. Andraka and R. Phelps, “An FPGA Based Processor Yields a Real Time High Fidelity Radar Environment Simulator,” in Conference on Military and Aerospace Applications of Programmable Devices and Technologies, 1998.

[5]

Chen J., Moon J., and Bazargan K. Reconfigurable Readback-signal Generator Based on a Field-programmable Gate Array IEEE Transactions on Magnetics 2004 40 3 1744-1750

[6]

S. Duplichan, PPSearch: A Primitive Polynomial Search Program, http://users2.ev1.net/~sduplichan/primitivepolynomials/, 2003.

[7]

V. Fischer and M. Drutarovský, “True Random Number Generator Embedded in Reconfigurable Hardware,” in CHES ’02: Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, Springer, Berlin Heidelberg New York, 2003, pp. 415–430.

[8]

Fushimi M. and Tezuka S. The K-distribution of Generalized Feedback Shift Register Pseudorandom Numbers Communications of the ACM 1983 26 7 516-523

[9]

M. George and P. Alfke, Linear Feedback Shift Registers in Virtex Devices, Technical Report, Xilinx, Inc., 2001.

[10]

Hortensius P. D., McLeod R. D., and Card H. C. Parallel Random Number Generation for VLSI Systems Using Cellular Automata IEEE Transactions on Computers 1989 38 10 1466-1473

[11]

Knuth D. E. Semi-numerical Algorithms, Volume 2 of the Art of Computer Programming 1981 2 Reading, MA Addison-Wesley

[12]

L’Ecuyer P. Maximally Equidistributed Combined Tausworthe Generators Mathematics and Computation 1996 65 213 203-213

[13]

P. L’Ecuyer and R. Simard, TestU01 Random Number Test Suite, http://www.iro.umontreal.ca/~simardr/indexe.html.

[14]

D. Lee, J. Villasenor, W. Luk, and P. Leong, “A Hardware Gaussian Noise Generator Using the Box-muller Method and Its Error Analysis,” To Appear in IEEE Transactions on Computers, 2006.

[15]

Lee D.-U., Luk W., Villasenor J. D., and Cheung P. Y. A Gaussian Noise Generator for Hardware-Based Simulations IEEE Transactions on Computers 2004 53 12 1523-1534

[16]

G. Marsaglia, The Diehard Random Number Test Suite, http://stat.fsu.edu/pub/diehard/, 1997.

[17]

Marsaglia G. A. and Tsay L. Matrices and the Structure of Random Number Sequences Linear Algebra and its Applications 1985 67 147-156

[18]

Matsumoto M. and Kurita Y. Twisted GFSR Generators II ACM Transactions on Modeling and Computer Simulation 1994 4 3 254-266

[19]

Matsumoto M. and Nishimura T. Mersenne Twister: A 623-dimensionally Equidistributed Uniform Pseudo-random Number Generator ACM Transactions on Modeling and Computer Simulation 1998 8 1 3-30

[20]

A. Negoi and J. Zimmermann, “Monte Carlo Hardware Simulator for Electron Dynamics in Semiconductors,” in International Annual Semiconductor Conference, Sinaia, Romania, 1996, pp. 557–560.

[21]

F. Panneton and P. L’Ecuyer, “On the Xorshift Random Number Generators,” To appear in ACM Transactions on Modeling and Simulation, 2005.

[22]

F. Panneton, P. L’Ecuyer, and M. Matsumoto, “Improved Long-period Generators Based on Linear Recurrences Modulo 2,” To appear in ACM Transactions on Mathematical Software, 2005.

[23]

B. Shackleford, M. Tanaka, R. J. Carter, and G. Snider, “FPGA Implementation of Neighborhood-of-four Cellular Automata Random Number Generators,” in ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, ACM, New York, 2002, pp. 106–112.

[24]

V. Shoup, Ntl: A Library for Doing Number Theory, http://www.shoup.net/ntl/.

[25]

Tausworthe R. C. Random Numbers Generated by Linear Recurrence Modulo Two Mathematics and Computation 1965 19 90 201-209

[26]

K. H. Tsoi, K. H. Leung, and P. H. W. Leong, “Compact FPGA-based True and Pseudo Random Number Generators,” in IEEE Symposium on FPGAs for Custom Computing Machines, IEEE Computer Society, Washington, DC, 2003, p. 51.

[27]

Wolfram S. Random Sequence Generation by Cellular Automata Advances in Applied Mathematics 1986 7 2 123-169

[28]

Xilinx, Inc., Virtex-II Platform FPGAs: Complete Data Sheet, 2000.

[29]

G. L. Zhang, P. H. Leong, D.-U. Lee, J. D. Villasenor, R. C. Cheung, and W. Luk, “Ziggurat-based Hardware Gaussian Random Number Generator,” in International Conference on Field Programmable Logic and Applications, IEEE Computer Society, 2005, pp. 275–280.

[30]

G. L. Zhang, P. H. W. Leong, C. H. Ho, K. H. Tsoi, D.-U. Lee, R. C. C. Cheung, and W. Luk, “Reconfigurable Acceleration for Monte Carlo Based Financial Simulation,” in International Conference on Field-Programmable Technology, IEEE Computer Society, 2005, pp. 215–224.

Cited By

Sivakumar ESingh KChawla PCheng X(2024)PRAY So You Don’t Become PreySN Computer Science10.1007/s42979-024-02644-45:3Online publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1007/s42979-024-02644-4
Guo LFunie AXie ZThomas DLuk W(2015)A general-purpose framework for FPGA-accelerated genetic algorithmsInternational Journal of Bio-Inspired Computation10.1504/IJBIC.2015.0731837:6(361-375)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1504/IJBIC.2015.073183
Thomas D(2015)The Table-Hadamard GRNGACM Transactions on Reconfigurable Technology and Systems10.1145/26296078:4(1-22)Online publication date: 24-Sep-2015
https://dl.acm.org/doi/10.1145/2629607
Show More Cited By

Recommendations

FPGA-Optimised Uniform Random Number Generators Using LUTs and Shift Registers
FPL '10: Proceedings of the 2010 International Conference on Field Programmable Logic and Applications

FPGA-optimised Random Number Generators (RNGs) are more resource efficient than software-optimised RNGs, as they can take advantage of bit-wise operations and FPGA-specific features. However, it is difficult to concisely describe FPGA-optimised RNGs, so ...
Uniform Random Number Generator Using Leap Ahead LFSR Architecture
ICCCS '09: Proceedings of the 2009 International Conference on Computer and Communications Security

Uniform Random Number Generator (URNG) is a key element in most applications which run on FPGA based hardware accelerators. As multi-bits is required and a normal LFSR could only generate one bit per cycle, more than one LFSR is needed in a URNG. In ...
The LUT-SR family of uniform random number generators for FPGA architectures

Field-programmable gate array (FPGA) optimized random number generators (RNGs) are more resource-efficient than software-optimized RNGs because they can take advantage of bitwise operations and FPGA-specific features. However, it is difficult to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of VLSI Signal Processing Systems

Journal of VLSI Signal Processing Systems Volume 47, Issue 1

Apr 2007

89 pages

ISSN:0922-5773

Issue’s Table of Contents

© Springer Science+Business Media, LLC 2007.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2007

Accepted: 13 November 2006

Received: 06 February 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sivakumar ESingh KChawla PCheng X(2024)PRAY So You Don’t Become PreySN Computer Science10.1007/s42979-024-02644-45:3Online publication date: 14-Mar-2024
https://dl.acm.org/doi/10.1007/s42979-024-02644-4
Guo LFunie AXie ZThomas DLuk W(2015)A general-purpose framework for FPGA-accelerated genetic algorithmsInternational Journal of Bio-Inspired Computation10.1504/IJBIC.2015.0731837:6(361-375)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1504/IJBIC.2015.073183
Thomas D(2015)The Table-Hadamard GRNGACM Transactions on Reconfigurable Technology and Systems10.1145/26296078:4(1-22)Online publication date: 24-Sep-2015
https://dl.acm.org/doi/10.1145/2629607
Withers CNadarajah S(2015)Solutions of linear recurrence equationsApplied Mathematics and Computation10.1016/j.amc.2015.09.079271:C(768-776)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.09.079
Thomas DLuk W(2013)The LUT-SR family of uniform random number generators for FPGA architecturesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.219417121:4(761-770)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1109/TVLSI.2012.2194171
Echeverría PLópez-Vallejo M(2013)High Performance FPGA-oriented Mersenne Twister Uniform Random Number GeneratorJournal of Signal Processing Systems10.1007/s11265-012-0684-471:2(105-109)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1007/s11265-012-0684-4
Jin QDong DTse AChow GThomas DLuk WWeston S(2012)Multi-level customisation framework for curve based monte carlo financial simulationsProceedings of the 8th international conference on Reconfigurable Computing: architectures, tools and applications10.1007/978-3-642-28365-9_16(187-201)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28365-9_16
Becker TJamieson PLuk WCheung PRissa T(2010)Power characterisation for fine-grain reconfigurable fabricsInternational Journal of Reconfigurable Computing10.1155/2010/7874052010(2-2)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1155/2010/787405
Thomas DHowes LLuk WChow PCheung P(2009)A comparison of CPUs, GPUs, FPGAs, and massively parallel processor arrays for random number generationProceedings of the ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1508128.1508139(63-72)Online publication date: 24-Feb-2009
https://dl.acm.org/doi/10.1145/1508128.1508139
Dalal IStefan DHutton MChow P(2008)A hardware framework for the fast generation of multiple long-period random number streamsProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344707(245-254)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344707
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents