Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

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

David B. ThomasContact Information and Wayne LukContact Information

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

Received: 6 February 2006  Accepted: 13 November 2006  Published online: 24 February 2007

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.

Keywords  Uniform Random Numbers - FPGA - Simulation


Contact Information David B. Thomas (Corresponding author)
Email: dt10@doc.ic.ac.uk

Contact Information Wayne Luk
Email: wl@doc.ic.ac.uk

David B. Thomas   received the MEng and Ph.D. degrees in computer science from Imperial College, in 2001 and 2006, respectively. He likes Imperial so much that he stayed on, and is now a post-doctoral researcher in the Custom Computing group. Research interests include FPGA-based Monte-Carlo simulations, algorithms and architectures for uniform and non-uniform random number generation, and financial computing.
MediaObjects/11265_2006_14_Figa_HTML.jpg
Wayne Luk   received the MA, MSc, and DPhil degrees in engineering and computer science from the University of Oxford, Oxford, United Kingdom. He is a professor of computer engineering, Department of Computing, Imperial College London and leads the Custom Computing Group there. His research interests include theory and practice of customizing hardware and software for specific application domains, such as graphics and image processing, multimedia, and communications. Much of his current work involves high-level compilation techniques and tools for parallel computers and embedded systems, particularly those containing reconfigurable devices such as field-programmable gate arrays. He is a member of the IEEE.
MediaObjects/11265_2006_14_Figb_HTML.jpg
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this article
Export this article as RIS | Text
 
Referenced by
1 newer article

  1. Becker, Tobias (2010) Power Characterisation for Fine-Grain Reconfigurable Fabrics. International Journal of Reconfigurable Computing 2010
    [CrossRef]
Remote Address: 38.107.191.110 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)