Nearest neighbor serial content addressable memory
OwnerLaurence H. Cookeinventor
Life of this patent
Estimating the term…
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.
Claims13
A digital logic device comprising:
- a serial data input to the digital logic device;
- a plurality of memory circuits;
- and
- compare logic circuitry for respective words of a selected one of the plurality of memory circuits;
- wherein the compare logic circuitry for a respective word of the selected one of the plurality of memory circuits 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 selected one of the plurality of memory circuits in parallel.
A digital logic device comprising:
- a plurality of memories, each containing a plurality of words and logic configured to write data into a respective word of each memory;
- comparison logic connected to an input and configured to compare the data in multiple words of a selected one of the plurality of memories with data from the input;
- and
- encode logic connected to said comparison logic and configured to select a nearest neighbor from the selected one of the plurality of memories,
- wherein the comparison logic and encode logic are configured to perform a nearest neighbor calculation on a selected one of the plurality of memories while one or more words in an enabled memory, other than the selected one of the plurality of memories, are being written.
A method of obtaining from at least one of a plurality of memories a nearest neighbor to a serially-input data word, the method comprising:
- selecting one of the plurality of memories;
- comparing, in parallel, data of multiple words of the selected one of the plurality of memories with data from the serially-input data word;
- and
- selecting a word of the selected one of the plurality of memories as the nearest neighbor.
A method for finding the location of a minimum of a set of numbers residing in a memory device, each number having a corresponding flag, the method comprising;
- setting, by a computing device, all of the flags;
- selecting, by the computing device, an integer m such that a maximum of the set of numbers in the memory device is less than 2m;
- performing, by the computing device, the following operations until all of the numbers are zero:
- doubling all of the numbers;
- clearing a flag corresponding to a number if the number is less than 2m;
- and
- subtracting 2m from all of the numbers that are larger than 2m−1;
- and
- selecting, by the computing device, and outputting at least one memory location from a set of memory locations corresponding to flags that remain set.
Dependencies are inferred from the claim text.