Information Technology Reference
In-Depth Information
each attractor basin having a unique pattern from the input patterns to be
learnt.
Phase I
- Since, the state transition diagram of a
GMACA
can be conceived
as a graph, we first randomly generate
k
number of
directed graphs
with each
node coded as an
n
-bit string. The cycle length
l
permissible for the generated
graph is assumed to be less than or equal to
L
max
; where
L
max
is the
maximum
permissible length
of the attractor cycle. Each graph represents a basin of the
candidate
GMACA
to be synthesized; while its cycle represents an attractor
cycle. Each directed graph has a unique pattern
P
i
in its attractor cycle, while
those with limited noise added to
P
i
are the patterns in the
P
i
-basin.
The number of nodes
p
of each graph is equal to the number of states in the
corresponding basin - that is, the patterns without or with specified noise. So,
n
r
r
max
p
=
(1)
r
=0
where,
r
is the number of noisy bits and
r
max
is the
maximum permissible noise
that can be tolerated by the
GMACA
based pattern recognizer. After mapping
a particular pattern (say
P
i
to be learnt) on to the cyclic node of a graph, we
randomly map other patterns to be covered by the
P
i
basin at different nodes
of same graph. Note that the
P
i
-basin of the
GMACA
to be synthesized covers
the states with permissible noise of
r
bits (
r
=0to
r
max
) added to
P
i
. A design
example follows.
0 1 0 0
1 0 0 0
1 1 1 0
1 0 1 1
1 1 0 1
0 0 0 1
0 1 1 1
Basin-2
Basin-1
1 1 1 1
0 0 1 0
0 0 0 0
Patterns To Be Learnt
(a)
Directed Graphs generated in Phase I
For '2nd' cell : -
Neighborhood :
Next State:
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
0
Basin
Present State
0 1 0 0
1 0 0 0
0 0 0 1
0 0 0 0
0 0 1 0
Next State
0 0 0 1
0 0 0 1
0 0 0 0
0 0 1 0
0 0 0 1
1
1
1
0
1
0
0
1
For '3rd' cell : -
Neighborhood :
Next State:
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
1 1 1 0
1 0 1 1
1 1 0 1
0 1 1 1
1 1 1 1
0 1 1 1
0 1 1 1
0 1 1 1
1 1 1 1
1 1 1 1
1
1
1
0
1
0
0
0 / 1
2
Note :
Next State for 3rd cell as per the
'Collision'
second row of state transition table is 0,
while it is 1 as per the 4th row of
state transition table for Basin-1
(b)
State Transition Table for graphs
of Fig. (a)
(c) Generation of Rule Vector as per Phase III
with illustration of Collision
Fig. 4.
Randomly Generated Directed Graphs with state transition tables and CA
Rules
