Fuzzy Cellular Automata Based Random Numbers Generation

Ramin Ayanzadeh, Azam S. Zavar Mousavi and Ehsan Shahamatnia

*Trends in Applied Sciences Research,
2012, 7(1), 96-102.*

Due to the steady increasing trend toward computer simulations, generating random numbers has attracted many researches and several techniques have been introduced in recent years. In this study by employing fuzzy operators on the structure of cellular automata update rules a new approach has been proposed for uniformly distributed random number generation. The simulation results show that the uniformity of the proposed method is very promising. The nature of this approach also makes it very suitable for hardware implementation.

**ASCI-ID: 95-461**

Ayanzadeh *et al*., 2010;
Moghaddas *et al*., 2008; Jang
*et al*., 2005). Lotteries, computer games, cryptography, Monte Carlo
based computation, computer simulations, operational research and most of intelligent
optimization approaches such as Genetic Algorithms (GA), Particle Swarm Optimization
(PSO), tabu search and etc., are among the vastly used applications of random
number generators (Ayanzadeh *et al*., 2009b, 2011;
Shahamatnia *et al*., 2011; Banks
*et al*., 2004). One of the primary techniques in random number generation
is use of various mappings based on parameters such as time i.e., system clock
(Sarkar, 2000). To this end, starting from an initial
state and employing a recursive equation, a sequence of random numbers is generated.
Linear congruential generator, multiple recursive generators and lagged Fibonacci
generator are among these techniques (Benkiniouar and Benmohamed,
2004; Sarkar, 2000; Viega, 2003).

Such processes generate a sequence of random numbers which in practice are
repeated after a (usually) long period. Random numbers generated within computer
applications are sensitive to variables such as the state of initialization
and are not completely random. Such systems are called pseudo random number
generators (Ayanzadeh * et al*., 2010, 2009a;
Jaberi * et al*., 2011; Sarkar,
2000).

Random number generators must be compatible with a variety of statistical distributions e.g., uniform, normal, exponential, Poisson, Erlang, etc. Due to the extensive use of uniform distribution in random number generation, this study also addressed uniform distribution but the proposed approach is extendable to other distributions as well. The efficiency of random number generators is evaluated considering criteria such as long period frequency, fast and easy computation, low correlation between generated random numbers and better conformance with the desired distribution.

**CELLULAR AUTOMATA**

With respect to the nature of cellular automata in complex system simulations,
it is widely used for random number generation (Szaban *et
al*., 2005; L’ecuyer, 1998). Fast algorithm,
parallelization capability, hardware implementation capability and generation
of better random numbers are the advantages of these approaches (Brent,
1994).

Cellular automata are discrete computational models that consist of lattice
of identical cells communicating within a neighborhood structure. Many structures
have been suggested for neighborhood but Moor neighborhood model and Neumann
neighborhood model are two widely used. Figure 1 illustrates
the Moor and Neumann neighborhood structure with neighborhood radius 1 and 2
(Brent, 1994; Azghadi *et al*.,
2007). The state (value) of cells is derived from a finite set and in each
iteration is updated considering current state of cell and current state of
the cell’s neighbors, according to governing rules which are equally applied
to all cells (Brent, 1994).

Binary cellular automata are one of widely used methods to model CA. In binary cellular automata, state of each cell can be either zero or one. Update rules are obtained from Boolean algebra rules which are based on basic AND, OR and NOT operators. The decimal value of bit sequence for next cell state is a method to name the CA rules, first suggested by Wolfram and widely adopted (Bar-Yam, 1997).

Some of the most employed binary cellular automata update rules which are named under Wolfram scheme are shown in Table 1. Table 1 the first line is the current state of the cell (the middle bit) along with right neighbor’s states (right bit) and left neighbor’s state (left bit). The next state of the cell according to each rule is shown in the lines below.

Initiating from a random state and applying the update rules shown in Table 1, the binary cellular automata generates pseudo random numbers. Due to the locality of update rules, the repeat period of cellular automata in generating pseudo random bits is admissible (Bar-Yam, 1997).

