Method and apparatus for a sparse distributed memory system

• US 5,113,507 A
• Filed: 05/03/1989
• Issued: 05/12/1992
• Est. Priority Date: 10/20/1988
• Status: Expired due to Fees

• Current Assignee: Universities Space Research Association Columbia MD
• Original Assignee: Universities Space Research Association (The National Academies of Science)
• Inventors: Jaeckel, Louis A.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/353,179
• Time in Patent Office: 1,105 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/5
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A computer memory includes K hard memory locations, hereinafter HMLs, each HML having M counters. A reference address element stores a reference address sequence of N bits. A data register stores data as a sequence of M integers. The memory has a processor system for determining a subset of HMLs to access for each reference address during read and write operations. For each HML, the processor system receives a subset of the reference address bits equal in number to q. The subset of reference address bits is chosen by selecting, for each HML, q integers between 1 and N as selected coordinates, hereinafter SCs, each SC corresponding to a bit position within the reference address, and for each SC for each HML, assigning a 0 or 1 as an assigned value for that SC. The processor system then stores the SCs and the assigned values and, for each of the SCs for each of the HMLs, compares the assigned value for the SC with the value of the corresponding bit in the reference address bits. The processor system then accesses those HMLs for which the assigned values for all SCs are identical with the corresponding bits in the subset of the reference address bits. During a write, the processor system combines data in the data register with any data already located in the M counters in each of the accessed HMLs, the M counters in each of the accessed HMLs being used for storing the combined data. The memoryy also has an accumulator system made up of a set of M accumulators with the i^th accumulator coupled to receive data from the i^th counter, for each accessed HML, so that each of the accumulators accumulates integers from the counters, receiving one integer from the corresponding counter for each accessed HML, thereby obtaining a value Vi in the i^th accumulator. The accumulator system can then be used for outputting data corresponding to the values in the accumulators.

Claims

1. A computer memory system comprising:

a plurality of hard memory locations in number equal to K, where K is an integer greater than one, each hard memory location comprising M counters, C1 through CM, where M is an integer greater than zero;

reference address means for storing a reference address received from a source external to said memory system, said reference address being a sequence of N bits, where N is an integer greater than zero;

data register means for storing data as a sequence of M integers;

processor means coupled to said reference address means, to said hard memory locations, and to said data register means, for determining for each reference address a subset of hard memory locations to be made available during read operations and during write operations, each such hard memory location that is made available hereinafter called an activated hard memory location, and for reading from and writing to said activated hard memory locations, said processor means coupled to said reference address means such that for each hard memory location said processor means receives a subset of said reference address bits equal in number to q, where q is an integer related to the proportion of the number of hard memory locations in said memory system that are to be accessed relative to the total number of hard memory locations in the memory system;

said subset of reference address bits chosen by selecting for each hard memory location, q integers between 1 and N as selected coordinates, each selected coordinate corresponding to a bit position within said reference address, and for each selected coordinate for each hard memory location, assigning a zero or one, as an assigned value for that selected coordinate;

said processor means for receiving said selected coordinates and said assigned values and in response to receiving said subset of reference address bits, for each of said selected coordinates for each of said hard memory locations, comparing the assigned value for the selected coordinate with the value of the corresponding bit in the subset of the reference address bits;

said activated hard memory locations comprising those hard memory locations for which the assigned values for all selected coordinates are identical with the corresponding bits in the subset of the reference address bits; and

said processor means during a write operation for combining data in said data register means with any data already located in said M counters in each of said activated hard memory locations, said M counters in each of said activated hard memory locations for storing said combined data; and

accumulator means comprising a set of M accumulators, A1 through AM, with the i^th accumulator, Ai, coupled to receive data from the i^th counter, Ci, for each activated hard memory location, where i=1 through M, so that during a read operation each of said accumulators accumulates integers from said counters, the i^th accumulator, Ai, receiving one integer from the i^th counter for each activated hard memory location, thereby obtaining a value Vi in the i^th accumulator, Ai.

