Nearest neighbor serial content addressable memory

摘要

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.

主权项

1. A method for selecting a K-dimensional vector that is a Manhattan nearest neighbor to a K-dimensional input vector containing K N-bit coordinates, from set of K-dimensional vectors, each containing K N-bit coordinates, where K and N are positive integers, the vectors residing in an orthogonal memory, the method utilizing a set of counters, one counter per vector in the set of vectors, the method comprising:
a) initializing, the set of counters; b) successively, for each of the N bits in the coordinates, doubling the counters, and successively tor each of the K coordinates adjusting each counter in parallel with the difference between the bit of the input vector and the corresponding bit of the vector from the set of vectors; and c) selecting, from the set of vectors one or more vectors that are closest to the input vector.