Skip to main content
SpringerLink
Log in

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

  • Published:
The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology Aims and scope Submit manuscript

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 2k − 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11

Similar content being viewed by others

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. J. Chen, J. Moon, and K. Bazargan, “Reconfigurable Readback-signal Generator Based on a Field-programmable Gate Array,” IEEE Transactions on Magnetics, vol. 40, no. 3, 2004, pp. 1744–1750.

    Article  Google Scholar 

  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. M. Fushimi and S. Tezuka, “The K-distribution of Generalized Feedback Shift Register Pseudorandom Numbers,” Communications of the ACM, vol. 26, no. 7, 1983, pp. 516–523.

    Article  MATH  Google Scholar 

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

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

    Article  Google Scholar 

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

    Google Scholar 

  12. P. L’Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators,” Mathematics and Computation, vol. 65, no. 213, 1996, pp. 203–213.

    Article  MATH  MathSciNet  Google Scholar 

  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. D.-U. Lee, W. Luk, J. D. Villasenor, and P. Y. Cheung, “A Gaussian Noise Generator for Hardware-based Simulations,” IEEE Transactions on Computers, vol. 53, no. 12, 2004, pp. 1523–1534.(December)

    Article  Google Scholar 

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

  17. G. A. Marsaglia and L. Tsay, “Matrices and the Structure of Random Number Sequences,” Linear Algebra and its Applications, vol. 67, 1985, pp. 147–156.

    Article  MATH  MathSciNet  Google Scholar 

  18. M. Matsumoto and Y. Kurita, “Twisted GFSR Generators II,” ACM Transactions on Modeling and Computer Simulation, vol. 4, no. 3, 1994, pp. 254–266.

    Article  MATH  Google Scholar 

  19. M. Matsumoto and T. Nishimura, “Mersenne Twister: A 623-dimensionally Equidistributed Uniform Pseudo-random Number Generator,” ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1, 1998, pp. 3–30.(January)

    Article  MATH  Google Scholar 

  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. R. C. Tausworthe, “Random Numbers Generated by Linear Recurrence Modulo Two,” Mathematics and Computation, vol. 19, no. 90, 1965, pp. 201–209.

    Article  MATH  MathSciNet  Google Scholar 

  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. S. Wolfram, “Random Sequence Generation by Cellular Automata,” Advances in Applied Mathematics, vol. 7, no. 2, 1986, pp. 123–169.

    Article  MATH  MathSciNet  Google Scholar 

  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.

Download references

Author information

Authors and Affiliations

  1. Department of Computing, Imperial College London, South Kensington Campus, London, UK

    David B. Thomas & Wayne Luk

Authors
  1. David B. Thomas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wayne Luk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David B. Thomas.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Thomas, D.B., Luk, W. High Quality Uniform Random Number Generation Using LUT Optimised State-transition Matrices. J VLSI Sign Process Syst Sign Image Video Technol 47, 77–92 (2007). https://doi.org/10.1007/s11265-006-0014-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation