Information Technology Reference
In-Depth Information
Table 1.
The
CA
Rule Table
With XOR (linear
CA
) With XNOR (complemented rule)
rule 60 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
(
t
) rule 195 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
(
t
)
rule 90 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
+1
(
t
) rule 165 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
+1
(
t
)
rule 102 :
q
i
(
t
+1)=
q
i
(
t
)
⊕ q
i
+1
(
t
) rule 153 :
q
i
(
t
+1)=
q
i
(
t
)
⊕ q
i
+1
(
t
)
rule 150 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
(
t
)
⊕ q
i
+1
(
t
) rule 105 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
⊕ q
i
(
t
)
⊕ q
i
+1
(
t
)
rule 170 :
q
i
(
t
+1)=
q
i
+1
(
t
)
rule 85 :
q
i
(
t
+1)=
q
i
+1
(
t
)
rule 204 :
q
i
(
t
+1)=
q
i
(
t
)
rule 51 :
q
i
(
t
+1)=
q
i
(
t
)
rule 240 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
rule 15 :
q
i
(
t
+1)=
q
i
−
1
(
t
)
2 CA Preliminaries
A
Cellular Automata
(CA) consists ofa number ofcells arranged in a regular
manner, where the state transitions ofeach cell depends on the states ofits two
neighbors and itself(Fig. 1). Each cell stores 0 or 1 in GF(2). The next state
function (local transition function) of a cell is defined by one of the 256 (2
2
3
)
rules [4]. Some ofthe XOR and XNOR rules ofGF(2)
CA
are noted in Table 1.
A
CA
employing only XOR rules is referred to as Linear, while the ones using
both XOR and XNOR are referred to as Additive
CA
.A
CA
with XNOR rules
can be viewed as a
CA
with XOR rules and an inversion vector
F
to account
for the XNOR logic function.
Such a CA we have marked as GF(2) CA. In order to enhance the computing
power ofsuch a three neighborhood structure, GF(2
p
) CA [8] has been proposed.
2.1
GF(2
p
)CA
The Fig. 1 depicts the general structure ofan
n
-cell GF(2
p
) CA. Each cell ofsuch
a CA having
p
number ofmemory elements can store an element
{
0
,
1
,
2
, ...,
2
p
−
1
}
in GF(2
p
). In
GF
(2
p
) [5], there exists an element
α
that generates all the
non-zero elements,
α, α
2
, ....α
2
p
−
1
, ofthe field.
α
is termed as the
generator
.
α
can be represented by a
p×p
matrix having its elements as
{
0
,
1
}∈GF
(2). The
matrix representation
ofelement
α
j
(
j
=2
,
3
, ···,
(2
p
−
1)) for
p
= 2 is shown in
Fig. 2.
The connections among the cells ofthe CA are weighed in the sense that to
arrive at the next state
q
i
(
t
+1) of
i
th
cell, the present states of(
i −
1)
th
,
i
th
and (
i
+1)
th
are multiplied respectively with
w
i−
1
,
w
i
and
w
i
+1
and then added.
The
addition
and
multiplication
follows the rule of addition and multiplication
defined in GF(2
p
). So, under three neighborhood restriction, the next state of
the
i
th
cell is given by -
q
i
(
t
+1)=
φ
((
w
i−
1
,q
i−
1
)
,
(
w
i
,q
i
)
,
(
w
i
+1
,q
i
+1
)).
φ
denotes the local transition
function of the
i
th
cell and
w
i−
1
,w
i
&
w
i
+1
∈
GF(2
p
) specify the weights of
interconnection. A three neighborhood
n
cell GF(2
p
) CA is equivalent to
np
cell
3
p
neighborhood GF(2) CA. The structure ofGF(2
p
) CA provides hierarchy and
abstraction that can be exploited in many applications [8].
