Information Technology Reference
In-Depth Information
1
i-1
i
i+1
n
Input
Input
Input
Input
Input
FF
1
FF
2
FF
p
Output
Output
Output
Output
Output
p
w
i
p
p
p
w
w
i-1
i+1
Next State Function
p
F
i
Fig. 1.
General structure of a GF(2
p
) CA (For p=1, it's a conventional GF(2) CA)
An
n
cell GF(2
p
) CA can be characterized by the
n×n
characteristic matrix
T
, where
w
ij
,
if the next state of the
i
th
cell
depends on the present state of the
j
th
cell by a weighed
w
ij
∈ GF
(2
p
)
0
,
otherwise
F = an n symbol inversion vector with each ofits element in GF(2
p
).
The state ofa GF(2
p
) CA at time
t
is an
n−
symbol string, where a symbol
∈
GF(2
p
) is the content ofa
CA
cell. If
s
t
represents the state ofthe automata
at the
t
th
instant oftime, then the next state, at the (
t
+1)
th
time, is given by
s
(
t
+1)
=
T ∗ s
t
+
F
, and
s
(
t
+
n
)
=
T
n
∗ s
t
+(
I
+
T
+
T
2
+
···
+
T
n−
1
)
∗ F.
The '
∗
' and '+' operators are the operators ofthe Galois Field GF(2
p
). Ifthe
F
vector ofGF(2
p
)
CA
is an all zero vector, the
CA
is termed as linear
CA
, else
it is an Additive
CA
.
In the CA state transition graph, ifall the states lie in some cycles, it is
called a group CA. For a group CA, det[T]
= 0. Ifthe characteristic matrix T is
singular, that is det[T] = 0, then the CA is a non-group CA. The T matrix ofthe
example non-group GF(2
2
) CA ofFig. 2 has the elements in GF(2
2
). Its state
transition graph has a single component ofan inverted tree with a root (a node
with self-loop) referred to as 'Attractor'. Consequently, such a CA is marked as
Single Attractor CA (
SACA
).
T
ij
=
Definition 1
Dependency matrix D - if all the non-zero weights in Tare re-
placed by 1 then it is referred to as the dependency matrix of the CA in GF(
2
p
).
For
p
= 1, dependency matrix is the characteristic matrix T ofGF(2) CA (Fig.
2).
