Information Technology Reference
In-Depth Information
0101
1010
0100
1011
0010
1101
0011
1100
1110
0111
0110
1111
0000
0001
1000
1001
Zero tree
Attractors { 0, 1, 8, 9}
rule < 150, 102, 60, 150 >
Fig. 2.
State space of a 4-cell
MACA
divided into four attractor basins
1 1 0 1
0 1 0 0
1 0 0 0
1 1 0 0
1 0 0 1
0 1 1 1
P'
1 0 1 0
0 0 0 1
0 0 1 1
0 1 1 0
1 0 1 1
0 1 0 1
0 0 1 0
1 1 1 0
P
attractor-1
0 0 0 0
1
attractor-2
P
1 1 1 1
2
rule vector : < 202, 168, 218, 42>
Fig. 3.
State space of a GMACA divided into two attractor basins
Example 1
Suppose, we want to recognize two patterns P
1
= 0000
and
P
2
= 1111
of length 4 with single bit noise. We first synthesize a CA (rule
vector) for which the state transition behavior of GMACA is similar to that of
Fig.3
, that maintains both
R1
and
R2
.
It learns two patterns, P
1
= 0000
and P
2
= 1111
. The state P
= 0001
has
the hamming distances 1 and 3 with P
1
and P
2
respectively. Let P be given as
the input and its closest match is to be identified with one of the learnt patterns.
The recognizer designed with the GMACA of
Fig.3
is loaded with P=
0001
. The
GMACA returns the desired pattern P
1
after two time steps.
3 Synthesis of CA Machine (
CAM
)
The
CAM
is synthesized around a
GMACA
. The synthesis of
GMACA
can be
viewed as the training phase of
CAM
for Pattern Recognition. The
GMACA
synthesis scheme outputs the rule vector of the desired
GMACA
that can rec-
ognize a set of given patterns with or without noise.
3.1 GMACA Evolution
The
GMACA
synthesis procedure consists of three phases. It accepts the pat-
terns to be learnt as the input. It cycles through these phases till desired
GMACA
is reached as its output or the specified time limit gets elapsed with
null output.
Let, the input be denoted as
k
number of
n
bit patterns to be learnt. The
output should be an
n
-cell
GMACA
with
k
number of attractor basins, with