US5852569A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Content addressable memory multiple match detection circuit
Assignee: Avago Technologies International Sales Pte Ltd
•
Filing: 1997-05-20
•
Granted: 1998-12-22
•
Expires: 2017-05-20
Abstract
Abstract A circuit and a method for detecting the presence of multiple active match lines in a content addressable memory is disclosed. The circuit includes at least one bus group for expressing a unary-encoded address portion of an active match line and, for each match line, an encoding circuit capable of activating a single member of each bus group according to the address of that match line when that match line is active. The multiple match detection circuit advantageously uses the property that each match line has a unique address, and therefore if there is more than one active match line, at least one bus group will have at least two active members. The multiple match detection circuit further comprises, for each bus group, an bus group detection-OR circuit for computing the logical bus group detection-OR of the members of that bus group. The multiple match detection circuit further comprises an OR circuit for computing the logical OR of the outputs of the bus group detection-OR circuits, for providing a multiple match flag which is active when two or more match lines are active and which is inactive otherwise.
Inventors
- 👤 Varadarajan Srinivasan
- 👤 Sandeep Khanna
- 👤 Sanjay V. Gala
- 👤 Ketan K. Mehta
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 03:03
CPC Classifications
G; G11; G11C; G11C15/00; G11C15/04
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
214 words
A multiple match detection circuit for use with a content addressable memory having a plurality of match lines, said multiple match detection circuit for detecting whether two or more match lines are simultaneously active, comprising: at least one bus group having a plurality of members; a plurality of encoding circuits, each encoding circuit for coupling to a one of the match lines, each encoding circuit being coupled to each of said bus groups for activating a single member of said bus group responsive to the activation of its associated match line; at least one bus group detection circuit, each bus group detection circuit corresponding to a one of said bus groups and coupled thereto, said bus group detection circuit having an output which is active when more than one of said members of said one bus group is active; a logical OR circuit coupled to said bus group detection circuits, said logical OR circuit having an output which is active when at least one of said outputs of said bus group detection circuits is active; wherein each of said encoding circuits activates a unique set of members responsive to the activation of its associated match line; whereby the output of said logical OR circuit is active when more than one match line is active.
Claim 2
Dependent Claim
214 words
A multiple match detection circuit for use with a content addressable memory having a plurality of match lines, said multiple match detection circuit for detecting whether two or more match lines are simultaneously active, comprising: at least one bus group having a plurality of members; a plurality of encoding circuits, each encoding circuit for coupling to a one of the match lines, each encoding circuit being coupled to each of said bus groups for activating a single member of said bus group responsive to the activation of its associated match line; at least one bus group detection circuit, each bus group detection circuit corresponding to a one of said bus groups and coupled thereto, said bus group detection circuit having an output which is active when more than one of said members of said one bus group is active; a logical OR circuit coupled to said bus group detection circuits, said logical OR circuit having an output which is active when at least one of said outputs of said bus group detection circuits is active; wherein each of said encoding circuits activates a unique set of members responsive to the activation of its associated match line; whereby the output of said logical OR circuit is active when more than one match line is active.
Claim 3
Dependent Claim
56 words
The multiple match detection circuit of claim 1, said match lines each having an address, wherein each bus group corresponds to a unique set of m bits of said match line address having 2 m possible values, and wherein said bus group comprises 2 m members capable of unary-encoding each of said 2 m possible values.
Claim 4
Dependent Claim
92 words
The multiple match detection circuit of claim 2, each of said encoding circuits comprising: an input lead for coupling to the match line associated with said encoding circuit; a plurality of activation circuits, one activation circuit for each bus group, for activating a single member of each bus group according to the address of the match line associated with said encoding circuit; whereby the single member of each bus group activated by said encoding circuit corresponds to a unary-encoded form of said m bits of the address of the activated match line.
Claim 5
Dependent Claim
48 words
The multiple match detection circuit of claim 3, each of said activation circuits comprising: a transistor having a gate coupled to the match line, a first current node coupled to said single member of said bus group, and a second current node coupled to a constant voltage source.
Claim 6
Dependent Claim
108 words
The multiple match detection circuit of claim 4, said address having N bits, said multiple match detection circuit comprising: N/m bus groups, each bus group having 2 m members; 2 N encoding circuits, each encoding circuit comprising N/m activation circuits; N/m bus group detection circuits, each bus group detection circuit corresponding to a one of said N/m bus groups, each bus group detection circuit comprising 2 m inputs and an output, each input being coupled to a one of said members of said bus group; and a logical OR circuit having N/m inputs each coupled to the output of a one of said N/m bus group detection circuits.
Claim 7
Dependent Claim
14 words
The multiple match detection circuit of claim 5, wherein m is equal to 1.
Claim 8
Dependent Claim
13 words
The multiple match detection circuit of claim 5, wherein is equal to 2.
Claim 9
Dependent Claim
14 words
The multiple match detection circuit of claim 7, wherein N is equal to 10.
Claim 10
Independent Claim
106 words
A method of detecting whether two or more match lines are simultaneously active in a content addressable memory, each of the match lines having a unique N-bit address, comprising the steps of: encoding the N-bit address of a first active match line into a first set of N/m unary-encoded address portions; encoding the N-bit address of a second active match line into a second set of N/m unary-encoded address portions; mapping said first and second sets into a common set of N/m unary-encoded address portions; and activating a multiple match flag if at least one of said unary-encoded address portions contains two or more active members.
Claim 11
Independent Claim
106 words
A method of detecting whether two or more match lines are simultaneously active in a content addressable memory, each of the match lines having a unique N-bit address, comprising the steps of: encoding the N-bit address of a first active match line into a first set of N/m unary-encoded address portions; encoding the N-bit address of a second active match line into a second set of N/m unary-encoded address portions; mapping said first and second sets into a common set of N/m unary-encoded address portions; and activating a multiple match flag if at least one of said unary-encoded address portions contains two or more active members.
Claim 12
Dependent Claim
23 words
The method of claim 9, wherein each of said N/m unary-encoded address portions are expressed as logic levels at 2 m electrical nodes.
Claim 13
Dependent Claim
34 words
The method of claim 10, wherein said step of mapping comprises the step of determining the logical OR of the active logic levels corresponding to said first and second sets of unary-encoded address portions.
Claim 14
Dependent Claim
28 words
The method of claim 11, wherein m is equal to 1 and wherein there are N unary-encoded address portions each expressed as logic levels at 2 electrical nodes.
Claim 15
Dependent Claim
33 words
The method of claim 11, wherein m is equal to 2 and N is equal to 10, wherein there are 5 unary-encoded address portions each expressed as logic levels at 4 electrical nodes.
Claim 16
Dependent Claim
57 words
A circuit, comprising: means for coupling to a plurality of sequentially-addressed input lines; means for encoding the address of each active input line into a plurality of unary-encoded address portions, each unary-encoded address portion comprising members; means for activating a match flag if at least one of said unary-encoded address portions contains two or more active members.
Claim 17
Dependent Claim
57 words
A circuit, comprising: means for coupling to a plurality of sequentially-addressed input lines; means for encoding the address of each active input line into a plurality of unary-encoded address portions, each unary-encoded address portion comprising members; means for activating a match flag if at least one of said unary-encoded address portions contains two or more active members.
Claim 18
Dependent Claim
118 words
The circuit of claim 14, said unary-encoded address portions being contained on bus groups, said means for encoding being coupled to said means for activating and comprising: a first node for coupling to said active input line; a plurality of switch transistors, each of said switch transistor corresponding to a one of said bus groups and having a control node coupled to said first node, a source coupled to a constant voltage source, and a drain coupled to a one of said members of said one bus group; wherein said one of said members is selected to correspond to the unary-encoded address portion corresponding to the address of the input line to which said first node is coupled.
Claim 19
Dependent Claim
58 words
The circuit of claim 15, said members of said bus groups being coupled through a pullup means to a high logic level, said constant voltage source being at a low logic level, said single member of said bus group being pulled low and the other members of said bus group remaining high for indicating a unary-encoded address portion.
Claim 20
Dependent Claim
56 words
The circuit of claim 16, wherein said means for activating comprises: means for detecting for each bus group whether that bus group contains at least two active members and for activating a bus group detect signal responsive thereto; means for determining the logical OR of said bus group detect signals for producing said multiple match flag.
References Cited (Backward Citations)
US4559618A
Cited
US4899307A
Cited
US4785428A
Cited
US5383146A
Cited
US5406508A
Cited
US5454094A
Cited
US5422838A
Cited
US5446686A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-21 | 2002-06-22 | 2002-12-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-21 | 2006-06-22 | 2006-12-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-21 | 2010-06-22 | 2010-12-22 | $7700.00 | Window Closed / Lapsed |