Method and apparatus for a sparse distributed memory system

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.ltoreq.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.sup.th accumulator, Ai, coupled to receive data from the i.sup.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.sup.th accumulator, Ai, receiving one integer from the i.sup.th counter for each activated hard memory location, thereby obtaining a value Vi in the i.sup.th accumulator, Ai.

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.

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.

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.

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.

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.

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.

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.ltoreq.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.

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.ltoreq.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.

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.

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.