Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2002-07-02
2004-03-16
Lebentritt, Michael S. (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230010, C365S230060, C365S230090
Reexamination Certificate
active
06707694
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to Content Addressable Memories (CAM) and circuits for detecting multiple matches therein.
BACKGROUND OF THE INVENTION
A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data being stored within a given memory location) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory search on a RAM, the user supplies the address and gets back the data stored in that address (location).
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address, or the data can be written into a first empty memory location. Once information is stored in a memory location, it is found doing a memory search by comparing every bit in any memory location with every bit of data in a comparand register circuit. When the content stored in the CAM memory location does not match the data placed in the comparand register, the CAM device returns a no match indication. When the content stored in the CAM memory location matches the data placed in the comparand register, the CAM device returns a match indication. In addition, the CAM returns the identification of the address location in which the matching data is stored. Thus, with a CAM, the user supplies the data and gets back an indication of an address where a matching data is stored in the memory.
Locally, CAMs perform an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number, or all of the memory locations may be simultaneously searched for a match with incoming data. In certain cases, data in more than a single location in the memory matches the input data, and such condition of multiple simultaneous matches must be detected and reported. However, circuitry for detecting multiple matches in a CAM memory generally is large and complex, and grows exponentially with the number of data words in the memory. Also, the switching time is impeded because of the parasitic capacitance associated with the complex logic. Thus, there is a need for a multiple match detector having increased switching speed, yet reduced circuit complexity.
BRIEF SUMMARY OF THE INVENTION
In one aspect, the invention provides a circuit for detecting multiple matches in a content addressable memory including a plurality of input pins where is are connected to a match line of the content addressable memory; a plurality of transistors connected to the input pins and logically arranged to detect a multiple match condition; a current source transistor for controlling the current through the plurality of transistors; and a current sensing detector connected to the plurality of transistors for outputting a signal indicating that a multiple match condition has been detected.
In an additional aspect, a portion of the plurality of transistors are connected in parallel to achieve a logical ‘OR’ condition; and a portion of the plurality of transistors are connected in series to achieve a logical ‘AND’ condition. In yet another aspect, a plurality of OR gates are connected to the input line of a multiple match signal. Additional aspects of the present invention include a method for operating the above components.
REFERENCES:
patent: 5446686 (1995-08-01), Bosnyak et al.
patent: 6175513 (2001-01-01), Khanna
patent: 6307798 (2001-10-01), Ahmed et al.
patent: 6317350 (2001-11-01), Pereira et al.
patent: 6370613 (2002-04-01), Diede et al.
patent: 6392910 (2002-05-01), Podaima et al.
Application Brief AB-N6, Music Semiconductors, What Is A Cam (Content-Addressable Memory)?, Sep. 30, 1998, pp. 1-4.
Application Brief AB-N11, Music Semiconductors, Advantages of CAM in Asic-Based Network Address Processing, Sep. 30, 1998, pp. 1-4.
Dickstein , Shapiro, Morin & Oshinsky, LLP
Le Toan
Lebentritt Michael S.
Micro)n Technology, Inc.
LandOfFree
Multi-match detection circuit for use with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-match detection circuit for use with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-match detection circuit for use with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3197751