Patent US4897814A successfully refreshed from Google Patents.
US4897814A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pipelined "best match" content addressable memory
Assignee: Arizona's Public Universities
•
Filing: 1988-06-06
•
Granted: 1990-01-30
•
Expires: 2008-06-06
Abstract
Abstract A memory system for rapidly choosing a stored item which most closely matches a given input is having a unique memory architecture capable of returning the item stored which most closely correlates to the input. The architecture represents a departure from previous digital content-addressable memories (CAM's) in that it is capable of returning the stored data which most closley resembles the input data rapidly. In addition, a measure of the quality of the selected (best matching) memory is generated. The architecture is capable of significant data throughput rates due to pipelining, and is amenable to implementation using conventional digital VLSI fabrication processes.
Inventors
- 👤 Lawrence T. Clark
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 09:07
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
348 words
A pipelined content addressable memory for rapidly locating the best match therein and generating an address pattern therefrom comprising: a pipeline containing a plurality of identical processing elements, each processing element containing a delay section containing data, a storage section containing data, first means to generate a distance metric between said data in said delay section and said data in said storage section, and second means to compare the magnitude of said distance metric of one processing element with the distance metric generated by the immediately preceding one of said processing elements in said pipeline and when the distance metric of said one processing element is less than that of said immediately preceding processing element placing the address of said one processing element on the address pattern output of said processing element and when the distance metric of said one processing element is greater than or equal to that of said immediately preceding processing element, and placing said address of said immediately preceding processing element on said output; a control circuit generating clock signals which synchronize communication between each of said processing elements and said preceding processing element corresponding thereto; and means for collecting and recording the address pattern created thereby, each such processing element having a data delay memory storage unit, a local control unit having operation storage and used storage means for generating a distance metric between the data contained within said data delay and said memory storage units, means to compare the magnitude of said distance metric generated in said processing element with the smallest distance metric corresponding to the data which is contained in the processing element disposed prior thereto in said pipeline, a least previous distance metric storage unit, a best matching location (that address with the least distance metric) storage unit, and a control circuit having a single bit storage element therein for indicating the validity of the data stored within said processing element, said single bit storage element controlling the writing of new data to the storage of the processing element while avoiding overriding valid data already contained in said storage.
Claim 2
Dependent Claim
348 words
A pipelined content addressable memory for rapidly locating the best match therein and generating an address pattern therefrom comprising: a pipeline containing a plurality of identical processing elements, each processing element containing a delay section containing data, a storage section containing data, first means to generate a distance metric between said data in said delay section and said data in said storage section, and second means to compare the magnitude of said distance metric of one processing element with the distance metric generated by the immediately preceding one of said processing elements in said pipeline and when the distance metric of said one processing element is less than that of said immediately preceding processing element placing the address of said one processing element on the address pattern output of said processing element and when the distance metric of said one processing element is greater than or equal to that of said immediately preceding processing element, and placing said address of said immediately preceding processing element on said output; a control circuit generating clock signals which synchronize communication between each of said processing elements and said preceding processing element corresponding thereto; and means for collecting and recording the address pattern created thereby, each such processing element having a data delay memory storage unit, a local control unit having operation storage and used storage means for generating a distance metric between the data contained within said data delay and said memory storage units, means to compare the magnitude of said distance metric generated in said processing element with the smallest distance metric corresponding to the data which is contained in the processing element disposed prior thereto in said pipeline, a least previous distance metric storage unit, a best matching location (that address with the least distance metric) storage unit, and a control circuit having a single bit storage element therein for indicating the validity of the data stored within said processing element, said single bit storage element controlling the writing of new data to the storage of the processing element while avoiding overriding valid data already contained in said storage.
Claim 3
Dependent Claim
18 words
A pipelined content addressable memory according to claim 1 in which said distance metric is the Hamming distance.
Claim 4
Dependent Claim
25 words
A pipelined content addressable memory according to claim 2 in which said means to compare magnitudes of distance metrics is a bit serial magnitude comparator.
Claim 5
Dependent Claim
23 words
A pipelined content addressable memory according to claim 2 in which said least previous distance metric storage unit is a static shift register.
Claim 6
Dependent Claim
23 words
A pipelined content addressable memory according to claim 2 in which said least previous matching location storage unit is a static parallel register.
Claim 7
Dependent Claim
25 words
A pipelined content addressable memory according to claim 1 in which said means to compare magnitudes of distance metrics is a bit serial magnitude comparator.
Claim 8
Dependent Claim
23 words
A pipelined content addressable memory according to claim 1 in which said least previous distance metric storage unit is a static shift register.
Claim 9
Dependent Claim
23 words
A pipelined content addressable memory according to claim 6 in which said least previous matching location storage unit is a static parallel register.
Claim 10
Dependent Claim
23 words
A pipelined content addressable memory according to claim 1 in which said least previous distance metric storage unit is a static shift register.
Claim 11
Dependent Claim
23 words
A pipelined content addressable memory according to claim 9 in which said least previous matching location storage unit is a static parallel register.
Claim 12
Dependent Claim
23 words
A pipelined content addressable memory according to claim 1 in which said least previous matching location storage unit is a static parallel register.
Claim 13
Dependent Claim
38 words
A pipelined content addressable memory according to claim 1 in which said single bit storage element controls the matching of input data to the data stored in said element without matching input data to invalid data stored therein.
Claim 14
Dependent Claim
347 words
A pipelined content addressable memory for rapidly locating the best match therein and generating an address pattern therefrom comprising: a pipeline containing a plurality of identical processing element, each processing element containing a delay section containing data, a storage section containing data, first means to generate a distance metric between said data in said delay section and said data in said storage section, and second means to compare the magnitude of said distance metric of one processing element with the distance metric generated by the immediately preceding one of said processing elements in said pipeline and when the distance metric of said one processing element is less than that of said immediately preceding processing element, placing the address of said one processing element on the address pattern output of said processing element and when the distance metric of said one processing element is greater than or equal to that of said immediately preceding processing element, and placing said address of said immediately preceding processing element on said output; a control circuit generating clock signals which synchronize communication between each of said processing elements and said preceding processing element corresponding thereto; and means for collecting and recording the address pattern created thereby, each such processing element having a data delay memory storage unit a local control unit having operation storage and used storage means for generating a distance metric between the data contained within said data delay and said memory storage units, means to compare the magnitude of said distance metric generated in said processing element with the smallest distance metric corresponding to the data which is contained in the processing element disposed prior thereto in said pipeline, a least previous distance metric storage unit, a best matching location (that address with the least distance metric) storage unit, and a control circuit having a single bit storage element therein for indicating the validity of the data stored within said processing element said single bit storage element controlling the matching of input data to the data stored in said element without matching input data to invalid data stored therein.
Claim 15
Dependent Claim
347 words
A pipelined content addressable memory for rapidly locating the best match therein and generating an address pattern therefrom comprising: a pipeline containing a plurality of identical processing element, each processing element containing a delay section containing data, a storage section containing data, first means to generate a distance metric between said data in said delay section and said data in said storage section, and second means to compare the magnitude of said distance metric of one processing element with the distance metric generated by the immediately preceding one of said processing elements in said pipeline and when the distance metric of said one processing element is less than that of said immediately preceding processing element, placing the address of said one processing element on the address pattern output of said processing element and when the distance metric of said one processing element is greater than or equal to that of said immediately preceding processing element, and placing said address of said immediately preceding processing element on said output; a control circuit generating clock signals which synchronize communication between each of said processing elements and said preceding processing element corresponding thereto; and means for collecting and recording the address pattern created thereby, each such processing element having a data delay memory storage unit a local control unit having operation storage and used storage means for generating a distance metric between the data contained within said data delay and said memory storage units, means to compare the magnitude of said distance metric generated in said processing element with the smallest distance metric corresponding to the data which is contained in the processing element disposed prior thereto in said pipeline, a least previous distance metric storage unit, a best matching location (that address with the least distance metric) storage unit, and a control circuit having a single bit storage element therein for indicating the validity of the data stored within said processing element said single bit storage element controlling the matching of input data to the data stored in said element without matching input data to invalid data stored therein.
References Cited (Backward Citations)
US4084260A
Cited
US4438489A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-01-29 | 1993-07-31 | 1994-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-01-29 | 1997-07-31 | 1998-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-01-29 | 2001-07-31 | 2002-01-30 | $7700.00 | Window Closed / Lapsed |