Method and apparatus for adding or subtracting in an associative memory

Claim 3

The method of claim 1 further including the steps of: setting, before the sequential steps, a special bit in each memory word to be added to or subtracted from; unmasking during said unmasking step of a first cycle a set entry special bit for subtraction or a reset entry special bit for addition; and wherein said interrogating and writing steps include interrogating and writing with said entry special bit.

Claim 4

The method of claim 2 further including, after completion of addition or subtraction, the step of: interrogating the special bits for all memory words with the true value of an unmasked set entry bit so as to detect words containing an overflow condition.

Claim 9

An associative memory apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for subtracting a number from all selected words in memory, each selected by having a set special bit comprising: a control unit means operative to establish, as initial conditions, 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit positions of said entry and mask register means and thereafter to generate a plurality of sequential control signals in each cycle; first means operative, in each cycle, in response to a first control signal to apply a reset signal to the mask register means special bit and lowest order significant bit that was not previously unmasked so as to unmask a field of bits in said entry register, and operative, in each cycle after the first, to reset the entry bit which was unmasked during the previous cycle; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the true value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the complement of the unmasked entry field into all memory words having a set match indicator.

Claim 10

An associative memory apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for subtracting a number from all selected words in memory, each selected by having a set special bit comprising: a control unit means operative to establish, as initial conditions, 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit positions of said entry and mask register means and thereafter to generate a plurality of sequential control signals in each cycle; first means operative, in each cycle, in response to a first control signal to apply a reset signal to the mask register means special bit and lowest order significant bit that was not previously unmasked so as to unmask a field of bits in said entry register, and operative, in each cycle after the first, to reset the entry bit which was unmasked during the previous cycle; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the true value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the complement of the unmasked entry field into all memory words having a set match indicator.

Claim 11

The apparatus of claim 6 further including; inhibit means connected to inhibit operation of said control means, and connecting means connecting said first means to said inhibit means, said connecting means operative, in response to a first control signal occurring in a cycle after the highest order entry bit is unmasked, to inhibit operation of said control unit.

Claim 12

The apparatus of claim 7 further including; overflow sequential control means for generating a plurality of sequential control overflow signals, fifth means connected, in response to a first overflow signal, to set all bits in said mask register means, sixth means connected, in response to a second overflow signal to set all match indicators and to reset the mask register means special bit to 0, and seventh means connected to said third means and operative, in response to a third overflow signaL, to interrogate all memory words with the unmasked entry register special bit so as to detect all words exhibiting an overflow condition.

Claim 13

An associative memory addition apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for adding a number to all selected words in memory, each selected by having a set special bit, comprising: a control unit means operative to establish, as initial conditions 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit position of said mask register means and to establish a 0 in said entry special bit and thereafter to generate a plurality of sequential control signals in each cycle, first means operative, in each cycle, in response to a control signal to apply a reset signal to the mask register means special bit and lowest order significant bit that was not previously unmasked so as to unmask a field of bits in said entry register, and operative, in each cycle after the first, to reset the entry bit which was unmasked during the previous cycle; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the complement value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the true value of the unmasked entry field into all memory words having a set match indicator.

Claim 14

An associative memory addition apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for adding a number to all selected words in memory, each selected by having a set special bit, comprising: a control unit means operative to establish, as initial conditions 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit position of said mask register means and to establish a 0 in said entry special bit and thereafter to generate a plurality of sequential control signals in each cycle, first means operative, in each cycle, in response to a control signal to apply a reset signal to the mask register means special bit and lowest order significant bit that was not previously unmasked so as to unmask a field of bits in said entry register, and operative, in each cycle after the first, to reset the entry bit which was unmasked during the previous cycle; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the complement value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the true value of the unmasked entry field into all memory words having a set match indicator.

Claim 15

The apparatus of claim 9 further including: inhibit means connected to inhibit operation of said control means, and connecting means connecting said first means to said inhibit means, said connecting means operative, in response to a first control signal occurring in a cycle after the highest order entry bit is unmasked, to inhibit operation of said control unit.

Claim 16

The apparatus of claim 10 further including: overflow sequential control means for generating a plurality of sequential control overflow signals, fifth means connected, in response to a first overflow signal, to set all bits in said mask register means, sixth means connected, in response to a second overflow signal to set all match indicators and to reset the mask register means special bit to 0, and seventh means connected to said third means and operative, in response to a third overflow signal, to interrogate all memory words with the unmasked entry register special bit so as to detect all words exhibiting an overflow condition.

Claim 17

