Parallel Random Number Generators for Sequences Uniformly Distributed Over Any Range of Integers

摘要

A VLSI design methodology is proposed for the efficient generation of multiple pseudorandom number sequences based on a simplification of Cauwenberghs' counterpropagation technique. We demonstrate that the counterpropagation of two sequences can be replaced by one propagating and one nonpropa-gating sequence, requiring as few as half the number of flip-flops, while still allowing new circuits to be added to the system without additional calculations - there is no need to keep track of random starting values, tap combinations, or time shifts. Moreover we extend our method from multiple bit sequences to multiple random number sequences that are uniformly distributed over any range of integers. In particular we address the more general problem of generating sequences over the range [0, K] where K+1 is any desired integer, including a power of two or a prime number. To this end we demonstrate that the simple concatenation of random bits to form random bytes is a special case of a more general concept whereby random integers distributed over prime number ranges are concatenated to form random integers distributed over any range. We find that the proposed design compares favorably with design strategies based on cellular automata, both in terms of statistical properties and implementation efficiencies.