Associative Memory

Associative Memory
• A memory unit accessed by content is called an
associative memory or content addressable memory
(CAM).
• This type of memory is accessed simultaneously and in
parallel on the basis of data content rather than by
specific address or location.
• The time required to find an item stored in memory can
be reduced considerably if stored data can be identified
for access by the content of the data itself rather than
by an address.
• When a word is written in an associative memory, no
address is given.
 Associative Memory
• When a word is to be read from an associative memory,
the content of the word, or part of the word, is
specified.
• The memory locates all words which match the
specified content and marks them for reading.
• An associative memory is more expensive than a RAM
because each cell must have storage capability as well
as logic circuits for matching its content with an
external argument.
• For this reason, associative memories are used in
applications where the search time is very critical and
must be very short.
 Associative Memory
• The block diagram of an
associative memory is shown
in Fig. consists of a memory
array and logic for m words
with n bits per word.
• The argument register A and
key register K each have n bits,
one for each bit of a word.
• The match register M has m
bits, one for each memory
word.
Fig: Block diagram of associative memory.
 Associative Memory
• Each word in memory is
compared in parallel with the
content of the argument
register.
• The words that match the bits
of the argument register set a
corresponding bit in the match
register.
• After the matching process,
those bits in the match register
that have been set indicate the
fact that their corresponding
words have been matched. Fig: Block diagram of associative memory.
 Associative Memory
• The key register provides a
mask for choosing a particular
field or key in the argument
word.
• The entire argument is
compared with each memory
word if the key register
contains all 1's.
• Otherwise, only those bits in
the argument that have 1's in
their corresponding position
of the key register are
Fig: Block diagram of associative memory.
compared.
 Associative Memory
• For example, suppose that the
argument register A and the
key register K have the bit
configuration shown below.
• Only the three leftmost bits of
A are compared with memory
words because K has 1's in
these positions.

Fig: Block diagram of associative memory.

 Associative Memory
• Reading is accomplished by a
sequential access to memory
for those words whose
corresponding bits in the
match register have been set.

Fig: Block diagram of associative memory.

 Associative Memory
• The relation between the memory array and external
registers in an associative memory is shown in Fig.
• The cells in the array are marked by the letter C with two
subscripts. The first subscript gives the word number and the
second specifies the bit position in the word.

Fig: Associative memory of m word, n cells per word

 Associative Memory
• The cell Cij is the cell for bit j in word i. A bit Aj in the
argument register is compared with all the bits in
column j of the array provided that Kj = 1. This is done
for all columns j = 1, 2, . . . , n.

Fig: Associative memory of m word, n cells per word

 Associative Memory
• If a match occurs between all the unmasked bits of the
argument and the bits in word i, the corresponding bit M1 in
the match register is set to 1.
• If one or more unmasked bits of the argument and the word do
not match, M1 is cleared to 0.

Fig: Associative memory of m word, n cells per word

 Associative Memory
• The internal organization of a typical cell Cij is shown in Fig.
• It consists of a flip-flop storage element Fij and the circuits for
reading, writing, and matching the cell.
• The input bit is transferred into the storage cell during a write
operation.

Fig: One cell of associative memory

 Associative Memory
• The bit stored is read out during a read operation.
• The match logic compares the content of the storage cell
with the corresponding unmasked bit of the argument and
provides an output for the decision logic that sets the bit in
M i.

Fig: One cell of associative memory

 Associative Memory
• The match logic for each word can be derived from the
comparison algorithm for two binary numbers.
• First, we neglect the key bits and compare the
argument in A with the bits stored in the cells of the
words.
• Word i is equal to the argument in A if Ai = Fij for j = 1, 2,
...,n.
• Two bits are equal if they are both 1 or both 0.
• The equality of two bits can be expressed logically by
the Boolean function

• where xj = 1 if the pair of bits in position j are equal;

otherwise, xj = 0.
 Associative Memory
• For a word i to be equal to the argument in A we must
have all xj variables equal to 1.
• This is the condition for setting the corresponding
match bit M, to 1.
• The Boolean function for this condition is
 Associative Memory
• We now include the key bit Kj in the comparison logic.
• The requirement is that if Kj = 0, the corresponding bits
of Aj and Fij need no comparison.
• Only when Kj = 1 must they be compared. This
requirement is achieved by ORing each term with K’j
thus:

• When Kj = 1, we have K’j = 0 and xj + 0 = xj .

• When Kj = 0, then K’j = 1 and xj + 1 = 1.
• A term (xj + K’j) will be in the 1 state if its pair of bits is
not compared.
 Associative Memory
• The match logic for word i in an associative memory
can now be expressed by the following Boolean
function:

• Each term in the expression will be equal to 1 if its

corresponding Kj = 0.
• If Kj = 1, the term will be either 0 or 1 depending on the
value of xj.
• A match will occur and Mi will be equal to 1 if all terms
are equal to 1 .
 Associative Memory
• If we substitute the original definition of xj, the Boolean
function can be expressed as follows:
 Associative Memory
• READ Operation:
• If more than one word in memory matches the
unmasked argument field, all the matched words will
have 1's in the corresponding bit position of the match
register.
• It is then necessary to scan the bits of the match
register one at a time.
• The matched words are read in sequence by applying a
read signal to each word line whose corresponding M,
bit is a 1.
 Associative Memory
• READ Operation:
• In most applications, the associative memory stores a
table with no two identical items under a given key.
• In this case, only one word may match the unmasked
argument field.
• By connecting output Mi directly to the read line in the
same word position (instead of the M register)
• The content of the matched word will be presented
automatically at the output lines and no special read
command signal is needed.
 Associative Memory
• WRITE Operation:
• An associative memory must have a write capability for
storing the information to be searched.
• Writing in an associative memory can take different
forms, depending on the application.
• If unwanted words have to be deleted and new words
inserted one at a time, there is a need for a special
register to distinguish between active and inactive
words.
• This register, sometimes called a tag register, would
have as many bits as there are words in the memory.
• For every active word stored in memory, the
corresponding bit in the tag register is set to 1.
 Associative Memory
• WRITE Operation:
• A word is deleted from memory by clearing its tag bit to
0.
• Words are stored in memory by scanning the tag
register until the first 0 bit is encountered.
• This gives the first available inactive word and a
position for writing a new word.