Information Technology Reference
In-Depth Information
b
Transient
a
Transient
c
Transient
d
Transient
Stable State
Fig. 1.
Model of Associative Memory
In this paper we propose the design of a
CAM
for pattern recognition. The
CAM
basically acts as an
Associative Memory
which is also referred to as
Con-
tent Addressable Memory
. Thus the acronym
CAM
stands for both
Cellular
Automata Machine
acting as
Content Addressable Memory
.
The memorizing
capacity of
CAM
, as established in this paper, can be found to be
better than that of conventional Hopfield Net by 33%.
2 Cellular Automata Preliminaries
A
Cellular Automaton
(
CA
) consists of a number of cells organized in the form of
a lattice. It evolves in discrete space and time. The next state of a cell depends on
its own state and the states of its neighboring cells. In a two state 3-neighborhood
CA
, there can be a total of 2
2
3
- that is, 256 distinct next state functions of a
cell referred to as the
rule
of
CA
cell [7].
A special class of
CA
referred to as
Multiple Attractor CA
(
MACA
) designed
with rule vector
<
150
,
102
,
60
,
150
>
is shown in
Fig.2
. Its state space gets
divided into four attractor basins; each basin contains an attractor (with self
loop) and transient states.
MACA
employing linear/additive
CA
rules have
been widely studied in the topic [8].
Generalized Multiple Attractor Cellular Automata
(GMACA) em-
ploys non-linear CA rules with attractor cycle length greater than or equal to
1. It can e
"
ciently model an associative memory [9,10,11].
The
Fig.3
illustrates
the state space of a 4-cell
GMACA
with rule vector
<
202
,
168
,
218
,
42
>
. The
state space of this
CA
is divided into two attractor basins. The non-cyclic states
are referred to as
Transient States
in the sense that a
CA
finally settles down in
one of its attractor cycles after passing through such transient states.
In order to model an
associative memory
for a given set of patterns
P
=
{P
1
, ···, P
i
, ···P
k
}
, following two relations has to be satisfied by the
GMACA
.
R1:
Each attractor basin of the
GMACA
should contain one and only one
pattern (
P
i
) to be learnt in its attractor cycle; the corresponding basin is referred
to as
P
i
-basin.
R2:
The hamming distance (
HD
) of each state
S
i
∈P
i
-basin with
P
i
is
lesser than that of
S
i
with any other
P
's. That is,
HD
(
S
i
, P
i
)
<HD
(
S
i
, P
j
),
P
j
∈P
and
P
j
=
P
i
.
While the relation
R1
ensures uniqueness of the stored patterns, the relation
R2
ensures recognition of patterns with distortion due to noise.
