Nearest neighbor serial content addressable memory

• US 8,339,824 B2
• Filed: 07/02/2008
• Issued: 12/25/2012
• Est. Priority Date: 07/02/2008
• Status: Active Grant

• Current Assignee: Laurence H. Cooke
• Original Assignee: Laurence H. Cooke
• Inventors: Cooke, Laurence H.
• Primary Examiner(s): Sofocleous, Alexander
• Application Number:
  US12/166,960
• Publication Number:
  US 20100005254A1
• Time in Patent Office: 1,637 Days
• Field of Search: None
• US Class Current: 365/49.1
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: H03K 19/02 using specified components H03K19/0005 - H03K19/0021, H03K19/003 - H03K19/0175 take precedence

Abstract

A digital design and technique may be used to implement a Manhattan Nearest Neighbor content addressable memory function by augmenting a serial content addressable memory design with additional memory and counters for bit serially accumulating in parallel and subsequently comparing in parallel all the Manhattan distances between a serially inputted vector and all corresponding vectors resident in the CAM. Other distance measures, besides a Manhattan distance, may optionally be used in conjunction with similar techniques and designs.

Claims

1. A digital logic device comprising:

a serial data input to the digital logic device;

a first memory circuit;

and

compare logic circuitry for respective words of said first memory circuit. wherein the compare logic circuitry for a respective, word of the first memory circuit is configured to serially accept each of all bits of the respective word and to serially compare each serially accepted bit from the respective word with a bit of serial data from the serial data input, and wherein the compare logic circuitry is configured to perform the serial comparing for the respective words of the first memory circuit in parallel.

2. The digital logic device as in claim 1, wherein said compare logic circuitry includes a shifter/counter to accumulate the comparison results.

3. The digital logic device as in claim 1, wherein the digital logic device is configured to perform said comparison and calculating the distance metric in parallel for words stored in the first memory circuit, and to perform this parallel comparison and calculating serially, for respective bits as they are input through the serial data input.

4. The digital logic device as in claim 1, wherein the digital logic device is configured to traverse the words stored in the first memory circuit in parallel, from most-significant bit (MSB) to least-significant bit (LSB), and to set a sign of the distance metric for a given word based on a first bit of the given word that fails to match a bit from the serial data input

5. The digital logic device as in claim 1, further comprising;

a second memory circuit;

wherein said second memory circuit is configured to contain information related to said serial comparison, and

wherein said compare logic is configured to incrementally calculate a distance metric between the respective word and the bits of said serial data input, using said information related to said serial comparison.

6. The digital logic device as in claim 5, wherein said compare logic circuitry includes shifter/counter logic configured to perform one or more operations based at least in part on at least a portion of said information related to the comparison.

7. The digital logic device as in claim 5, wherein said distance metric is a Hamming distance metric.

8. The digital logic, device as in claim 5, wherein said distance metric is a Manhattan distance metric.

9. A digital logic device comprising:

a serial input to the digital logic device;

at least one memory circuit containing at least one set of items;

logic circuitry configured to perform operations ID parallel between data from said serial input and at least a subset of said set of items from at least one said memory circuit, the subset containing at least two items of said set of items, wherein the logic, circuitry is further configured to accept in parallel data of said at least a subset of said set of items to serially receive data from the serial input and to perform the parallel operations as the data from the serial input are serially received, wherein the parallel operations are performed on a common item data received from the serial input in parallel with parallel data items of said at least a subset of said set of items;

wherein said logic circuitry is further configured based on a serial ordering used to order data inputted into said serial input.

10. The digital logic device as in claim 9, wherein an input vector to the logic circuitry is ordered into groups of bits, one bit from each coordinate of an item associated with said set of items, in order from most to least significant bit.

11. The digital logic device as in claim 9, wherein said items in said set of items are ordered into groups of bits, one bit from each coordinate of an item, in order from most to least significant bit.

12. A digital logic device comprising:

a serial dam input to the digital logic device;

a serial content-addressable memory (CAM) circuit;

a second memory circuit; and

compare logic circuitry for each word of said serial CAM circuit;

wherein said second memory circuit is configured to contain information reflecting a result of a comparison of a portion of data from said serial CAM and said serial data input, and wherein said compare logic circuitry incrementally calculates a distance metric between said data from said serial CAM and said serial data input, using said information reflecting the result the comparison.

13. The digital logic device as in claim 12, wherein said compare logic circuitry includes shifter/counter logic configured to perform one or more operations based at least in part on at least a portion of said information reflecting the result of the comparison.

14. The digital logic device as in claim 13, wherein said distance metric is a Hamming distance metric.

15. The digital logic device as in claim 12, wherein said compare logic circuitry includes as shifter/counter to accumulate the results of comparisons.

16. The digital logic device as in claim 15, wherein said distance metric is a Manhattan distance metric.

17. A digital logic device comprising:

a serial input to the digital logic device;

a serial content-addressable memory (CAM) containing at least one set of items;

logic circuitry configured to perform operations in parallel between data from said serial input and at least a subset of said set of items from a serial CAM and further configured based on a serial ordering used to order.

18. The digital logic device as in claim 17, wherein an input vector to the logic circuitry is ordered into groups of bits, one bit from each coordinate of an item associated with said set of items, in order from most to least significant bit.

19. The digital logic device as in claim 17, wherein said items in said set of items are ordered into groups of bits, one bit from each coordinate of an item, in order from most to least significant bit.