Static information storage and retrieval – Read/write circuit – Precharge
Reexamination Certificate
2002-11-12
2003-06-17
Lam, David (Department: 2818)
Static information storage and retrieval
Read/write circuit
Precharge
C365S049130, C365S230030
Reexamination Certificate
active
06580652
ABSTRACT:
The present invention relates generally to the field of content addressable memories (CAMs) and particularly to a circuit and method for providing a highest priority binary memory match line address resulting from a search operation.
BACKGROUND OF THE INVENTION
A content addressable memory (CAM) is a binary or ternary memory storage device in which data is searched, read and written based on the content of the stored data, rather than the location where the data is stored. Each CAM memory cell is created by the intersection of a row and an associated match line and a column and associated search line. A CAM typically compares externally-provided search data with stored data in each row of the CAM array and provides match results on multiple match lines. The match results are subsequently provided to a priority encoder which converts the match results into a binary address representing the highest priority matching address. Each match line provides a “hit” or “match” indication if the stored data word matches the search word and provides a “miss” or “mis-match” indication if the stored data does not match the search word. Each row and match line combination has a unique N-bit address within the CAM. Accordingly, for any search cycle there may be up to 2
N
match lines activated. Using the N-bit address generated by the priority encoder, the CAM may provide the address as an output for applications such as IP routing table lookup, compression and decompression.
Usually within the context of CAM array, the highest priority matching word is located at the lowest physical address in the CAM array and, accordingly, the lowest priority matching word is located at the highest physical address in the CAM array.
It may be well appreciated that a complex array of standard static boolean logic gates is required to achieve this function. This problem is further complicated by a requirement to deliver address information at a full data rate of the search-and-compare function of the CAM. The most difficult logic operation that a priority encoder must perform is to detect the highest priority match line and to disable any and all lower priority match lines at a high speed. Once the single highest priority match line output has been resolved, a programmable logic array (PLA) or read-only-memory memory (ROM) is used to convert the highest priority match line output into a binary address. The function of detecting the highest priority match line and disabling all lower priority match lines is conventionally implemented using an array of standard boolean logic gates. Examples of such approaches are proposed by Yamagata et al. in IEEE publication “A 288-kb Fully Parallel Content Addressable Memory Using a Stacked Capacitor Cell Structure”, IEEE Journal of Solid State Circuits Vol. 27, No. 12, December 1992 pp. 1927-1933 and by Shultz et al. in IEEE publication “Fully Parallel Integrated CAM/RAM Using Preclassification to Enable Large Capacities,” IEEE Journal of Solid State Circuits Vol. 31, No. 5, May 1996. However, the resulting static logic gate implementations are relatively complex and consume large areas of semiconductor as well as introduce substantial propagation delays. Accordingly, there is a need for an efficient high-speed priority encoder for resolving a highest priority match which exhibits reduced circuit complexity and area consumed.
SUMMARY OF THE INVENTION
In accordance with an aspect of the present invention there is provided a circuit for selecting a highest priority signal from a plurality of input signals. The circuit comprises the following components. A plurality of serially coupled input blocks, each of which are coupled to a corresponding one of a plurality of input lines for receiving respective ones of the input signals and providing corresponding output signals. A pre-charging device coupled between a first supply voltage terminal and a first one of the serially coupled input blocks. The pre-charging device couples the supply voltage to the first one of the serially coupled input blocks in response to a clock pulse signal transition. An activation device coupled between a second supply voltage terminal and a last one of the serially coupled input blocks. The activation device couples the second supply voltage to the last one of the serially coupled input blocks in response to an activation signal transition. The second supply voltage is propagated through the plurality of input blocks to an input block having an input signal voltage that is different from a predefined voltage state. The second supply voltage terminal is subsequently provided as the only output from said plurality of input blocks representing a highest priority match signal.
REFERENCES:
patent: 5274596 (1993-12-01), Watanabe
Yamagata, et al., “A 288-kb Fully Parallel Content Addressable Memory Using a Stacked Capacitor Cell Sructure”, IEEE Journal of Solid State Circuits, vol. 27, No. 12, Dec. 1992, pp. 1927-1933.
Shultz et al., “Fully Parallel Integrated CAM/RAM Using Preclassification to Enable Large Capacities”, IEEE Journal of Solid State Circuits, vol. 31, No. 5, May 1996.
Foss Richard C.
Roth Alan
Dowell & Dowell PC
Lam David
LandOfFree
Priority encoder circuit and method for content addressable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Priority encoder circuit and method for content addressable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority encoder circuit and method for content addressable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099172