3. A computer memory system as in claim 1 or claim 2 further comprising thresholding means coupled to said accumulator means for converting said data in said M accumulators to bits and providing a set of output values {Qi}, such that if {Xi} is a set of M thresholding numbers, than Qi=0 if Vi<

Xi and Qi=1 if Vi≧

Xi, or Qi=1 if Vi<

Xi and Qi=0 if Vi≧

Xi.

4. A computer memory system as in claim 1 or claim 2 further comprising thresholding means coupled to said accumulator means for converting said data in said M accumulators to bits and providing a set of output values {Qi}, such that if {Xi} is a set of M thresholding numbers, then Qi=0 if Vi≦

Xi and Qi=1 if Vi>

Xi, or Qi=1 if Vi≦

Xi and Qi=0 if Vi>

Xi.

5. A computer memory system as in claim 1 or claim 2 wherein said processor means when combining said data in said data register means with data in each of said counters of each of said activated hard memory locations, adds the value of the data in the i^th position in said data register means to the value in the i^th counter, Ci, and stores the result in counter Ci.

6. A computer memory system as in claim 1 or claim 2 wherein said data are in the form of bits in said data register means, and wherein said processor means when combining said data in said data register means with data in each of said counters of each of said activated hard memory locations, increments the value of the data in the i^th counter, Ci, if the value of the i^th bit in the data register means is 1, and decrements the value of the data in the i^th counter, Ci, if the value of the i^th bit in the data register means is 0.

7. A computer memory system as in claim 1 or claim 2 wherein said processor means comprises a plurality of address decoder means, each of said address decoder means coupled to at least one of said hard memory locations and to said reference address means, said address decoder means for designating which hard memory locations are to become activated hard memory locations in response to said reference address.

8. A computer memory system as in claim 7 wherein said plurality of address decoder means comprises K address decoders, with each of said address decoders being coupled to one of said hard memory locations and to said reference address means, such that each of said hard memory locations is coupled to only one of said address decoders.

10. A computer memory system as in claim 7 wherein said processor means comprises K individual processors, with each of said K individual processors being coupled to one of said hard memory locations and to said data register means, such that each of said hard memory locations is coupled to only one of said K individual processors, said K individual processors for combining said data from said data register means with data in said M counters in each of said activated hard memory locations.

2. A computer memory system comprising:

reference address means for storing a reference address received from a source external to said memory system, said reference address being a sequence of N bits, where N is an integer greater than zero;

a plurality of hard memory locations in number equal to K, where K is an integer greater than one, each hard memory location comprising M counters, C1 through CM, where M is an integer greater than zero, and each hard memory location having associated therewith an integer q and a threshold T, said q and T which may be difference for each hard memory location, and said integers q≦

N, except that if all q=N, not all T have the same value;

data register means for storing data as a sequence of M integers;

processor means coupled to said reference address means, to said hard memory locations, and to said data register means, for determining a subset of hard memory locations, hereinafter called activated hard memory locations, to access for each reference address and for accessing said activated hard memory locations during read operations and during write operations, said processor means coupled to said reference address means such that for each hard memory location said processor means receives a subset of said reference address bits equal in number to q for that hard memory location;

said subset of reference address bits chosen by selecting for each hard memory location a set of integers equal in number to q for that hard memory location as selected coordinates, each selected coordinate corresponding to a bit position within said reference address, and for each selected coordinate for each hard memory location, assigning a zero or one as an assigned value for that selected coordinate;

said processor means for receiving said selected coordinates and said assigned values and in response to receiving said subset of reference address bits, for each of said selected coordinates for each of said hard memory locations, comparing the assigned value for the selected coordinate with the value of the corresponding bit in the subset of the reference address bits; and

said processor means for computing for each hard memory location the value of a function based on the comparison by the processor means of the assigned values for all selected coordinates for the particular hard memory location with the values of the corresponding bits in the subset of the reference address bits, said process means for providing an activation signal for each hard memory location based on a comparison of the value of said function to the threshold T for that hard memory location;

