US5815737A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Approach for identifying a subset of asynchronous transfer mode (ATM) VPI/VCI values in the complete VPI/VCI range
Assignee: Microsemi Storage Solutions Ltd
•
Filing: 1995-06-05
•
Granted: 1998-09-29
•
Expires: 2015-06-05
Abstract
Abstract A method of searching a table stored in a memory for a record identifying a stored data word corresponding to a binary input data word, wherein the table is comprised of a plurality of records containing a select value field, a left search table address field, a right search table address field, and left and right search table address leaf fields, comprised of (a) indicating a particular single bit of the binary input data word based on a value stored in a select value field, (b) reading either the left or right search table address fields of the record containing the value stored in the first select value field, depending on the binary value of the particular single bit of the input data word indicated, (c) in the event a leaf field corresponding to the read left or right search table address stores a first binary value, repeating steps (a) and (b) using a record identified by the read left or right search table address, (d) in the event a left field corresponding to the read left or right search table address stores a second binary values, terminating the search and use the left or right search table address as an address for the data word stored in a second table.
Inventors
- 👤 Kenneth M. Buckland
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:58
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; H04L; H04L45/00; H04L45/74; H04L45/742; H04L49/00; H04L49/30; H04L49/3009; H04L49/3081; H04L49/309; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
201 words
A searching apparatus comprising: (a) a memory storing a search table, the search table comprising records, each record comprising a select word, a left leaf field, a left address field, a right leaf field and a right address field, (b) means for receiving an input word to be searched, (c) means for selecting one bit of the input word based on a value in a select word of a first record, (d) means for reading a left or right address field in said record, based on a binary value of said one bit, (e) means for reading a left or right leaf field in said record based on said binary value of said one bit, (f) means for selecting another record based on data stored in said left or right address field in the event of one particular binary value being stored in a corresponding left or right leaf field, (g) means for providing the data stored in said left or right address field at an output port in the event of another particular binary value being stored in said corresponding left or right leaf field, as an address to another table for identifying a record corresponding to the input word.
Claim 2
Dependent Claim
201 words
A searching apparatus comprising: (a) a memory storing a search table, the search table comprising records, each record comprising a select word, a left leaf field, a left address field, a right leaf field and a right address field, (b) means for receiving an input word to be searched, (c) means for selecting one bit of the input word based on a value in a select word of a first record, (d) means for reading a left or right address field in said record, based on a binary value of said one bit, (e) means for reading a left or right leaf field in said record based on said binary value of said one bit, (f) means for selecting another record based on data stored in said left or right address field in the event of one particular binary value being stored in a corresponding left or right leaf field, (g) means for providing the data stored in said left or right address field at an output port in the event of another particular binary value being stored in said corresponding left or right leaf field, as an address to another table for identifying a record corresponding to the input word.
Claim 3
Dependent Claim
51 words
A searching apparatus as defined in claim 1 in which the selecting means is a multiplexer for receiving all of the bits of the input word, for receiving the value of the select word and outputting a single bit of the input word determined by the value of the select word.
Claim 4
Dependent Claim
96 words
A searching apparatus as defined in claim 2 in which the means for reading a left or right address field in said record is a multiplexer for receiving a left leaf and left address of said record at one set of inputs and a right leaf and right address of said record at another set of inputs, for receiving the single bit output from the multiplexer as a select control, and for outputting either the left leaf and left address or said right leaf and right address depending on the binary value of the select bit.
Claim 5
Dependent Claim
26 words
A searching apparatus as defined in claim 3 including means for addressing a subsequent record of the search table using said output left or right address.
Claim 6
Dependent Claim
32 words
A searching apparatus as defined in claim 4 in which the address of said subsequent record addressed by said output left or right address is the value stored in the select field.
Claim 7
Dependent Claim
20 words
A searching apparatus as defined in claim 5 in which the multiplexers are implemented in a software controlled micro processor.
Claim 8
Dependent Claim
56 words
A searching apparatus as defined in claim 1 in which the means for receiving receives a cell of an asynchronous transfer mode signal comprising a header portion and a payload portion, the header portion comprising a virtual path identifier/vertical channel identifier (VPI/VCT) and means for providing the VPI/VCI to the receiving means as the input word.
Claim 9
Independent Claim
210 words
A method of searching a table stored in a memory for a record identifying a stored data word corresponding to a binary input data word, wherein the table is comprised of a plurality of records containing a select value field, a left search table address field, a right search table address field, and left and right search table address leaf fields, comprising: (a) selecting a particular single bit of the binary input data word based on a value stored in a select value field, (b) reading either the left or right search table address fields of the record containing said value stored in said first select value field, depending on the binary value of said particular single bit of the input data word indicated, (c) in the event a leaf field corresponding to the read left or right search table address stores a first binary value, repeating steps (a) and (b) using a record identified by the read left or right search table address, (d) in the event a leaf field corresponding to the read left or right search table address stores a second binary value, terminating the search and using the left or right search table address as an address for said data word stored in a second table.
Claim 10
Independent Claim
210 words
A method of searching a table stored in a memory for a record identifying a stored data word corresponding to a binary input data word, wherein the table is comprised of a plurality of records containing a select value field, a left search table address field, a right search table address field, and left and right search table address leaf fields, comprising: (a) selecting a particular single bit of the binary input data word based on a value stored in a select value field, (b) reading either the left or right search table address fields of the record containing said value stored in said first select value field, depending on the binary value of said particular single bit of the input data word indicated, (c) in the event a leaf field corresponding to the read left or right search table address stores a first binary value, repeating steps (a) and (b) using a record identified by the read left or right search table address, (d) in the event a leaf field corresponding to the read left or right search table address stores a second binary value, terminating the search and using the left or right search table address as an address for said data word stored in a second table.
Claim 11
Dependent Claim
36 words
A method as defined in claim 8 in which the left or right search table address which identifies the record in step (c) is a value stored in another select value field of said identified record.
Claim 12
Dependent Claim
16 words
A method as defined in claim 9 in which said first binary value is a "0".
Claim 13
Dependent Claim
56 words
A method as defined in claim 10 in which a left search table address field is searched in the event the binary value of said particular single bit is a "1" and in which a right search table address field is searched in the event the binary value of said particular single bit is a "0".
Claim 14
Independent Claim
168 words
A method of searching a table stored in memory for a record containing a stored data value corresponding to an input data value comprising: (a) identifying a single bit of the input data value, (b) searching a corresponding bit of each stored data value from one end of the table toward the other until a change in the value of said corresponding bit is detected, (c) looking up a leaf bit, stored in association with the identification of the bit of the input data value, which indicates whether the changed value is part of the stored data value to be located, (d) in the event the leaf bit is of one binary value, repeating steps (a), (b) and (c) using a less significant bit as the identified single bit, but searching the table in an opposite direction, (e) in the event the leaf bit is of another binary value, terminating the search and identifying a record containing the changed value as the stored data value to be located.
Claim 15
Independent Claim
168 words
A method of searching a table stored in memory for a record containing a stored data value corresponding to an input data value comprising: (a) identifying a single bit of the input data value, (b) searching a corresponding bit of each stored data value from one end of the table toward the other until a change in the value of said corresponding bit is detected, (c) looking up a leaf bit, stored in association with the identification of the bit of the input data value, which indicates whether the changed value is part of the stored data value to be located, (d) in the event the leaf bit is of one binary value, repeating steps (a), (b) and (c) using a less significant bit as the identified single bit, but searching the table in an opposite direction, (e) in the event the leaf bit is of another binary value, terminating the search and identifying a record containing the changed value as the stored data value to be located.
Claim 16
Dependent Claim
47 words
A method as defined in claim 12 in which the single bit of the input data to be searched is identified by an address derived from a group of successive least significant bits of stored data values one of which is to be located by the search.
Claim 17
Dependent Claim
37 words
A method as defined in claim 12 including identifying a less significant single bit by looking up an identifying address of said less significant single bit stored in association with said single bit identification of step (a).
Claim 18
Dependent Claim
61 words
A method as defined in claim 14 in which the address of said less significant single bit is identified by either of two values, one based on whether the searching of step (b) is to be carried out in one direction and the other based on whether the searching of step (b) is to be carried out in the other direction.
References Cited (Backward Citations)
US4677550A
Cited
EP0419889A2
Cited
US5271010A
Cited
EP0520116A1
Cited
US5323389A
Cited
US5467349A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-28 | 2002-03-30 | 2002-09-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-28 | 2006-03-30 | 2006-09-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-28 | 2010-03-30 | 2010-09-29 | $7700.00 | Window Closed / Lapsed |