m
(2.6)
where [2n, m] is the least common multiple of the 2n − 1 and m. Following (2.6), the maximum period can consequently reach the ideal one 2n − 1 when 2n − 1 is not devided by m.
In addition, it is obviously to be seen that the implementation of Leap Ahead LFSR approach need a
lower area overhead compared to that of multiple LFSRs approach. The reason for this fact is multiple LFSRs design includes m × n stages (or registers), wheareas Leap–Ahead architecture need only m
registers. Leap–Ahead LFSR trully gives a considerable achievement in comparison with other methods
based on LFSR.

CA–based PRNG

\label{cabased-prng}
Besides LFSR, Cellular Automata (CA) is widely used in generating random number. This approach was firstly proposed by S.Wolfram in [23], considered as one–dimensional CA which includes a line of
cell with values belong to the set {0, 1}. These values are simultaneously refreshed due to a fixed rule.
Two–dimensional CA and Three–dimensional CA have been recently introduced with a higher level in
complexity. Our work will only consider One–dimensional CA as case study.
Boundary

. . .

\label{section-10}

. . .

\label{section-11}
Boundary
Figure 2.4: A One–dimensional two–neighbor CA
It can be shown in Fig.2.4 that an One–dimensional CA includes an array of cells which progress in discrete time steps by using some specified rules. These rules can be seen as the transformation functions from this time step to another one. More clearly, the next state of each cell depends on its own state and the states of its nearby neighbors at the previous time step. It can be mathematically represented as
si(t + 1) = f (si(t), si−k (t), …, si+r(t)) , (2.7)
where f is the transformation function, si(t), si(t + 1) are the states of cell ith at time steps t and t + 1, and si−k (t), …, si+r(t) are the states of its neighbors at time step t (i,k are positive integer numbers). For simplicity reason, we will investigate CA with two neighbors: si−k and si+r for a specified function f . With such assuming, following Wolfram’s numbering system for One–dimensional CA, there are total 256 CA rules that depend on three cells. For example, there are two rules [23] that seem best as random number generator using CA, rule 30 and 45, given by:
and
si(t + 1) = (si−k (t) + si(t) + si+r(t) + si(t)si+r(t)) mod 2
or si(t + 1) = si−k (t) XOR (si(t) OR si+r(t)) , (rule 30)
si(t + 1) = (1 + si−k (t) + si+r(t) + si(t)si+r(t)) mod 2
or si(t + 1) = si−k (t) XOR (si(t) OR (NOT (si+r(t)))) , (rule 45)
(2.8)
(2.9)
About the boundary problem in CA, there can be two solutions. The first one is that we can consider CA with null boundary condition, i.e., the cells 1th and nth take the zeros as its virtual left, right neighbors, respectively. This idea can be found in [11]. The second solution was proposed in [22] where a one–dimensional ring network is investigated. Due to this boundary condition, the first cell
and the last cell are adjacent, therefore, the negative direction −k from the first cell will be from
Cell(0) to Cell(n − 1).
Single rule CA approach
In this first approach, only one rule will be considered in condition of using the appropriate neighbors, i.e., suitable values of k and r, and a corresponding boundary condition. Besides rule 30, the following others will be considered in our implementation:
si(t + 1) = si−k (t) XOR si+r(t), (rule 90) (2.10)
and
si(t + 1) = NOT (si−k (t) XOR si+r(t)), (rule 165) (2.11)
These rules are interested us because they have been proved the quality with respect to random number generator in lots of work in literature.
Mixed rule CA approach
In the second approach, the rule in each cell change dynamically [7] based on considering an implicit structure of each cell as shown in Fig.2.5. It can be show in this configuration, each cell includes two small cell: upper cell and lower cell in which the first one with its rules is used to define what rule will be used in the second one to determine the output state. This can be seen as a hierachical structure where the upper cell navigates the lower cell, however, it replies on the state of the lower cell to enter in the next time step. Note that there are the difference not only in the rules used, but also in the neighbors (depend on values of k and r applied) for each small cell.
The behavior of this method can be described as follows: throughout each time step, the upper cell
applies its rule based on its neighbors to calculate its next state, at the same time, the lower cell checks

Figure 2.5: Behavior of the mixed rule CA in which each cell is considered including two virtual cells:
Upper cell and Lower cell
the current state of the upper cell to decide the rule to be use, then the same behavior will be carried in the lower cell but with the different rule and neighbors. Note that in this architecture, the lower cell uses the current state not the next state of the upper cell because these operations are implemented simultaneously.