A simple proof of Lewin's ordered-retrieval theorem for associative memories

Publisher Website
Google Scholar
Abstract
An efficient method of ordered retrieval of binary words from an associative memory, as described by Lewin, is based on the use of special readout circuits which indicate the digit values present in the individual digit columns of the memory. Thus the circuits indicate whether the individual digit columns contain digits of both values, or of only one value, or contain no digits at all (i.e. that the memory is empty). The use of these circuits, which in this paper are termed column value indicators, reduces considerably the number of memory accesses necessary to retrieve in order a number of distinct binary words from the memory. Lewin proves that, for the readout by the described method of m distinct binary words, 2m--1 memory accesses are necessary. (Thus he proves that the number of necessary memory accesses of his method, unlike those of other methods, is independent of the word length.) In this paper a very simple proof of this theorem derived from some elementary aspects of the structure of sets of binary numbers is presented. only the fornter are affected by the simu[ttmeous interrogation of the column value indicators. The memory access thus results in the indications of the digit values of the specified set of words in the various digit columns. The other words of the memory do not contribute to these indications. The following description makes reference to the illustrative example of Table I, which is a slightly expanded version of the example of Lewin's paper. The illustration of Table I is not meant to specify the positions of the given descriptors; indeed, these descriptors may be quite generally distributed within the words to be retrieved, and may even partition the ordering field. Also, the column value indications of the digit columns of the given descriptors will appear in the output register only if the corresponding column value indicators are interrogated together with those of the ordering field; this is, of course, not necessary in the use of Lewin's method. Lewin's method of ordered retrieval starts with a first memory access made with the aid of a given set of descriptors (see memory access 1). The descriptors reside in an input register whose information content is introduced into the memory. The results of this memory access are the activation of the given set of words and the indications of the digit values of the set in the various digit cohimns. These indications appear in an output register whose individual stages are capable of expressing the various

This publication has 4 references indexed in Scilit: