Tertiary CAM cell

Details Tertiary CAM cell Tertiary CAM cell

2002-07-25

2004-08-24

Le, Vu A. (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070

Reexamination Certificate

active

06781856

ABSTRACT:

FIELD OF INVENTION
The present invention relates generally to semiconductor memory, and more particularly to a tertiary CAM cell.
BACKGROUND OF THE INVENTION
Many applications require searching information at high speed. In many network devices, such as switches or routers, data packets are transferred based on the contents of embedded address information. Thus, in order to achieve a high data transfer rate, network systems must be able to perform very high speed searches and comparisons. One class of circuits useful for this function is a content addressable memory or CAM. It should be noted that although the following discussion is set within the context of a networked system, there are many other applications which require high speed searching and comparison, and which may also therefore benefit from the present invention. For example, the tag field of a fully associative cache memory also requires high speed searching and may be implemented using a CAM.
It may be useful to compare a CAM against a traditional memory device, such as a random access memory (RAM). To an extent, CAM and RAM device operate conversely. For example, a RAM may be read by presenting it with a read command and an address. The RAM responds by outputting the data stored at the specified address. However, when a CAM is read, it is presented with a data sample, and the CAM returns an match signal indicating whether the data sample is stored in the CAM, and if so, an address within the CAM which contains the data which matched the sample.
Network routers and switches generally employ a matching function, where a portion of a packet, such as an address field, is compared to a list of data entries. The list is often referred to as a database.
FIG. 1
is a block diagram of an exemplary CAM device
100
, which includes a CAM array
110
for storing the database, a match detection circuit
120
for detecting matches, and optionally a priority encoder
130
for selecting and outputting a matching address in a priority order, when appropriate. The CAM device also includes a controller
140
, for controlling the operation of the CAM array
110
, match detection logic
120
, and priority encoder
130
, as well as for interfacing the CAM device
100
to other devices via the data
150
a,
address
150
b,
and control
150
c
lines. Commercially available CAM devices may support, for example, searching a 136-bit wide data sample against a database having up to 16,384 entries. Commercially available CAM devices may be searched at rates up to 100 million searches per second. This ability for CAMs to quickly search relatively wide data words against relatively large databases at high speeds makes them highly useful in applications such as network routing and switching.
There are two types of searches which are of interest, namely a search for the exact match and the partial match search. In the exact match search, an entry stored in the CAM will match the data sample only if the data sample and the entry match bit for bit. In a partial match search, the search may be conducted on only a subset of bits in the word. That is, the CAM entries are permitted to specify a third “don't care” state in addition to the logical “0” and “1” states. When a partial match search is conducted, CAM entries will match a data sample as long as each bit in the entry set at a logical “0” or “1” states match the corresponding portion of the data sample.
CAMs having entries which only support the logical “0” and logical “1” states are known as binary CAMs, and can only support exact match searches. CAMs having entries which also support the use of the “don't care” state are known as ternary CAMs, and can be used for partial match searches. (These CAMs also support exact match searches when an entry does not contain any “don't care” states.)
In a ternary CAM, each bit of the database stored in the CAM array
110
must be represented by at least two bits, in order to encode the three required logical states (“0”, “1”, and “don't care”). Although a number of different technologies can be used to construct the CAM array
110
, modern CAM devices use storage elements based upon a static random access memory (SRAM), where data is stored in a flip-flop, or a dynamic random access memory (DRAM), where data is stored in the form of a charge on a capacitor.
FIG. 2
is an illustration of a CAM cell
200
based upon DRAM technology.
The cell
200
includes a transistor
202
and a capacitor
203
, which are coupled in series between a bit line
201
and a ground potential
206
as illustrated in
FIG. 2. A
select line
205
is coupled to the gate of the transistor
202
. Additionally, the cell
200
inherently includes parasitic capacitance, which is illustrated in
FIG. 2
as capacitor
204
, coupled between the bit line
201
and ground
206
. Data may be stored in the cell
200
by switching transistor
202
on (via line
205
) and forcing bit line
201
to either a high or a low state. This causes the capacitor
203
to charge or discharge until the potential at node
207
equals the potential of the bit line. The transistor
202
is then switched off (via line
205
) and the potential at node
207
is maintained by the charge stored in capacitor
203
.
In order to read data stored in the cell
200
, the bit line
201
is precharged to a high level. This ensures that the parasitic capacitance
204
is also charged. The transistor
202
is then switched on (via line
205
). If the capacitor
203
is storing a charge so that the potential at node
207
is high, there is no change of potential at node
207
and at the bit line
201
. The charge level of the capacitor
203
is also unchanged. However, if the capacitor
203
is storing a charge so that the potential at node
207
is low, charge will flow from the bit line
201
through the transistor
202
and into the capacitor
203
. This causes the potential at the bit line
201
to decrease and the potential at node
207
to increase. The charge level of the capacitor
203
also increases. The change in voltage in the bit line
201
and/or at node
207
can be sensed, in order to determine logical stated stored in the capacitor
202
.
The CAM cell illustrated in
FIG. 2
stores a single bit of data, and is therefore capable of encoding only two states. As previously discussed, ternary CAMs require cells which can encode three states. The
300
circuit illustrated in
FIG. 3
is similar to that the circuit
200
illustrated in
FIG. 2
, but includes two storage elements. This permits the cell
300
to store two bits, which can encode four states, three of which is sufficient to serve the storage requirements of a ternary CAM cell.
One problem associated with dynamic CAM cells
200
,
300
is that a read operation may be destructive. In cell
200
, for example, when the read operation is performed on a cell in which the capacitor
202
is storing a low level of charge, the flow of charge from the bit line
201
during the read operation alters the charge level of the capacitor
202
. Thus, in CAM cells
200
,
300
, a charge restoration operation is required after each read operation. The requirement for performing a charge restoration operation after each read limits the speed of a CAM device. The charge restoration circuit (not illustrated) also requires additional components and increases power consumption.
FIG. 4
is an illustration of another CAM cell
400
. In comparison to the previously described CAM cell
300
(FIG.
3
), CAM cell
400
includes two additional transistors
402
a,
402
b,
which are coupled in parallel with the data storage capacitors
203
a,
203
b,
respectively. The gate of transistor
402
a
is coupled to node
207
b
while the gate of transistor
402
b
is coupled to node
207
a.
These two transistors
402
a,
402
b
provide the circuit
400
a limited form of protection from destructive reads. More specifically, the CAM cell
400
can be read nondestructively only if the capacitors
203
a,
203
b
store opposite charges (i.e., “0”+“1” or “1”&p

Affiliated with

Also associated with

Rating

Tertiary CAM cell does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Tertiary CAM cell, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tertiary CAM cell will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3293202