Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

49 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)952-962
Journal / PublicationIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume15
Issue number8
Publication statusPublished - Aug 2007
Externally publishedYes

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; Villasenor, John D.

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, 22, 62)21_Publication in refereed journalpeer-review