Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-01-09
2002-05-14
Ho, Hoal V. (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230030, C365S230060, C711S108000
Reexamination Certificate
active
06388909
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an associative memory, more particularly to an associative memory for developing the address of a storage location storing therein data detected by the longest coincidence data detection principle.
2. Description of the Background Art
As is known in the art, the associative memory, or often called CAM (Content Addressable Memory), is adapted to include storage locations and develop data representative of the address of one of the storage locations which contains data coincident with input or reference data entered. The associative memory is advantageously applicable to searching for routing information in telecommunications network systems, for example.
With the longest coincidence data detection system, the associative memory is adapted to receive input data and produce output data representative of the address of a storage location which stores therein data of which the entire bits are coincident with the corresponding bits of the input data or otherwise data which have the most bits continuous from the MSB (Most Significant Bit) position toward the LSB (Least Significant Bit) position are coincident with the corresponding bits of the input data. The CAM memory is generally provided with the measures of masking a specific bit or bits of a reference word of data to exclude the bit or bits from the coincidence detection.
An example of the longest coincidence data detection system is disclosed in Japanese patent laid-open publication No. 7782/1999, equivalent to U.S. Pat. No. 6,098,147 to Mizuhara. The apparatus for detecting the longest coincidence data disclosed in the U. S. patent compares a word of data stored in the associative memory and coincident with a reference word of data with bits from the LSB position thereof masked being increased on the bit-by-bit basis by an incrementing device such as a counter to determine which bit position or positions continuous from the MSB of the stored word of data is or are coincident with a corresponding bit or bits of the reference word of data.
The system of increasing the mask bits one by one to detect the longest coincidence data requires an extensive period of time until a coincidence is found out. For example, an application which is popular to the telecommunications network systems and in which an address value represented by 32 bits is input to an associative memory as a reference word of data would require to repeat comparison operations 32 times at the worst. As taught by the U.S. patent, the CAM unit is divided into four subsections, for example, each including eight bit positions, or one byte length, requiring the comparison operations to be repeated eight times.
In an application of the CAM system structured as mentioned above to searching for routing information in the network systems, the extensive period of time required for finding coincidence would result in a reduced throughput, thus causing the efficiency of the network to unfavorably be decreased.
The comparison operation of the CAM unit suffers from charging and discharging the strayed capacitance caused by a lot of lengthy wiring. The conventional comparison operations continuously and repetitively accomplished in the CAM unit would consume much more electric power.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved associative memory.
More specifically, it is another object of the present invention to provide an associative memory for accomplishing the longest coincidence data detection in a minimum period of time.
Further, it is another object of the present invention to provide an associative memory advantageously applicable to telecommunications network systems.
It is still another object of the present invention to provide an associative memory with its power consumption minimized.
In accordance with the present invention, an associative memory comprises: an array of CAM cells each for storing therein a bit of data fed on a bit line, said array being formed in rows corresponding to words of the data and columns corresponding to bits of the word; each of said CAM cells comprising a first transistor circuit taking either one of a first and a second state, the first and the second state representing that the bit stored in said CAM cell is consistent and inconsistent, respectively, with a bit of a reference word fed on the bit line; a first plurality of logic circuits provided correspondingly to the rows, each of said first plurality of logic circuits producing a first signal representing that the first transistor circuits of all of the CAM cells in corresponding one of the rows take the first state, and otherwise which of the first and second states the first transistor circuit of the CAM cell at an LSB position of the corresponding one row takes; a second plurality of logic circuits provided correspondingly to the columns, each of said second plurality of logic circuits detecting whether or not all of the first transistor circuits in corresponding one of the columns take the first state, and producing a second signal when all of the first transistor circuits in the corresponding one column take the first state; and a plurality of drive circuits provided correspondingly to the columns for each receiving a bit of an input or reference word, and driving the bit line of said CAM cells in corresponding one of the columns in response to the bit received; each of said drive circuits being operative in response to the second signal produced from corresponding one of said second plurality of logic circuits to mask the bit line to cause the first transistor circuits of all of the CAM cells in the corresponding one column to take the first state; whereby the first signal is developed from the first logic circuit in one of the rows which includes the first transistor circuits all of which take the first state to thereby accomplish a longest coincidence data detection.
More specifically, an associative memory includes an array of CAM cells each having a transistor indicating a result from comparing a stored bit with a reference bit. The transistors are connected in serial in each row of the array to form a NAND circuit producing a signal representing that the bits stored in all the cells in the row are consistent with the reference bits or otherwise that the cell at the LSB of the row stores a bit consistent with a reference bit. Each column of the array includes a logic circuit for masking the bits except those continuous from the MSB toward the LSB which correspond to the bits of a word having the most bits continuous from the MSB toward the LSB and consistent with the bits of the reference word among the stored words. The NAND circuit in a row of the cells storing a word having the most bits continuous from the MSB toward the LSB and consistent with the corresponding bits of a reference word develops a signal representing the longest coincidence data detected.
REFERENCES:
patent: 6098147 (2000-09-01), Mizuhara
patent: 6175514 (2001-01-01), Henderson et al.
patent: 6181591 (2001-01-01), Miyatake et al.
patent: 6230236 (2001-05-01), Schultz et al.
patent: 11-7782 (1999-01-01), None
Odagiri Hideaki
Takahashi Noriaki
Ho Hoal V.
Oki Electric Industry Co. Ltd.
Rabin & Berdo P.C.
LandOfFree
Associative memory for accomplishing longest coincidence... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Associative memory for accomplishing longest coincidence..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Associative memory for accomplishing longest coincidence... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858626