Content addressable memory implementation with random access memory

DETAILED DESCRIPTION OF THE INVENTION In the following, the invention is described in detail with reference to the drawings and the prior ad.
The addresses of the memory locations of the shown random access memories correspond to the number of the rows when counted from above.
Bit-addressable RAMs have been used throughout.
The known concept of a CAM is shown in FIG.
1.
The keyword is fed into the CAM, which activates a matching line, when a match is encountered at a memory location (row).
Activation usually consists of applying a 1 to a particular output line of the device.
The key and the stored data have a width of W bits with W being 6 for the described example.
The number of matching lines m.
sub.
o to m.
sub.
N-1 is N.
It is assumed that 000110 is stored at row 1.
Consequently, a 000110 key input results in an activation of line m.
sub.
1.
The implementation of such a CAM according to the invention (FIG.
2) is based on using three known bit-addressable RAMs with a 4.
times.
N-bit capacity.
Thus, four words of N-bit width can be stored.
In the following, word and row are used as synonyms.
Additional address and control lines have been omitted for the sake of simplicity.
In the RAMs, words are stored in such a way that a 1 occurs at the first row of the first RAM, a 1 occurs at the second row of the second RAM, and a third 1 occurs at the third row of the third RAM.
The keyword is divided into three subsets of two bits, respectively, by an appropriate division of the keyword input lines.
The subsets are applied to the address lines of the RAMs, potentially addressing four rows of the particular memory.
The addressed data are applied to the output lines of three RAMs, respectively.
The three sets of output data are bitwise ANDed the following gate.
The AND operation, thus, results in a N-bit word with a 1 at the bit position where all input data sets (which are the output of the preceding RAMs) show a 1, too.
In the example, the keyword 000110 is applied to the RCAM.
The subsets of the keyword are 00, 01, and 10, respectively