Browse Prior Art Database

Associative Memory with Nearest Match

IP.com Disclosure Number: IPCOM000095001D
Original Publication Date: 1965-Aug-01
Included in the Prior Art Database: 2005-Mar-06
Document File: 4 page(s) / 38K

Publishing Venue

IBM

Related People

Lindquist, AB: AUTHOR

Abstract

The algorithm, utilized in an associative memory, finds a stored word whose bit pattern most nearly matches the bit pattern of an interrogating word. The detection of the nearest matching word is accomplished without the need of providing an individual match counter for each word register.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 4

Associative Memory with Nearest Match

The algorithm, utilized in an associative memory, finds a stored word whose bit pattern most nearly matches the bit pattern of an interrogating word. The detection of the nearest matching word is accomplished without the need of providing an individual match counter for each word register.

A portion of each word register, designated the distance field, is caused to function as a simulated counter for registering a cumulative distance number. This is equal to the number of matching bits which are detected in the respective word as the algorithm is executed. It is also possible to provide a complementary algorithm so that the distance number equals the number of mismatches detected. The length of the distance field depends upon the number of available bit storage positions per word. That is, it must have sufficient capacity to register the maximum number of bit matches or mismatches. The bit storage elements in the various distance fields are conventional associative memory bits. These have the ability to perform an interrogate function and a multiple write function. No changes are required in the memory circuits at the bit or word level to execute this algorithm.

A portion of the interrogating register is allocated to a distance field in which is stored a number designated I'. This changes as the algorithm proceeds, being partly dependent upon the order of the bit position under interrogation. The main part of the interrogating register stores the interrogating word I which does not change. An additional register, designated the entry register, stores a number E that changes as the algorithm proceeds. In general, E is equal to I' plus one. E represents a number which can be written into the distance fields of all matching words, under certain conditions, to simulate a match count in them.

During each interrogation, all words in memory are examined simultaneously to find those words having bits that match a pattern. Such consists of the currently active I bit in combination with the current I' bits. Thus, in the example, the searching pattern during the interrogation of the first bit position comprises the digit 1 in the first positions in the I register are masked. Thus, the first interrogation pattern is 1 -- 00. Each hyphen represents a masked bit position.

In the example, the first and second words have bit patterns that match the first interrogation pattern. The algorithm then calls for writing into the distance field of each matching word a number equal to the current value of E, in this instance 01. Hence, the distance fields of the first and second words are set to 01. The value of I', however, remains at 0 for the time being. The stored words now appear as follows. Word Field Distance Field

First word: 110 01

Second word: 111 01

Third word: 010 00.

1

Page 2 of 4

With I' at 0, following interrogation of the first bit position, the system now is conditioned to interrogate the next, i. e.,...