Determining distances between vectors

Abstract

In-memory computing circuits can be used to determine distances between vectors. Such circuits can be used for machine learning applications. Examples include obtaining at least one dimension of a query vector wherein the dimension includes one or more bits and comparing respective bits of the dimension to corresponding bits of at least one dimension of a reference vector. This obtains a control signal dependent upon whether the bits of the dimension of the query vector are the same as corresponding bits of the dimension of the reference vector. The control signal can then be used to control a pulse modifying circuit such that a modification applied to a pulse signal is dependent upon whether the bits of the dimension of the query vector are the same as corresponding bits of the dimension of the reference vector.

I claim: 
     
       1. An apparatus, comprising:
 at least one processor; and 
 at least one memory storing instructions that, when executed with the at least one processor, cause the apparatus to perform: 
 obtaining at least one dimension of a query vector wherein the dimension comprises one or more bits; 
 comparing respective one or more bits of the at least one dimension of the query vector to corresponding one or more bits of at least one dimension of a reference vector to obtain a control signal dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; 
 using the control signal to control a pulse modifying circuit such that a modification applied to an input pulse signal to form an output pulse signal with the pulse modifying circuit is dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; and 
 determining, using the output pulse signal, a distance between the query vector and the reference vector based on modifications to the input pulse signal applied with the pulse modifying circuit that forms the output pulse signal. 
 
     
     
       2. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to perform:
 comparing a plurality of dimensions of the query vector to a plurality of dimensions of the reference vector to obtain a corresponding plurality of control signals; and 
 using the plurality of control signals to control the pulse modifying circuit so that a plurality of modifications are applied to the input pulse signal to form the output pulse signal. 
 
     
     
       3. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to apply different magnitudes of modifications to the input pulse signal corresponding to different bits of the dimensions of the query and reference vectors. 
     
     
       4. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to apply a same magnitude of modifications to the input pulse signal corresponding to different bits of the dimensions of the query and reference vectors. 
     
     
       5. An apparatus as claimed in  claim 3  wherein the instructions, when executed with the at least one processor, cause the apparatus to cause a magnitude of the modifications applied to the input pulse signal to control a pulse width of pulses that result in the output pulse signal. 
     
     
       6. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to pass a pulse signal, initially formed using the input pulse signal, through the pulse modifying circuit a plurality of times to form the output pulse signal. 
     
     
       7. An apparatus as claimed in  claim 1  wherein the pulse modifying circuit comprises at least one of a pulse shrinking circuit or a pulse stretching circuit. 
     
     
       8. An apparatus as claimed in  claim 1  wherein the pulse modifying circuit comprises a transistor comprising a resistance such that a magnitude of a modification applied with the pulse modifying circuit is dependent upon a value of the resistance. 
     
     
       9. An apparatus as claimed in  claim 1  wherein the pulse modifying circuit comprises a first inverter and a second inverter and one or more resistors such that a magnitude of a modification applied with a pulse modifying circuit is dependent upon a number of inverters and resistors connected within a module of the pulse modifying circuit. 
     
     
       10. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to perform:
 comparing a plurality of bits of the query vector to a plurality of bits of a plurality of corresponding reference vectors to obtain a plurality of individual control signals for individual ones of the plurality of corresponding reference vectors; 
 using the plurality of individual control signals to control a plurality of pulse modifying circuits to form a plurality of output pulse signals; and 
 determining a plurality of individual distances based on the plurality of output pulse signals; and 
 producing a result, indicating a reference vector having a shortest distance between the reference vector and the query vector, based on comparison of the plurality of individual distances. 
 
     
     
       11. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to compare at least one bit of the query vector to a corresponding at least one bit of the reference vector using one or more XOR logic circuits. 
     
     
       12. An apparatus as claimed in  claim 1  wherein the instructions, when executed with the at least one processor, cause the apparatus to compare modified pulse signals corresponding to different reference vectors in order to determine the reference vector of the different reference vectors with a shortest distance to the query vector. 
     
     
       13. An apparatus as claimed in  claim 1  wherein the at least one processor and the at least one memory comprises in-memory computing circuits. 
     
     
       14. A method, comprising:
 obtaining at least one dimension of a query vector wherein the dimension comprises one or more bits; 
 comparing respective one or more bits of the at least one dimension of the query vector to corresponding one or more bits of at least one dimension of a reference vector to obtain a control signal dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; 
 using the control signal to control a pulse modifying circuit such that a modification applied to an input pulse signal to form an output pulse signal with the pulse modifying circuit is dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; and 
 determining, using the output pulse signal, a distance between the query vector and the reference vector based on modifications to the pulse signal applied with the pulse modifying circuit. 
 
     
     
       15. A non-transitory program storage device readable with an apparatus tangibly embodying a program of instructions executable with the apparatus to cause the apparatus to perform at least the following:
 obtaining at least one dimension of a query vector wherein the dimension comprises one or more bits; 
 comparing respective one or more bits of the at least one dimension of the query vector to corresponding one or more bits of at least one dimension of a reference vector to obtain a control signal dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; 
 using the control signal to control a pulse modifying circuit such that a modification applied to an input pulse signal to form an output pulse signal with the pulse modifying circuit is dependent upon whether the respective one or more bits of the at least one dimension of the query vector are the same as corresponding one or more bits of the at least one dimension of the reference vector; and 
 determining, using the output pulse signal, a distance between the query vector and the reference vector based on modifications to the input pulse signal applied with the pulse modifying circuit that forms the output pulse signal. 
 
     
     
       16. A method as claimed in  claim 12  further comprising:
 comparing a plurality of dimensions of the query vector to a plurality of dimensions of the reference vector to obtain a corresponding plurality of control signals; and 
 using the plurality of control signals to control the pulse modifying circuit so that a plurality of modifications are applied to the input pulse signal to form the output pulse signal. 
 
     
     
       17. A method as claimed in  claim 12  further comprising: passing a pulse signal, initially formed using the input pulse signal, through the pulse modifying circuit a plurality of times to form the output pulse signal. 
     
     
       18. A method as claimed in  claim 12  wherein the pulse modifying circuit comprises at least one of a pulse shrinking circuit or a pulse stretching circuit. 
     
     
       19. A method as claimed in  claim 12  further comprising:
 comparing a plurality of bits of the query vector to a plurality of bits of a plurality of corresponding reference vectors to obtain a plurality of individual control signals for individual ones of the plurality of corresponding reference vectors; 
 using the plurality of individual control signals to control a plurality of pulse modifying circuits to form a plurality of output pulse signals; and 
 determining a plurality of individual distances based on the plurality of output pulse signals; and 
 producing a result, indicating a reference vector having a shortest distance between the reference vector and the query vector, based on comparison of the plurality of individual distances. 
 
     
     
       20. A method as claimed in  claim 12  further comprising: comparing modified pulse signals corresponding to different reference vectors in order to determine the reference vector of the different reference vectors with a shortest distance to the query vector.