said processor means during a write operation for combining data in said data register means with any data already located in said M counters in each of said activated hard memory locations, said M counters in each of said activated hard memory locations for storing said combined data; and

accumulator means comprising a set of M accumulators, A1 through AM, with the i^th accumulator, Ai, coupled to receive data from the i^th counter, Ci, for each activated hard memory location, where i=1 through M, so that during a read operation each of said accumulators accumulates integers from said counters, the i^th accumulator, Ai, receiving one integer from the i^th counter for each activated hard memory location, thereby obtaining a value Vi in the i^th accumulator, Ai.

11. A computer memory system as in claim 2 wherein said function based on the comparison by the processor means comprises the number of all selected coordinates for which the assigned values do not equal the corresponding bits in the subset of reference address bits.

9. A computer memory system as in claim 9 wherein each of said address decoders comprises bit comparator means with q inputers and q outputs, said inputs coupled to said reference address means for comparing said bits in said reference address with said assigned values for said selected coordinate, and wherein each of said address decoders further comprises an AND-Gate with q inputs, with each of said q outputs from said bit comparator means being coupled to one of the q inputs to said AND-Gate, the output signal from said AND-gate for determining said activated hard memory locations.

12. A computer memory system that can retrieve stored vectors of data, based on only approximate addressing information, comprising:

control module means;

data module means having a plurality of data storage means equal in number to K, where K is a positive integer, each data storage means having Mm counters, where M is a positive integer, said data module means having a processor means for combining the contents of said counters with incoming vectors of data from said control module means, each counter for storing a linear combination of corresponding components of vectors of data transmitted from said control module means; and

address module means for providing address information to said control module means, comprising;

reference address means for storing a reference address as a vector of bits received from said control module means;

selected coordinate means for storing a set of bit positions for each data storage means in said data module means, said bit positions hereinafter called the selected coordinates for the corresponding data storage means;

assigned value means for storing a set of bits, hereinafter called a vector of assigned value bits, associated with the selected coordinates for each data storage means;

exclusive-OR means for performing a logical exclusive OR between vectors output from said reference address means and vectors output from said assigned value means;

AND means for performing a logical AND of the vector output from said exclusive-OR means and the vector output from said selected coordinate means;

zero test means for testing the vectors output from said AND means, and for providing an identification signal for each vector from said AND means when all bits in a vector from said AND means are zeros; and

activating means for receiving said identification signals and for providing a set of signals to said control module means indicating which data storage means in said data module means are to be made accessible during a read operation or during a write operation, hereinafter called activated data storage means, based on said reference address;

said processor means of said data module means also comprising accumulator means for summing data from said counters in said data storage means to enable reading data from said memory system, such that if a set of data storage means is activated for a read operation said accumulator means sums the contents of corresponding counters of said activated data storage means to form a vector of M sums, and for transmitting a signal to said control module means corresponding to said vector of M sums; and

said control module means for controlling said address module means and said data module means and for receiving read information and write information from a user interface, and for transmitting vectors of data to said data module means, and for transmitting data from said processor means to the user interface.

13. A computer memory system as in claim 12 wherein said activating means comprises hit switch means and tag cache means, said hit switch means for receiving said identification signals from said zero test means and for providing an activating signal to said tag cache means, said tag cache means for storing identifiers corresponding to which data storage means are to be made accessible in response to said activating signals, and for providing said identifiers to said control module means.

14. A method of accessing hard memory locations in a Sparse Distributed Memory for storing or retrieving data, comprising the steps of:

choosing a number N, where N is a positive integer, and where N is the number of bits in a reference address vector;

choosing a number q, where q is an integer relates to the proportion of the number of hard memory locations to be accessed in said Memory during a single read or write operation;

for each hard memory location, choosing q integers between 1 and N, as selected coordinates to represent positions within each of said reference address vectors;

for each selected coordinate of each hard memory location, assigning a zero or one, as the assigned value for that selected coordinate;

storing said selected coordinates and said assigned values;

in response to a reference address vector provided during a read or a write operation, for each selected coordinate for each hard memory location, comparing the value of the corresponding coordinate of the reference address vector with the assigned value for that selected coordinate; and

accessing those hard memory locations for which the assigned values for all selected coordinates are identical with the corresponding bits of the reference address vector.

15. A method of storing data in a Sparse Distributed Memory having a plurality of hard memory locations, said data having a reference address vector, comprising the steps of:

choosing a number N, where N is a positive integer, and where N is the number of bits in said reference address vector;

choosing a number q, where q is an integer that is related to the proportion of the number of hard memory locations to be written to in said Memory during a single write operation;

for each hard memory location, choosing q integers between 1 and N, as selected coordinates to represent positions within said reference address vector;

for each selected coordinate of each hard memory location, assigning a zero or one, as the assigned value for that selected coordinate;

storing in said Sparse Distributed Memory said selected coordinates and said assigned values;

in response to said reference address vector provided during a a write operation, or each selected coordinate for each hard memory location, comparing the value of the corresponding coordinate of said reference address vector with the assigned value for that selected coordinate; and

combining said data to be stored during said write operation with any data already located in each of those hard memory locations for which the assigned values for all selected coordinates are identical with the corresponding bits of said reference address vector.

16. A computer memory system that can retrieve stored vectors of data, based on only approximate addressing information, comprising:

control module means for providing a reference address during read and write operations and a data vector corresponding to said reference address during write operations;

data module means having a plurality of data storage means equal in number to K, where K is a positive integer, each data storage means having associated therewith M counters, where M is a positive integer, said data module means having a processor means for summing the contents of said counters with incoming vectors of data from said control module means, each counter for storing a linear combination of corresponding components of vectors of data transmitted from said control module means; and

address module means coupled to said control module means comprising;

tag counter means for providing a sequence of output signals corresponding to each data storage means in said data module means in response to signals from said control module means;

hard address means coupled to receive said output signals from said tag counter means for storing a set of bit positions for each data storage means in said data module means, said bit positions hereinafter called the selected coordinates for the corresponding data storage means, said hard address means also for storing a set of bits, hereinafter called assigned value bits, associated with said selected coordinates for each data storage means;

logic means for receiving said reference address from said control module means, for storing said reference address as a sequence of bits, for comparing said assigned value bits with corresponding bits from said reference address for said selected coordinates for each data storage means, and for providing an output logic signal when all of said compared bits for a data storage means match, thereby identifying which data storage means are to be accessed for storing or retrieving information in response to said reference address; and

activating means for receiving said output logic signals from said logic means and for providing a set of signals to said control module means indicating which data storage means in said data module means are to be accessed based on said reference address;

said processor means of said data module means also comprising accumulator means for summing data from said counters in said data storage means for reading data from said memory system, such that when a set of data storage means is accessed, said accumulator means sums the contents of corresponding counters of said accessed data storage means to form a vector of M sums, and for transmitting a signal to said control module means corresponding to said vector of M sums; and

said control module means for controlling said address module means and said data module means and for receiving read information and write information from a user interface, and for transmitting vectors of data to said data module means, and for transmitting data from said processor means to the user interface.

17. A computer memory system as in claim 16 wherein said activating means comprises hit switch means and tag cache means, said hit switch means for receiving said output logic signals and for providing an activating signal to said tag cache means, said tag cache means for storing identifiers corresponding to which data storage means are to be accessed in response to said activating signals, and for providing said identifiers to said control module means indicating which data storage means in said data module means are to be accessed.

58. A computer memory system as in claim 16 wherein said function based on the comparison by the processor means comprises the number of all selected coordinates for which the assigned values equal the corresponding bits in the subset of reference address bits.

18. A computer memory system that can retrieve stored vectors of data, based on only approximate addressing information, comprising:

control module means for controlling said computer memory system;

data module means having a plurality of data storage means equal in number to K, where K is a positive integer, each data storage means having M counters, where M is a positive integer, said data module means having a processor means for combining the contents of said counters with incoming vectors of data from said control module means, each counter for storing a linear combination of corresponding components of vectors of data transmitted from said control module means; and

address module means for receiving a reference address from said control module means, said reference address being a sequence of numerical values, said address module means comprising;

selected coordinate means for storing information identifying a set of positions in said sequence for each data storage means in said data module means, said positions hereinafter called the selected coordinates for the corresponding data storage means; and

function means for comparing a value of a function of the values of the reference address corresponding to the selected coordinates for each data storage means with a set of numerical values, hereinafter called assigned values, for the selected coordinates for that data storage means, said function means for providing in response to said comparison a set of identification signals indicating which data storage means in said data module means are to be accessed based on said reference address;

said processor means of said data module means also for summing data from said counters in said data storage means to enable reading data from said memory system, such that if a set of data storage means is accessed for a read operation said processor means sums the contents of corresponding counters of said accessed data storage means to form a vector of M sums, and for transmitting a signal to said control module means corresponding to said vector of M sums; and

said control module means for controlling said address module means and said data module means and for receiving read information and write information from a user interface, and for transmitting vectors of data to said data module means, and for transmitting data from said processor means to a user interface.

19. A memory as in claim 18 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s, and wherein said function means comprises:

OR means coupled to receive said reference address and coupled to receive said information identifying said selected coordinates from said selected coordinate means, said OR means for performing a logical OR of the sequence of numerical values from the reference address with the sequence of bits from the selected coordinate means for each data storage means; and

test means for testing said result for all 1'"'"'s for each data storage means.

20. A memory system as in claim 18 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s, and wherein said function means comprises:

AND means for performing a logical AND of the sequence of reference address bits with the sequence of bits for each data storage means from the selected coordinate means and outputting the results thereof;

adder means for adding said results for each data storage means to obtain a sum for each data storage means; and

comparison means for comparing the sum for each data storage means with a numerical value, hereinafter called a threshold value, for that data storage means.

21. A memory system as in claim 20 further comprising threshold means for providing said threshold value for each data storage means to said comparison means.

22. A memory system as in claim 18 wherein said reference address is a vector of bits, said memory system further comprising:

assigned value means for storing said assigned values as a vector of assigned value bits associated with the selected coordinates for each data storage means; and

wherein said function means comprises Exclusive-OR means for performing a logical exclusive OR between said reference address vectors and vectors output from said assigned value means;

AND means for performing a logical AND of the vectors output from said Exclusive-OR means and the vectors output from said selected coordinate means and outputting said results;

adder means for adding said results for each data storage means to obtain a sum for each data storage means; and

comparison means for comparing the sum for each data storage means with a numerical value, hereinafter called a threshold value, for that data storage means.

23. A memory system as in claim 22 further comprising threshold means for providing said threshold value for each data storage means to said comparison means.

24. A memory system as in claim 18 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s and wherein said function means comprises:

AND means for performing a logical AND of the complement of said first sequence of reference address bits with said second sequence of bits from said selected coordinate means for each data storage means, and outputting results as an output vector; and

zero test means for testing the output vector from said AND means for all 0'"'"'s for each data storage means.

25. A computer memory system that can retrieve stored vectors of data, based on only approximate addressing information, comprising:

control module means for providing a reference address which is a sequence of numerical values during read and write operations and a data vector corresponding to said reference address during write operations;

data module means having a plurality of data storage means equal in number to K, where K is a positive integer, each data storage means having associated therewith M counters, where M is a positive integer, said data module means having a processor means for summing the contents of said counters with incoming vectors of data from said control module means, each counter for storing a linear combination of corresponding components of vectors of data transmitted from said control module means; and

address module means coupled to said control module means comprising;

hard address means for storing information identifying a set of positions in said sequence for each data storage means in said data module means, said positions hereinafter called selected coordinates for the corresponding data storage means; and

logic means for receiving said reference address from said control module means, for comparing an evaluation of a function of the values of the reference address corresponding to the selected coordinates for each data storage means with a set of numerical values, hereinafter called assigned values for the selected coordinates for that data storage means, and for providing in response to said comparisons a set of output logic signals identifying which data storage means are to be accessed for storing or retrieving information in response to said reference address;

