Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 952-962 |
Journal / Publication | IEEE Transactions on Very Large Scale Integration (VLSI) Systems |
Volume | 15 |
Issue number | 8 |
Publication status | Published - Aug 2007 |
Externally published | Yes |
Link(s)
Abstract
We present an automated methodology for producing hardware-based random number generator (RNG) designs for arbitrary distributions using the inverse cumulative distribution function (ICDF). The ICDF is evaluated via piecewise polynomial approximation with a hierarchical segmentation scheme that involves uniform segments and segments with size varying by powers of two which can adapt to local function nonlinearities. Analytical error analysis is used to guarantee accuracy to one unit in the last place (ulp). Compact and efficient RNGs that can reach arbitrary multiples of the standard deviation σ can be generated. For instance, a Gaussian RNG based on our approach for a Xilinx Virtex-4 XC4VLX100-12 field-programmable gate array produces 16-bit random samples up to 8.2σ. It occupies 487 slices, 2 block-RAMs, and 2 DSP-blocks. The design is capable of running at 371 MHz and generates one sample every clock cycle. © 2007 IEEE.
Research Area(s)
- Algorithms implemented in hardware, Automatic synthesis, Chebyshev approximation and theory, Computer arithmetic, Elementary function approximation, Error analysis, Gate arrays, Piecewise polynomial approximation
Citation Format(s)
Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method. / Cheung, Ray C. C.; Lee, Dong-U; Luk, Wayne et al.
In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 15, No. 8, 08.2007, p. 952-962.
In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 15, No. 8, 08.2007, p. 952-962.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review