Many digital designs incorporate high-speed generation of pseudorandom numbers. Typically, pseudorandom number generation is implemented using linear-feedback shift register (LFSR). An LFSR produces a sequence of numbers that appears to be uniformly distributed over the range 1 to 2n − 1, where n is the LFSR size. For this type of generator, each output value has an equal probability of appearing.
Some applications, however, require the generation of random numbers that aren't uniformly distributed. Instead, they obey a predefined, arbitrary distribution. This example of an arbitrary probability distribution function (PDF) expresses the occurrence probability of 10 values (Fig. 1). The cumulative distribution function (CDF) is an incremental aggregation of the PDF.
Since by definition the CDF is a positive monotonic function with values from 0 to 1, it's apparent that an inverse CDF always exists.
The inverse CDF may be interpreted as a function mapping uniformly distributed values to some arbitrary distribution described by the PDF. Such an explanation leads to a straightforward digital hardware im-plementation (Fig. 2).
Two basic components make up the design. One is an LFSR functioning as a pseudorandom number generator. As such, it generates values uniformly distributed over a specific range in accordance with the LFSR size (M). The other is a programmable ROM (PROM) containing the inverse CDF function. This PROM acts as a lookup table with the LFSR outputs used as input lines. The PROM is a sequence of random numbers, distributed with respect to the PDF, used as output lines (N). Depending on the requirements of the specific application, the PROM may be replaced with a RAM device.
Precision may be flexibly determined by choosing the LFSR and ROM sizes that meet with design needs. Longer LFSR widths and wider ROM addresses result in finer granularity.
This technique also is attractive in terms of speed. The critical path is composed of merely an LFSR (on the order of a single-gate level) and a memory component, yielding very high clock rates.
Reprints