said processor means of said data module means also for summing data from said counters in said data storage means to enable reading data from said memory system, such that when a set of data storage means is accessed said processor means sums the contents of corresponding counters of said accessed data storage means to form a vector of M sums, and for transmitting a signal to said control module means corresponding to said vector of M sums; and

said control module means for controlling said address module means and said data module means and for receiving read information and write information from a user interface, and for transmitting vectors of data to said data module means, and for transmitting data from said processor means to the user interface.

26. A computer memory system as in claim 25 wherein said logic means further comprises bit switch means and tag cache means, said bit switch means for providing activating signals to said tag cache means in response to said comparisons, said tag cache means for storing identifiers corresponding to those data storage means that are to be accessed in response to said activating signals, and for providing said set of output logic signals indicating which data storage means in said data module means are to be accessed.

27. A computer memory system as in claim 25 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means for accessing for which the bits of the reference address vector corresponding to the selected coordinates for that data storage means match the assigned values for all of the selected coordinates.

28. A computer memory system as in claim 25 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates match the assigned values is greater than or equal to a numerical value, hereinafter called a threshold value, for that data storage means.

29. A computer memory system as in claim 28 wherein said hard address means is also for storing said threshold value for each data storage means.

30. A computer memory system as in claim 25 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means for accessing for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates do not match the assigned values is less than or equal to a numerical value, hereinafter called a threshold value, for that data storage means.

31. A computer memory system as in claim 25 wherein each of said reference addresses is a vector of bits, wherein said hard address means is also for storing a set of bits as assigned values, hereinafter called assigned value bits, associated with the selected coordinates for each data storage means and for providing said set of assigned value bits to said logic means, and wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates do not match the assigned values is less than or equal to a numerical value, hereinafter called a threshold value, for that data storage means.

32. A computer memory system as in claim 25 wherein each of said reference addresses is a vector of bits, wherein said hard address means is also for storing a set of bits as assigned values, hereinafter called assigned value bits, associated with the selected coordinates for each data storage means and for providing said set of assigned value bits to said logic means, and wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates match the assigned values is greater than or equal to a numerical value, hereinafter called a threshold value, for that data storage means.

33. A computer memory system as in claims 25, 28, 30, 31, or 32 wherein each data storage means has the same number of selected coordinates.

34. A computer memory system as in claims 28, 30, 31 or 32 wherein said hard address means is also for storing the number of selected coordinates and the threshold value for each data storage means, and for providing said numbers and said threshold values to said logic means.

35. A computer memory system as in claim 25 wherein said hard address means is also for storing the number of selected coordinates and a numerical value, hereinafter called a threshold value, for each data storage means, and for providing said numbers and said threshold values to said logic means.

36. An address module for a computer memory system having a set of data storage means, said address module for receiving a reference address, said reference address being a sequence of numerical values, said address module comprising:

selected coordinate means for storing information identifying a set of positions in said sequence for each data storage means in said computer memory system, said positions hereinafter called the selected coordinates for the corresponding data storage means; and

function means for comparing a value of a function of the values of the reference address corresponding to the selected coordinates for each data storage means with a set of numerical values, hereinafter called assigned values, for the selected coordinates for that data storage means, said function means for providing in response to said comparison a set of identification signals indicating which data storage means in said memory system are to be accessed for storing or retrieving data in response to said reference address.

37. An address module as in claim 36 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s , and wherein said function means comprises:

OR means coupled to receive said reference address and coupled to receive said information identifying said selected coordinates from said selected coordinate means, said OR means for performing a logical OR of the sequence of numerical values from the reference address with the sequence of bits from the selected coordinate means for each data storage means and outputting the result thereof; and

test means for testing said result for all 1'"'"'s for each data storage means.

38. An address module as in claim 36 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s, and wherein said function means comprises:

AND means for performing a logical AND of the sequence of reference address bits with the sequence of bits from the selected coordinate means for each data storage means and outputting the results thereof;

