US6252789B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Inter-row configurability of content addressable memory
Assignee: Avago Technologies International Sales Pte Ltd
•
Filing: 2000-06-14
•
Granted: 2001-06-26
•
Expires: 2020-06-14
Abstract
Abstract A CAM system for storing a data word chain having a sequence of one or more data words stored in one or more rows of CAM cells. For one embodiment, the CAM system includes rows of CAM cells each for storing a data word in a data word chain, match lines, and width expansion logic circuits each having a plurality of control inputs for receiving a plurality of control signals. The width expansion logic circuits are interconnected and determine when and how match results are communicated to a priority encoder and to each other. The control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word, a continuing data word, and a last data word of the data word chain are provided for comparison with the rows of CAM cells. The continuing data word is a data word between the first and last data word in the data word chain. For one embodiment, the control signals are generated by an instruction decoder in response to decoding separate instructions for comparing the first data word, a continuing data word, and the last data word of a data word chain. Each row of CAM cells may also include classification information or control bits that indicate the data word chain or the place of a data word in the data word chain. For one embodiment, the CAM system can store and operate on data word chains of different lengths.
Inventors
- 👤 Jose Pio Pereira
- 👤 Varadarajan Srinivasan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 07:21
CPC Classifications
G; G11; G11C; G11C15/00; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339
Claims Analysis
Total Claims: 57
Claim 1
Independent Claim
212 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs for receiving a plurality of control signals, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits, and wherein the control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word, a continuing data word, and a last data word of the data word chain are provided for comparison with the data word of each of the rows of CAM cells, wherein the continuing data word is a data word between the first and last data word in the data word chain.
Claim 2
Dependent Claim
212 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs for receiving a plurality of control signals, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits, and wherein the control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word, a continuing data word, and a last data word of the data word chain are provided for comparison with the data word of each of the rows of CAM cells, wherein the continuing data word is a data word between the first and last data word in the data word chain.
Claim 3
Dependent Claim
65 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise: a first plurality of CAM cells for storing the data word in the data word chain; and a second plurality of CAM cells for storing classification information about each data word of the first plurality of CAM cells, wherein the classification information uniquely identifies each data word chain.
Claim 4
Dependent Claim
70 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise: a first plurality of CAM cells for storing the data word in the data word chain; and a second plurality of CAM cells for storing classification information about each data word of the first plurality of CAM cells, wherein the information classification identifies the number of data words in each data word chain.
Claim 5
Dependent Claim
79 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise: a first plurality of CAM cells for storing the data word in the data word chain; and a second plurality of CAM cells for storing a plurality of control bits that indicate whether the data word of the first plurality of CAM cells is the first data word, the continuing data word or the last data word in the data word chain.
Claim 6
Dependent Claim
63 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise: a plurality of CAM cells for storing the data word in the data word chain; and another CAM cell for storing a control bit that indicates whether the data word of the plurality of CAM cells is the first data word in the data word chain.
Claim 7
Dependent Claim
63 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise: a plurality of CAM cells for storing the data word in the data word chain; and another CAM cell for storing a control bit that indicates whether the data word of the plurality of CAM cells is the last data word in the data word chain.
Claim 8
Dependent Claim
83 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise a plurality of CAM cells for storing the data word in the data word chain, and wherein the CAM system further comprises a plurality of memory elements for storing a plurality of control bits that indicate whether the data word of the first plurality of CAM cells is the first data word, the continuing data word or the last data word in the data word chain.
Claim 9
Dependent Claim
77 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise a plurality of CAM cells for storing the data word in the data word chain, and wherein the CAM system further comprises a memory element coupled to the width expansion logic circuit and for storing a control bit that indicates whether the data word of the plurality of CAM cells is the first data word in the data word chain.
Claim 10
Dependent Claim
77 words
The CAM system of claim 1 , wherein the plurality of rows of CAM cells each comprise a plurality of CAM cells for storing the data word in the data word chain, and wherein the CAM system further comprises a memory element coupled to the width expansion logic circuit and for storing a control bit that indicates whether the data word of the plurality of CAM cells is the last data word in the data word chain.
Claim 11
Dependent Claim
24 words
The CAM system of claim 1 , further comprising an instruction decoder for determining the control signals in response to decoding a compare instruction.
Claim 12
Dependent Claim
84 words
The CAM system of claim 1 , wherein each width expansion logic circuit comprises: a match carry generator circuit coupled to the match line input, at least one of the control inputs, and the match carry output, the match carry generator circuit for generating a match carry output signal; and a match result generator circuit coupled to the match line input, at least one of the control inputs, and the match line output, the match result generator circuit for generating a match output signal.
Claim 13
Dependent Claim
31 words
The CAM system of claim 11 , wherein the match carry output signal is indicative of when a corresponding row of CAM cells stores a data word that matches comparand data.
Claim 14
Dependent Claim
49 words
The CAM system of claim 11 , wherein the match carry output signal is indicative of when (i) a corresponding row of CAM cells stores a data word that matches first comparand data, and (ii) another row of CAM cells stores a data word that matches second comparand data.
Claim 15
Dependent Claim
30 words
The CAM system of claim 11 , wherein the match output signal is indicative of when a corresponding row of CAM cells stores a data word that matches comparand data.
Claim 16
Dependent Claim
49 words
The CAM system of claim 11 , wherein the match output signal is indicative of when (i) a corresponding row of CAM cells stores the last data word of a data word chain, and (ii) another row of CAM cells stores the first word of the data word chain.
Claim 17
Dependent Claim
69 words
The CAM system of claim 11 , wherein the match output signal is indicative of when (i) a corresponding row of CAM cells stores the last data word of a data word chain, (ii) one or more rows of CAM cells stores one or more continuing data words of the data word chain, and (iii) another row of CAM cells stores the first word of the data word chain.
Claim 18
Dependent Claim
40 words
The CAM system of claim 11 , wherein the match output signal is indicative of a mismatch between a first data word stored in a corresponding row of CAM cells and comparand data regardless of whether there is a match.
Claim 19
Dependent Claim
150 words
The CAM system of claim 11 , wherein the match carry generator circuit comprises: a first logic circuit having a first input coupled to the match line input and a second input coupled to receive a first control signal from one of the control inputs, the first logic circuit configured to determine when a corresponding row of CAM cells stores the first data word of a data word chain; and a second logic circuit having a first input coupled to the match line, a second input coupled to the match carry input, and a third input coupled to receive a second control signal from another one of the control inputs, the second logic circuit configured to determine when the corresponding row of CAM cells stores a continuing data word of a data word chain and another row of CAM cells stores the first data word of the data word chain.
Claim 20
Dependent Claim
166 words
The CAM system of claim 11 , wherein the match result generator circuit comprises: a first logic circuit having a first input coupled to the match line input and a second input coupled to receive a first control signal from one of the control inputs, the first logic circuit configured to determine when a corresponding row of CAM cells stores a data word that matches a data word chain having the same number of bits as in the corresponding row of CAM cells; and a second logic circuit having a first input coupled to the match line, a second input coupled to the match carry input, and a third input coupled to receive a second control signal from another one of the control inputs, the second logic circuit configured to determine when the corresponding row of CAM cells stores the last data word of a data word chain and another row of CAM cells stores the first or continuing data word of the data word chain.
Claim 21
Dependent Claim
24 words
The CAM system of claim 1 , further comprising a priority encoder coupled to the match line outputs of the width expansion logic circuits.
Claim 22
Dependent Claim
19 words
The CAM system of claim 20 , further comprising an address translation logic circuit coupled to the priority encoder.
Claim 23
Dependent Claim
15 words
The CAM system of claim 21 , wherein the address translation circuit comprises a multiplexer.
Claim 24
Dependent Claim
17 words
The CAM system of claim 21 , wherein the address translation circuit comprises an arithmetic logic unit.
Claim 25
Dependent Claim
16 words
The CAM system of claim 23 , wherein the arithmetic logic unit comprises a subtractor circuit.
Claim 26
Dependent Claim
187 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs for receiving a plurality of control signals, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits, and wherein the control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word and a last data word of the data word chain are provided for comparison with the data word of each of the rows of CAM cells.
Claim 27
Dependent Claim
187 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs for receiving a plurality of control signals, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits, and wherein the control signals are for determining the operation of the width expansion logic circuits and for indicating when a first data word and a last data word of the data word chain are provided for comparison with the data word of each of the rows of CAM cells.
Claim 28
Dependent Claim
218 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each including: a first plurality of CAM cells for storing a data word in the data word chain; a second plurality of CAM cells for storing a plurality of control bits that indicate whether the data word of the first plurality of CAM cells is the first data word, a continuing data word or the last data word in the data word chain, wherein the continuing data word is a data word between the first and last data word in the data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs coupled to receive the plurality of control bits from the second plurality of CAM cells, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits.
Claim 29
Dependent Claim
218 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each including: a first plurality of CAM cells for storing a data word in the data word chain; a second plurality of CAM cells for storing a plurality of control bits that indicate whether the data word of the first plurality of CAM cells is the first data word, a continuing data word or the last data word in the data word chain, wherein the continuing data word is a data word between the first and last data word in the data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs coupled to receive the plurality of control bits from the second plurality of CAM cells, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits.
Claim 30
Dependent Claim
24 words
The CAM system of claim 26 , further comprising a priority encoder coupled to the match line outputs of the width expansion logic circuits.
Claim 31
Dependent Claim
19 words
The CAM system of claim 27 , further comprising an address translation logic circuit coupled to the priority encoder.
Claim 32
Dependent Claim
15 words
The CAM system of claim 28 , wherein the address translation circuit comprises a multiplexer.
Claim 33
Dependent Claim
17 words
The CAM system of claim 28 , wherein the address translation circuit comprises an arithmetic logic unit.
Claim 34
Dependent Claim
16 words
The CAM system of claim 30 , wherein the arithmetic logic unit comprises a subtractor circuit.
Claim 35
Dependent Claim
211 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in the data word chain; a plurality of memory element groups each for storing a plurality of control bits that indicate whether the data word of a corresponding row of CAM cells is the first data word, a continuing data word or the last data word in the data word chain, wherein the continuing data word is a data word between the first and last data word in the data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs coupled to receive the plurality of control bits from a corresponding memory element group, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits.
Claim 36
Dependent Claim
211 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in the data word chain; a plurality of memory element groups each for storing a plurality of control bits that indicate whether the data word of a corresponding row of CAM cells is the first data word, a continuing data word or the last data word in the data word chain, wherein the continuing data word is a data word between the first and last data word in the data word chain; a plurality of match lines each coupled to a corresponding row of CAM cells; and a plurality of width expansion logic circuits each having a match line input coupled to a match line of a corresponding row of CAM cells, a match line output, a match carry output, a match carry input, and a plurality of control inputs coupled to receive the plurality of control bits from a corresponding memory element group, wherein the match carry output of one of the width expansion logic circuits is coupled to the match carry input of another one of the width expansion logic circuits.
Claim 37
Dependent Claim
24 words
The CAM system of claim 32 , further comprising a priority encoder coupled to the match line outputs of the width expansion logic circuits.
Claim 38
Dependent Claim
19 words
The CAM system of claim 33 , further comprising an address translation logic circuit coupled to the priority encoder.
Claim 39
Dependent Claim
15 words
The CAM system of claim 34 , wherein the address translation circuit comprises a multiplexer.
Claim 40
Dependent Claim
17 words
The CAM system of claim 34 , wherein the address translation circuit comprises an arithmetic logic unit.
Claim 41
Dependent Claim
16 words
The CAM system of claim 36 , wherein the arithmetic logic unit comprises a subtractor circuit.
Claim 42
Dependent Claim
100 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; and means for determining when the data word of a one of the rows of CAM cells is the first data word, a continuing data word, or the last data word of the data word chain, wherein a continuing data word is a data word between the first and last data words in the data word chain.
Claim 43
Dependent Claim
100 words
A content addressable memory (CAM) system for storing a data word chain having a sequence of one or more data words, the CAM system comprising: a plurality of rows of CAM cells each for storing a data word in a data word chain; and means for determining when the data word of a one of the rows of CAM cells is the first data word, a continuing data word, or the last data word of the data word chain, wherein a continuing data word is a data word between the first and last data words in the data word chain.
Claim 44
Dependent Claim
38 words
The CAM system of claim 38 , further comprising means for determining when all of the data words in a data word chain match all corresponding data word chains stored in the plurality of rows of CAM cells.
Claim 45
Dependent Claim
38 words
The CAM system of claim 39 , further comprising priority encoding means for determining the highest priority address of the plurality of rows of CAM cells that stores all of the data words of the data word chain.
Claim 46
Dependent Claim
19 words
The CAM system of claim 40 , further comprising means for translating the highest priority address into another address.
Claim 47
Dependent Claim
95 words
A content addressable memory (CAM) comprising: a first plurality of rows CAM cells each for storing a data word in a first data word chain, a second plurality of rows of CAM cells each for storing a data word in a second data word chain, wherein the number of data words in the second data word chain is different than the number of data words in the first data word chain; and means for distinguishing a match of comparand data with the first data word chain from a match with the second data word chain.
Claim 48
Dependent Claim
95 words
A content addressable memory (CAM) comprising: a first plurality of rows CAM cells each for storing a data word in a first data word chain, a second plurality of rows of CAM cells each for storing a data word in a second data word chain, wherein the number of data words in the second data word chain is different than the number of data words in the first data word chain; and means for distinguishing a match of comparand data with the first data word chain from a match with the second data word chain.
Claim 49
Independent Claim
68 words
A method comprising: generating first match results on a plurality of match lines in response to a comparison of a first data word of a data word chain with data words stored in each of a plurality of rows of CAM cells; providing the first match results to width expansion logic circuits; outputting a mismatch state from the width expansion logic circuits regardless of the first match results.
Claim 50
Independent Claim
68 words
A method comprising: generating first match results on a plurality of match lines in response to a comparison of a first data word of a data word chain with data words stored in each of a plurality of rows of CAM cells; providing the first match results to width expansion logic circuits; outputting a mismatch state from the width expansion logic circuits regardless of the first match results.
Claim 51
Dependent Claim
76 words
The method of claim 43 , further comprising: generating second match results on the plurality of match lines in response to a comparison of a second data word of the data word chain with data words stored in each of the plurality of rows of CAM cells; providing the second match results to the width expansion logic circuits; and logically combining the first match results and the second match results in the width expansion logic circuits.
Claim 52
Dependent Claim
21 words
The method of claim 44 , wherein the second data word is the last data word of the data word chain.
Claim 53
Dependent Claim
42 words
The method of claim 44 , wherein the second data word is a continuing data word of the data word chain, wherein the continuing data word is between the first data word and a last data word of the data word chain.
Claim 54
Dependent Claim
110 words
The method of claim 44 , further comprising: outputting a mismatch state from the width expansion logic circuits regardless of the first and second match results; generating third match results on the plurality of match lines in response to a third comparison of a third data word of the comparand data line with data words stored in each of the plurality of rows of content addressable memory (CAM) cells; providing the third match results to the width expansion logic circuits; and logically combining the first match results, second match results, and third match results in the width expansion logic circuits to generate a match result for the data word chain.
Claim 55
Independent Claim
88 words
A method comprising: comparing, in response to a first instruction, a first data word of a data word chain with data words stored in each of a plurality of rows of CAM cells, wherein the data word chain comprises a sequence of one or more data words; and comparing, in response to a second instruction, a last data word of the data word chain with data words stored in each of the plurality of rows of CAM cells, wherein the first and second instructions are uniquely coded instructions.
Claim 56
Independent Claim
88 words
A method comprising: comparing, in response to a first instruction, a first data word of a data word chain with data words stored in each of a plurality of rows of CAM cells, wherein the data word chain comprises a sequence of one or more data words; and comparing, in response to a second instruction, a last data word of the data word chain with data words stored in each of the plurality of rows of CAM cells, wherein the first and second instructions are uniquely coded instructions.
Claim 57
Dependent Claim
70 words
The method of claim 48 , further comprising comparing, in response to a third instruction, a continuing data word of the data word chain with data words stored in each of the plurality of rows of CAM cells, wherein the first, second and third instructions are uniquely coded instructions, and wherein the continuing data word is data word between the first and last data word in the data word chain.
References Cited (Backward Citations)
US3257646A
Cited
US3353159A
Cited
US4575818A
Cited
US4622653A
Cited
US5072422A
Cited
US5053991A
Cited
US5440715A
Cited
US5483480A
Cited
US5394353A
Cited
US5818786A
Cited
US5787458A
Cited
US5943252A
Cited
US5930790A
Cited
US6081441A
Cited
US6147890A
Cited
US6081442A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-06-25 | 2004-12-25 | 2005-06-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-06-25 | 2008-12-25 | 2009-06-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-06-25 | 2012-12-25 | 2013-06-26 | $7700.00 | Window Closed / Lapsed |