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.
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
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.