adder means for adding said results for each data storage means to obtain a sum for each data storage means; and

comparison means for comparing the sum for each data storage means with a numerical value, hereinafter called a threshold value, for that data storage means.

39. An address module as in claim 38 further comprising threshold means for providing said threshold value for each data storage means to said comparison means.

40. An address module as in claim 36 wherein said reference address is a vector of bits, said address module further comprising:

assigned value means for storing said assigned values as a vector of assigned value bits associated with the selected coordinates for each data storage means; and

wherein said function means comprises Exclusive-OR means for performing a logical exclusive OR between said reference address vectors and vectors output from said assigned value means;

AND means for performing a logical AND of the vectors output from said Exclusive-OR means and the vectors output from said selected coordinate means and outputting said results;

adder means for adding said results for each data storage means to obtain a sum for each data storage means; and

comparison means for comparing the sum for each data storage means with a numerical value, hereinafter called a threshold value, for that data storage means.

41. An address module as in claim 40 further comprising threshold means for providing said threshold value for each data storage means to said comparison means.

42. An address module as in claim 36 wherein said numerical values in the reference address comprise a first sequence of bits, wherein said information identifying said set of positions comprises a second sequence of bits for each data storage means, one bit for each position in the first sequence of bits, wherein the assigned values for all selected coordinates are 1'"'"'s, and wherein said function means comprises:

AND means for performing a logical AND of the complement of said first sequence of reference address bits with said second sequence of bits from said selected coordinate means for each data storage means, and outputting results as an output vector; and

zero test means for testing the output vector from said AND means for all 0'"'"'s for each data storage means.

43. An address module for a computer memory system having a set of data storage means, said address module for receiving a reference address, said reference address being a sequence of numerical values, said address module comprising:

hard address means for storing information identifying a set of positions in said sequence for each data storage means, said positions hereinafter called selected coordinates for the corresponding data storage means; and

logic means for receiving said reference address, for comparing an evaluation of a function of the values of the reference address corresponding to the selected coordinates for each data storage means with a set of numerical values, hereinafter called assigned values, for the selected coordinates for that data storage means, and for providing in response to said comparisons a set of output logic signals identifying which data storage means are to be accessed for storing or retrieving data in response to said reference address.

44. An address module as in claim 43 wherein said logic means further comprises hit switch means and tag cache means, said hit switch means for providing activating signals to said tag cache means in response to said comparisons, said tag cache means for storing identifiers corresponding to those data storage means that are to be accessed in response to said activating signals, and for providing said set of output logic signals indicating which data storage means are to be accessed.

45. An address module as in claim 43 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means for accessing for which the bits of the reference address vector corresponding to the selected coordinates for that data storage means match the assigned values for all of the selected coordinates.

46. An address module as in claim 43 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means for accessing for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates match the assigned values is greater than or equal to a numerical value, hereinafter called a threshold value, for that data storage means.

47. An address module as in claim 46 wherein said hard address means is also for storing said threshold value for each data storage means.

48. An address module as in claim 43 wherein said reference address is a vector of bits, wherein said assigned values for said selected coordinates are all 0'"'"'s or all 1'"'"'s, wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates do not match the assigned values is less than or equal to a numerical value, hereinafter called a threshold value for that data storage means.

49. An address module as in claim 43 wherein each of said reference addresses is a vector of bits, wherein said hard address means is also for storing a set of bits as assigned values, hereinafter called assigned value bits, associated with the selected coordinates for each data storage means and for providing said set of assigned value bits to said logic means, and wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates do not match the assigned values is less than or equal to a numerical value, hereinafter called a threshold value for that data storage means.

50. An address module as in claims 46, 48, or 49, wherein said hard address means is also for storing the number of selected coordinates and the threshold value for each data storage means, and for providing said numbers and said threshold values to said logic means.

