Cellular Automata-Based Parallel Random Number Generators Using FPGAs

Cellular computing represents a new paradigm for implementing high-speed massively parallel machines. Cellular automata (CA), which consist of an array of locally connected processing elements, are a basic form of a cellular-based architecture. The use of field programmable gate arrays (FPGAs) for implementing CA accelerators has shown promising results. This paper investigates the design of CA-based pseudo-random number generators (PRNGs) using an FPGA platform. To improve the quality of the random numbers that are generated, the basic CA structure is enhanced in two ways. First, the addition of a superrule to each CA cell is considered. The resulting self-programmable CA (SPCA) uses the superrule to determine when to make a dynamic rule change in each CA cell. The superrule takes its inputs from neighboring cells and can be considered itself a second CA working in parallel with the main CA. When implemented on an FPGA, the use of lookup tables in each logic cell removes any restrictions on how the super-rules should be defined. Second, a hybrid configuration is formed by combining a CA with a linear feedback shift register (LFSR). This is advantageous for FPGA designs due to the compactness of the LFSR implementations. A standard software package for statistically evaluating the quality of random number sequences known as DIEHARD is used to validate the results. Both the SPCA and the hybrid CA/LFSR were found to pass all the DIEHARD tests. 1. Introduction Cellular computing is touted as one of the new paradigms for future computational systems due to three key properties: simplicity, massive parallelism, and local interconnect [1]. Such systems have advantages over the traditional general-purpose processor in terms of high-speed parallel computation and fault tolerant capabilities. A variety of unique applications have been proposed and implemented using the cellular computational model including fault-tolerant self-healing architectures [2], cellular neural networks [3, 4], and pseudo-random number generators [5]. Cellular automata (CA), which consist of an array of locally interconnected, elementary processing elements, can be viewed as one form of a high-speed massively parallel machine. As CA are dynamical systems which evolve in discrete time and space, they are used to model a variety of physical and biological processes, including fluid dynamics, the immune system, the evolution of genetic regulatory networks, and urban traffic flow [6–10]. A CA-based architecture will likely form the basis for the development of ultra-high speed and compact