FPGA implementation of neighborhood-of-four cellular automata random number generators

ABSTRACT

Random number generators (RNGs) based upon neighborhood-of-four cellular automata (CA) with asymmetrical, non-local connections are explored. A number of RNGs that pass Marsaglia's rigorous Diehard suite of random number tests have been discovered. A neighborhood size of four allows a single CA cell to be implemented with a four-input lookup table and a one-bit register which are common building blocks in popular field programmable gate arrays (FPGAs). The investigated networks all had periodic (wrap around) boundary conditions with either 1-d, 2-d, or 3-d interconnection topologies. Trial designs of 64-bit networks using a Xilinx XCV1000-6 FPGA predict a maximum clock rate of 214 MHz to 230 MHz depending upon interconnection topology.

REFERENCES

• 1: N. Metropolis and S. Ulam, "The Monte Carlo method," Journal of American Statistical Association, vol. 44, pp. 335-341, 1949.
• 2: Malvin H. Kalos , Paula A. Whitlock, Monte Carlo methods. Vol. 1: basics, Wiley-Interscience, New York, NY, 1986
• 3: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: G. Marsaglia, "Remarks on choosing and implementing random number generators," Communications of the ACM, vol. 36, no. 7, pp. 105-110, July 1993.
• 6: G. Marsaglia, "A current view of random numbers," Computer Science and Statistics: The Interface,L.Billard,ed.,Elsevier Science Publishers B. V., pp. 3-10, 1985.
• 7: G. Marsaglia, DIEHARD, http://stat.fsu.edu/geo/diehard.html, 1996.
• 8: VR. C. Tausworthe, "Random numbers generated by linear recurrence modulo two," Mathematical Computing, vol. 19, pp. 201-209, 1965.
• 9: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 10: Stephen Wolfram, Random sequence generation by cellular automata, Advances in Applied Mathematics, v.7 n.2, p.123-169, June 1986 [doi>10.1016/0196-8858(86)90028-X]
• 11: P. D. Hortensius , R. D. McLeod , H. C. Card, Parallel Random Number Generation for VLSI Systems Using Cellular Automata, IEEE Transactions on Computers, v.38 n.10, p.1466-1473, October 1989 [doi>10.1109/12.35843]
• 12: Barry Shackleford , Greg Snider , Richard J. Carter , Etsuko Okushi , Mitsuhiro Yasuda , Katsuhiko Seo , Hiroto Yasuura, A High-Performance, Pipelined, FPGA-Based Genetic Algorithm Machine, Genetic Programming and Evolvable Machines, v.2 n.1, p.33-60, March 2001 [doi>10.1023/A:1010018632078]
• 13: P. D. Hortensius , H. C. Card , R. D. McLeod , W. Pries, Importance Sampling for Ising Computers Using One-Dimensional Cellular Automata, IEEE Transactions on Computers, v.38 n.6, p.769-774, June 1989 [doi>10.1109/12.24285]
• 14: Ph. Tsalides, T. A. York, and A. Thanailakis, "Pseudorandom number generators for VLSI systems based on linear cellular automata," IEE Proceedings-E, vol. 138, no. 4, pp. 241-249, July 1991.
• 15: S. Nandi, B. Vamsi, S. Chakraborty, and P. P. Chaudhuri, "Cellular automata as a BIST structure for testing CMOS circuits," IEE Proceedings-Computer Digital Technology, vol. 141, no. 1, pp. 41-47, January 1994.
• 16: D. Roy Chowdhury , I. Sengupta , P. Pal Chaudhuri, A class of two-dimensional cellular automata and their applications in random pattern testing, Journal of Electronic Testing: Theory and Applications, v.5 n.1, p.67-82, Feb. 1994 [doi>10.1007/BF00971964]
• 17: M. Sipper and M. Tomassini, "Generating parallel random number generators by cellular programming," International Journal of Modern Physics C, vol. 7, no. 2, pp. 181-190, 1996.
• 18: Marco Tomassini , Moshe Sipper , Mosé Zolla , Mathieu Perrenoud, Generating high-quality random numbers in parallel by cellular automata, Future Generation Computer Systems, v.16 n.2-3, p.291-305, Dec. 1999 [doi>10.1016/S0167-739X(99)00053-9]
• 19: Marco Tomassini , Moshe Sipper , Mathieu Perrenoud, On the Generation of High-Quality Random Numbers by Two-Dimensional Cellular Automata, IEEE Transactions on Computers, v.49 n.10, p.1146-1151, October 2000 [doi>10.1109/12.888056]
• 20: S. Wolfram, "Statistical mechanics of cellular automata," Reviews of Modern Physics, vol. 55, pp. 601-644, July 1983. (Also available in S. Wolfram, Cellular Automata and Complexity, Addison-Wesley, 1994.)
• 21: S. Ulam, "Random processes and transformations," Proceedings of the International Congress of Mathematics (1950),vol.2,pp. 264-275, 1952.
• 22: John Von Neumann , Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press, Champaign, IL, 1966
• 23: S. Wolfram (ed.), Theory and Applications of Cellular Automata, World Scientific, 1986.
• 24: A new kind of science, Wolfram Media Inc., Champaign, Ilinois, US, 2002

INDEX TERMS

Keywords:
FPGA, cellular automata, random number generator