Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-01-26
2002-11-05
Portka, Gary J (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S049130
Reexamination Certificate
active
06477615
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a content addressed memory (CAM), and more specifically to a detecting circuit and a detecting method of an idle word having no data to be retrieved in a CAM having valid cells.
BACKGROUND OF THE INVENTION
The content addressed memory (CAM) is a semiconductor memory in which by adding a data retrieving device to the semiconductor memory, whether or not data matching the inputted retrieval data exists in the memory is detected, in addition to the normal data read/write operation, and if there is matching data, the address of it is outputted, otherwise the absence of such data is outputted. The typical CAM comprises, as shown in
FIG. 1
, an address/data circuit (bus)
1
, an input-output/control circuit
2
, and a plurality of memory blocks
3
.
FIG. 2
is a diagram showing the memory block
3
of the conventional CAM. The memory block
3
includes an address decoder
10
, a data write driver
11
, a data read sense amplifier
12
, and a CAM cell array
13
, which are seen in the typical memory, and in addition, includes a data retrieve driver
11
, word match lines
14
, valid cells
15
, valid
16
, a word match circuit
17
, and an address encoder
18
. Since the data retrieve driver can also be used as the data write driver, it is denoted by the same symbol
11
in
FIG. 2
, and has a function of sending retrieval data to the bit line of the cell array when data is retrieved. The valid cells
15
are a memory cell existing for each word address. The valid cell
15
is a memory which holds “false” (bit “0”) if data is not written in its word address, and holds “true” (bit “1”) that is written if data is written.
To the word match lines
14
, the result of the comparison between the retrieval data and the data in the memory cell for each word address, which is made when data retrieval is performed, is outputted. The word match circuit
17
is connected to the CAM cell array
13
through the word match lines
14
. The word match circuit
17
is a circuit which determines and outputs the presence or absence of matched data upon receipt of the valid
16
, which is the output of the word match line
14
and the valid cells
15
. The address encoder
18
receives the output of the word match circuit
17
, assigns specified weight to it, and creates and outputs an address. The assigning of a specified weight means, for instance, increasing the priority of a low address.
Now, the operation of the CAM of
FIG. 2
will be described.
FIG. 3
is a diagram for explaining the data flow in the CAM. In
FIG. 3
, at the word address
0
to address
6
of the CAM cell array, the shown seven data are stored. In the valid cells for the word addresses
0
,
1
,
3
,
5
, and
6
, a bit “1” showing the presence of data to be retrieved is stored. Further, the valid cells for the word addresses
2
and
4
have stored therein a bit “0” showing the absence of data to be retrieved (data is invalid), in other words, showing that data is not written yet, or data has become invalid after written.
Now, suppose that retrieval data shown by a symbol
20
in
FIG. 3
is inputted by the data retrieve driver
11
(FIG.
2
). To the word match lines
14
, the results of the comparisons made between the retrieval data and the memory cells for the respective word addresses in the data retrieval are outputted. Upon receipt of the valid
16
which is the output of the word match line
14
and the valid cells
15
, the word match circuit
17
detects the presence or absence of matched data and provides an output. If there is a match between the retrieval data and the data in the cell, it outputs a bit “0.” Inversely, if there is no match between the retrieval data
20
and the data in the cell, it outputs a bit “1.” In the example of
FIG. 3
, data are matching at the word addresses
1
,
2
, and
6
. However, for the address
2
, since there is a bit “0” in the valid cell, the output of the word match circuit is “1.” Accordingly, only the word match outputs for the addresses
1
and
6
are “
0
,” and the remaining addresses are “1.”
The address encoder
18
receives the output of the word match circuit
17
, and outputs the smallest address. In the example of
FIG. 3
, it outputs the smaller address
1
of the two matching addresses, addresses
1
and
6
. Simultaneously, it outputs “true” as the match output.
SUMMARY OF THE INVENTION
There are the following problems with the conventional CAM described using
FIGS. 1
to
3
.
(1) It is not clear whether or not the CAM has an “empty address” (idle word) in which no data is written.
(2) It is not clear which address of the CAM is an “empty address.”
(3) To solve the problems (1) and (2), to know the presence or absence of an “empty address” (idle word), and if there is an “empty address” (idle word), to know that address, it is necessary to provide a new circuit outside the CAM.
The present invention was made to solve the above problems of the CAM. Its object is to enable the knowing of the presence or absence of an “empty address” in the CAM, and knowing of the particular address if there is an “empty address.”
It is an object of the present invention to enable the knowing of the presence or absence of an idle word and the word address of the idle word if it is present, without providing a new circuit outside the CAM.
It is an object of the present invention that, in the CAM having valid cells, the data in the valid cells and an address encoder are used to enable an idle word to be detected and outputted.
In accordance with the invention, a detection circuit of an idle word for a content addressed memory having valid cells is provided, which comprises means for supplying the output of a valid cell to an address encoder in response to an idle word detection signal.
In accordance with the invention, a content addressed memory (CAM) is provided, which comprises CAM cells, valid cells, word match lines, a word match circuit, an address encoder, a circuit for detecting an idle word by using the output of valid cells.
In accordance with the invention, a detection method of an idle word for a content addressed memory having valid cells is provided, which comprises a step of writing bit data representing the presence or absence of valid data to a valid cell, and a step of outputting the bit data of a valid cell to an address encoder in response to an idle word detection signal.
REFERENCES:
patent: 5440715 (1995-08-01), Wyland
patent: 5813040 (1998-09-01), Rathke
patent: 5978245 (1999-11-01), Hata et al.
patent: 5999434 (1999-12-01), Yoneda et al.
patent: 6070223 (2000-05-01), Yoshizawa et al.
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6219748 (2001-04-01), Srinivasan et al.
Odagiri et al., “A New CAM for 622 Mbps ATM Cell Processing”, IEEE 1996 Custom Integrated Circuits Conference.
Portka Gary J
Walsh Robert A.
LandOfFree
Detecting circuit and detecting method of idle word for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detecting circuit and detecting method of idle word for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting circuit and detecting method of idle word for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2993441