Fig. 1(a-d): | (a) and (b) are Neumann and Moor neighborhood structures respectively, with neighborhood radius 1. (c) and (d) are Neumann and Moor neighborhood structures, respectively with neighborhood radius 2 |

Table 1: | Update rules for the binary cellualr automate |

**FUZZY SETS AND FUZZY OPERATORS**

Fuzzy set theory maps the state space {0, 1} in classic logic (binary valued
logic) to the domain [0, 1] (infinite valued logic). For each member x of set
A, membership function determines the measure of existence of x to set A and
is shown as μ_{A }(x) (Rozyyev *et al*.,
2011; Jang *et al*., 2005; Khanale
and Ambilwade, 2011). Fuzzy sets are an extension to the classical sets
and likewise fuzzy operators are an extension to Boolean algebra operators.
The operators fuzzy complement, fuzzy s-norm and fuzzy t-norm are equivalents
of operators NOT, OR and AND in binary valued logic (Darestani
and Jahromi, 2009; Hatami-Marbini *et al*., 2009;
Jang *et al*., 2005).

Various classes of fuzzy operators have been suggested for different types
of applications. Eq. 1 shows the standard fuzzy complement,
Eq. 2 shows the Yager class fuzzy complement and Eq.
3 shows the Sugeno class fuzzy complement. In these equations μ_{A}
(x) specifies membership value of x in A. Also λ and ω are fuzzy complement
parameters (Jang *et al*., 2005):

(1) |

(2) |

(3) |

Fuzzy s-norm of classes Dombi, Dubois-Prade, Yager and Max are the most commonly
used and are provided at Eq. 4 to 7, respectively.
In these equations a = μ_{A}, b = μ_{B} and λ
and ω are related parameters (Jang *et al*., 2005):

(4) |

(5) |

(6) |

(7) |

For any of various classes of fuzzy s-norm, there is a fuzzy t-norm. Eq.
8 to 11 represent the t-norm formulation in classes Dombi,
Dubois-Prade, Yager and Min. Parameters a, b, , λ, ω and α are
same as respective s-norm classes (Jang *et al*., 2005):

(8) |

(9) |

(10) |

(11) |

**FUZZY CA FOR RANDOM NUMBER GENERATING**

The basis of most random number generators is to generate a sequence of random bits, convert the base and map it to the desired domain. Using binary cellular automata, one dimensional CA and applying the update rules such as rules 30, 90, 105, 150 and 165 (by Wolfram naming) one can generate pseudo random bits. In each step in linear binary CA one pseudo random bit can be generated. By iterating the process n times and generating n bits, or by running n parallel CA and generating one bit from each, a random number with desired precision in the specified domain is obtained. Variable n is used to adjust the precision.

Generating large number of pseudo random numbers either serially or in parallel, can be very time consuming and burdensome. It is the case for generating high precision decimal fraction random numbers which require many bits. To solve this problem, this study introduces a fuzzy cellular automaton which by exploiting fuzzy operators and mapping the update rules (such as rules 30, 90 and 165) to fuzzy space it can generate a random number in each step of automata. For example rule 90 can be formulated as in Eq. 12.

(12) |

where, b = x_{i} (t), a = x_{i-l} (t), c = x_{i+l}
(t) and b' =x_{i} (t+1).

Now by replacing NOT operators by a fuzzy complement operator, OR operators by a fuzzy s-norm class, AND operators by a fuzzy t-norm class, it will give us the fuzzy equivalent of rule 90. There can be various expressions of fuzzy rule 90 by employing different fuzzy operator classes and also by choosing different values for operator variables.

If the cell values of linear CA consist of decimal numbers from domain [0, 1] (the state space is concrete) and border cells are assumed neighbors (linear CA is loop), applying fuzzy rule 90 to update the states of cells leads each of the cells of FCA behave like a random number generator.