An associative memory apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for subtracting a number from all selected words in memory, each selected by having a set special bit comprising: a control unit means operative to establish, as initial conditions, 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit positions of said entry and mask register means and thereafter to generate a plurality of sequential control signals in each cycle; gate means including a plurality of backup gates, one for each of said plurality of ordered bit positions, including means connecting the output from each of said backup register means ordered positions to a corresponding one of said backup gates, including means connecting the reset output of each backup gate to the backup gate of the adjacent higher order position, to the reset input of the adjacent higher order position, to the reset input of the adjacent higher order mask register means, and to the reset input of the entry register means bit of the same order, and including means connecting a control signal from said control unit to the mask register means special bit and lowest-order bit and to the lowest order backup gate whereby, in each cycle, the lowest order significant entry register means bit which was not previously unmasked is unmasked and whereby, in each cycle after the first, the entry bit which was unmasked during the previous cycle is reset; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the true value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the complement of the unmasked entry field into all memory words having a set match indicator.

Claim 18

An associative memory apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for subtracting a number from all selected words in memory, each selected by having a set special bit comprising: a control unit means operative to establish, as initial conditions, 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit positions of said entry and mask register means and thereafter to generate a plurality of sequential control signals in each cycle; gate means including a plurality of backup gates, one for each of said plurality of ordered bit positions, including means connecting the output from each of said backup register means ordered positions to a corresponding one of said backup gates, including means connecting the reset output of each backup gate to the backup gate of the adjacent higher order position, to the reset input of the adjacent higher order position, to the reset input of the adjacent higher order mask register means, and to the reset input of the entry register means bit of the same order, and including means connecting a control signal from said control unit to the mask register means special bit and lowest-order bit and to the lowest order backup gate whereby, in each cycle, the lowest order significant entry register means bit which was not previously unmasked is unmasked and whereby, in each cycle after the first, the entry bit which was unmasked during the previous cycle is reset; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the true value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the complement of the unmasked entry field into all memory words having a set match indicator.

Claim 19

An associative memory addition apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for adding a number to all selected words in memory, each selected by having a set special bit, comprising: a control unit means operative to establish, as initial conditions 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit position of said mask register means and to establish a 0 in said entry special bit and thereafter to generate a plurality of sequential control signals in each cycle; gate means including a plurality of backup gates, one for each of said plurality of ordered bit positions, including means connecting the output from each of said backup register means ordered positions to a corresponding one of said backup gates, including means connecting the reset output of each backup gate to the backup gate of the adjacent higher order position, to the reset input of the adjacent higher order mask register means, and to the reset input of the entry register means bit of the same order, and including means connecting a control signal from said control unit to the mask register meAns special bit and lowest-order bit and to the lowest order backup gate whereby, in each cycle, the lowest order significant entry register means bit which was not previously unmasked is unmasked and whereby, in each cycle after the first, the entry bit which was unmasked during the previous cycle is reset; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the complement value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the true value of the unmasked entry field into all memory words having a set match indicator.

Claim 20

An associative memory addition apparatus including a memory containing a plurality of words each having a special bit and a plurality of ordered bit positions, entry register means containing the same special bit and plurality of ordered bit positions, mask register means containing the same special bit and plurality of ordered bit positions for controlling which field of bits in said entry register means is gated to the same field of bits in said memory words, backup register means selectively connectable to said entry and mask register means including the same plurality of bit positions, word sense and selection circuitry including match indicators for detecting which words compare during an interrogation step and for selecting which words to write into during a write step, the improvement for adding a number to all selected words in memory, each selected by having a set special bit, comprising: a control unit means operative to establish, as initial conditions 1''s in all said ordered bit positions of said entry, mask and backup register means and in said special bit position of said mask register means and to establish a 0 in said entry special bit and thereafter to generate a plurality of sequential control signals in each cycle; gate means including a plurality of backup gates, one for each of said plurality of ordered bit positions, including means connecting the output from each of said backup register means ordered positions to a corresponding one of said backup gates, including means connecting the reset output of each backup gate to the backup gate of the adjacent higher order position, to the reset input of the adjacent higher order mask register means, and to the reset input of the entry register means bit of the same order, and including means connecting a control signal from said control unit to the mask register meAns special bit and lowest-order bit and to the lowest order backup gate whereby, in each cycle, the lowest order significant entry register means bit which was not previously unmasked is unmasked and whereby, in each cycle after the first, the entry bit which was unmasked during the previous cycle is reset; second means operative, in each cycle, in response to a control signal to condition all match indicators; third means operative, in each cycle, in response to a subsequent control signal to interrogate all memory words with the complement value of all unmasked entry register bits and thereby set a match indicator for each memory word having a field which compares with the unmasked entry field; and fourth means operative, in each cycle, in response to a control signal to write the true value of the unmasked entry field into all memory words having a set match indicator.