A Simple Proof of Lewin's Ordered-Retrieval Theorem for Associative Memories 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 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. CACM July, 1968 Wolinsky, A. associative memories, content-addressed memories, ordered lists, ordered information retrieval, ordered retrieval theorem, column digit values, digit value variety, column sensing arrangement, digit value readout, digit variety readout, memory access, memory access frequency, ordered retrieval efficiency, access frequency proof, retrieval theorem proof 3.74 3.79 5.29 5.31 6.31 6.36 CA680704 JB February 22, 1978 12:24 PM 1725 5 1725 1725 5 1725 1725 5 1725