The question arise here that in conversion of rule 90 to a fuzzy rule which fuzzy operators must be used and what should be the values of the parameters of these operators. In this study fuzzy complement, s-norm and t-norm operators are all from Yager class and value of parameter ω in all operators is same and equal to the value of central cell. As shown in Eq. 12, the value of cell in time t + 1 only depends on the value of neighbor cells in time t. Using the central cell value as the parameter for fuzzy operator can be useful in increasing the disorder and hence increasing randomness in the generated numbers.

**ad5**

**EXPERIMENTAL RESULTS**

To evaluate the proposed approach, first the capability of CA in random number generation is evaluated. To this end a binary linear CA is simulated. The number of cells is 100, neighborhood radius is 1 and cell update rule is rule 90. In this simulation 1000 random bits are generated and number of ones in the sequence is counted. Running the simulation 100 times, statistical indexes average, standard deviation and scattering length is computed for the number of ones in sequences of 1000 bits. The simulation result is shown in Table 2.

The CA approaches proves to be a successful way in generating random numbers in that the generated numbers are almost uniformly distributed. To evaluate the performance of the proposed approach, the generated numbers are compared with the numbers generated with proposed FCA and numbers generated with MATLAB random number generator.

To this end, 800’000 random number is generated with FCA and MATLAB RNG, then each of the random number sets are divided into 20 equal intervals and the frequency of random numbers belonging to each interval is computed. Finally, the average, standard deviation and scattering length for every interval of each set is calculated. Table 3 presents the statistical indexes for FCA and MATLAB random number generator. According to the results the proposed FCA using the fuzzy rule 90 outperforms the MATLAB RNG in the terms of uniformity.

Figure 2 represents the histogram diagram of dividing FCA generated random numbers into sub-intervals and Fig. 3 represents the same diagram for random numbers generated with MATALB RNG. As it can be seen from the Fig. 2 and 3, the uniformity of random numbers generated with FCA RNG is improved compared to the MATLAB RNG.

According to the simulations fuzzy cellular automata incorporating the fuzzy rule 90 is capable of generating more unified random numbers and if implemented on hardware it can generate a random number on each clock pulse. Therefore, the very high speed of this approach along with the quality of generated random numbers is the advantages of the proposed approach.

Table 2: | Statistical index for evaluation of CA in random number generation |

Table 3: | Statical index for uniformity evaluation of proposed FCA compared to MATLAB RNG |

Fig. 2: | Histogram diagram for FCA random number generator |

Fig. 3: | Histogram diagram for MATLAB Random Number generator |

Meanwhile, the initialization of automaton is yet an issue, as it can lead the automaton to the Garden of Eden configuration which results in short frequency periods in the generated numbers.

**CONCLUSION**

This study introduces a novel approach for uniformly generating random numbers by modifying fuzzy operators to operate on the cellular automata update rules. Employing different classes of fuzzy operators complement, s-nor and t-norm makes the FCA behave in different ways. The simulation results showed that the proposed approach generates more uniform random numbers compared to the MATLAB RNG. The nature of the proposed approach makes it suitable for hardware implementation where it can generates the random numbers in a fast way.

As an open issue is the initialization of first run of FCA which is yet to be solved. An unsuitable initialization may lead the FCA to be trapped in Garden of Eden configuration. Considering the applicability of various update rules other than rule 90, studying the impact of different neighborhood structures of CA, combining different fuzzy operator classes and optimally tuning the relative variables for random number generation are the other issues which can be addressed to increase the quality of the random numbers generated within this approach.

" class="btn btn-success" target="_blank">View FulltextTwo-layer Cellular Automata Based Cryptography

*Trends in Applied Sciences Research,
2012, 7(1), 68-77.*

Empowering vehicle tracking in a cluttered environment with adaptive cellular automata suitable to intelligent transportation systems

*IET Intelligent Transport Systems,
2017, (), .
DOI: 10.1049/iet-its.2015.0253*

*International Journal of Intelligent Transportation Systems
Research,
2017, 15(3), 127.
DOI: 10.1007/s13177-016-0127-x*