51. An address module as in claim 43 wherein each of said reference addresses is a vector of bits, wherein said hard address means is also for storing a set of bits as assigned values, hereinafter called assigned value bits, associated with the selected coordinates for each data storage means and for providing said set of assigned value bits to said logic means, and wherein said output logic signals identify those data storage means to be accessed for which the number of selected coordinates for which the bits in the reference address corresponding to the selected coordinates match the assigned values is greater than or equal to a numerical valued, hereinafter called a threshold value, for that data storage means.

52. An address module as in claim 51 wherein said hard address means is also for storing the number of selected coordinates and the threshold value for each data storage means, and for providing said numbers and said threshold values to said logic means.

53. An address module as in claim 43 wherein said hard address means is also for storing the number of selected coordinates and a numerical value, hereinafter called a threshold value, for each data storage means, and for providing said numbers and said threshold values to said logic means.

54. A method of accessing hard memory locations in a Sparse Distributed memory when storing or retrieving data, comprising the steps of:

choosing a number N, where N is a positive integer;

providing a reference address vector which is N bits in length;

for each hard memory location, choosing an integer q and a threshold T, which may be different for each hard memory location, said integer q≦

N except that if all q=N, not all T have the same value;

for each hard memory location, choosing q distinct integers between 1 and N, as selected coordinates to represent positions within said reference address vector;

for each selected coordinate for each hard memory location, assigning a zero or one, as an assigned value for that selected coordinate;

in response to a reference address vector provided during a read or a write operation, for each hard memory location, evaluating a function of the values of the reference address corresponding to the selected coordinates for that hard memory location and the assigned values for the selected coordinates for that hard memory location; and

accessing those hard memory locations for which said function is greater than or equal to said threshold T.

55. A method of storing data in a Sparse Distributed Memory having a plurality of hard memory locations comprising the steps of:

choosing a number N, where N is a positive integer;

providing a reference address vector which is N bits in length;

for each hard memory location, choosing an integer q and a threshold T, which may be different for each hard memory location, said integer q≦

N except that if all q=N, not all T have the same value;

for each hard memory location, choosing q distinct integers between 1 and N, as selected coordinates to represent positions within said reference address vector;

for each selected coordinate for each hard memory location, assigning a zero or one, as an assigned value for that selected coordinate;

in response to a reference address vector provided during a write operation, for each hard memory location, evaluating a function of the values of the reference address corresponding to the selected coordinates for that hard memory location and the assigned values for the selected coordinates for that hard memory location; and

combining data to be written during said write operation with any data already located in each of those hard memory locations for which the value of said function is greater than or equal to said threshold T.

56. An address module for a computer memory system having a set of data storage means, said address module for receiving a reference address, said reference address being a sequence of bits, said address module comprising:

reference address means for storing said reference address;

selected coordinate means for storing a set of bit positions for each data storage means, said bit positions hereinafter called the selected coordinates for the corresponding data storage means;

assigned value means for storing a set of bits, hereinafter called a vector of assigned value bits, associated with the selected coordinates for each data storage means;

exclusive-OR means for performing a logical exclusive OR between vectors output from said reference address means and vectors output from said assigned value means;

AND means for performing a logical AND of the vector output from said exclusive-OR means and the vector output from said selected coordinate means; and

zero test means for testing the vectors output from said AND means, and for providing an identification signal to said computer memory system for each vector from said AND means when all bits in a vector from said AND means are zeros, thereby identifying which data storage means are to be accessed for storing or retrieving information in response to said reference address.

57. An address module for a computer memory system having a set of data storage means, said address module for receiving a reference address, said reference address being a sequence of bits, said address module comprising:

tag counter means for providing a sequence of output signals corresponding to each data storage means;

hard address means coupled to receive said output signals from said tag counter means for storing a set of bit positions for each data storage means, said bit positions hereinafter called the selected coordinates for the corresponding data storage means, said hard address means also for storing a set of bits, hereinafter called assigned value bits, associated with said selected coordinates for each data storage means; and

logic means for storing said reference address as a sequence of bits, for comparing said assigned value bits with corresponding bits from said reference address for said selected coordinates for each data storage means, and for providing an output logic signal to said computer memory system when all of said compared bits for a data storage means match.