Word-organized, content-addressable memory

• US 4,296,475 A
• Filed: 12/19/1978
• Issued: 10/20/1981
• Est. Priority Date: 12/19/1978
• Status: Expired due to Term

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Salters, Roelof H. W., Nederlof, Leendert
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Heckler, Thomas M.
• Application Number:
  US05/970,883
• Time in Patent Office: 1,036 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 365/49, 365/200, 235/306
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

A word-organized, content-addressable memory comprises per word location a validity indicator, having a position "valid" and a position "invalid", and a correspondence indicator. The following functions can be performed:

(a) associative searching and reading of the content of a word for which correspondence occurs (R);

(b) reading the next word in sequence of words for which correspondence occurs (SR);

(c) loading a mask word in the mask register (LM);

(d) selective invalidating of the content of one or more predetermined word locations (CPM);

(e) writing in an empty word location, i.e. a location not having a valid data content (WFP);

(f) writing data in a number of selective bit positions of one or more words for which correspondence occurs (WP).

There is also provided a mask register whose data activate the comparisons as well as the outputting of data for which no comparison has taken place.

As a result of such an organization, a very versatile use is realized for a comparatively inexpensive memory. In a memory of this kind, constructed as an integrated circuit, moreover, only a small number of connections are required per number of bit positions.

Claims

1. A content-addressable memory having a matrix of bit cells for accommodating a plurality of multibit words on an integrated circuit, said integrated circuit comprising:

a first input for inputting a key word, a second input for inputting a mask word for the selective deactivation of a part of the input key word by masking, and an output for outputting a data word stored in a word location;

first means for comparing a non-masked part of a key word with a corresponding part of a data word stored in a word location;

second means for indicating, for each word location, correspondence detected by said first means and for activating said output for outputting data from a word location for which correspondence occurs, wherein said second means comprise a validity indicator for each word location, having a state "valid" and a state "invalid", for selectively indicating the validity of the word stored at this location, and for each word a correspondence indicator, having a state "correspondence" and a state "non correspondence", said validity indicator acting as a bit position of the associated word location, so that when the memory is addressed as regards valid word location content, said state "invalid" blocks the associated correspondence indicator for the effective supply of a signal "correspondence", each validity indicator comprising a switch input for selectively setting the indicator, by an externally applied switch signal, to the one or to the other state;

third means for clearing a part of the memory and for switching, under the control of a correspondence signal from the correspondence indicator of one or more word locations, the validity indicator of said one or more word locations to the state "invalid";

a multiple match resolver for forming, in the case of simultaneous appearance of at least two active "correspondence" signals, a sequence for accessing the associated word locations, wherein for the writing of a data word in a word location, the bit position corresponding to the data of the validity indicator remains exclusively unmasked by the mask word in order to control, in the position "invalid", the associated correspondence indicator so as to form a position "correspondence", after which the multiple match resolver controls a write enable signal for a single word location thus provided with a correspondence signal;

fourth means for switching, under the control of a sequence signal from said multiple match resolver, the correspondence indicator for a word location indicated by said sequence signal to the position "non-correspondence" in order to apply, when a read command signal is received, the data of a word location to said output only once.

2. A memory as claimed in claim 1, wherein said integrated circuit has a mask register for a mask word whose non-masking data location(s) bit-wise activate said first means and whose masking data location(s) bit-wise activate said output wherein said first input, said second input, said output, and an input for inputting a data word to be stored in a word location are connected together, via pins which are common for each bit position, to a data bus line.

4. A content-addressable memory as claimed in claims 2 or 3 further including a separate integrated circuit for the storage of n data words of m bits plus an associated mask word of corresponding length, said separate circuit comprising m connections to said bus, n connections each associated with a separate word serving for a correspondence signal for each word, power supply terminals as external connections, at least three connections for receiving mode selection signals in order to activate a decoder in the circuit and a connection for receiving a clock signal.

5. The content-addressable memory of claims 2 or 3 further including a separate integrated circuit for the storage of n data words of m bits plus an associated mask word of corresponding length, said separate circuit comprising m connections to said bus, n connections which are each associated with a separate word and each serving for a correspondence signal for each word, power supply terminals as external connections, at least three connections for receiving mode selection signals in order to activate a decoder in the circuit and a connecton for receiving a clock signal;

wherein said n connections are suitable for transporting a correspondence signal and a pointer signal to said circuit, said n connections comprising a unidirectional element, provided with a control terminal for alternatively determining a conducting direction therein, the control terminals of the n unidirectional elements all being interconnected in order to form together a single further external connection of said circuit.

6. The content-addressable memory of claims 2 or 3 further including fifth means for writing, under the control of an effective correspondence signal from a correspondence indicator, predetermined data for the bit positions of relevant word locations which are not masked by the prevailing mask word.

7. The content-addressable memory of claim 5 further including fifth means for writing, under the control of an effective correspondence signal from a correspondence indicator, predetermined data for the bit positions of the relevant word locations which are not masked by the prevailing mask word.

8. The content-addressable memory of claim 7 wherein said fifth means are furthermore suitable for writing, under the control of simultaneously appearing effective correspondence signals from the correspondence indicators of at least two word locations, predetermined data for the bit positions of relevant word locations which are not masked by the mask word then prevailing.

9. The content-addressable memory of claim 6 wherein said fifth means are furthermore suitable for writing, under the control of simultaneously appearing effective correspondence signals from the correspondence indicators of at least two word locations, predetermined data for the bit positions of relevant word locations which are not masked by the mask word then prevailing.

3. A content addressable memory having a matrix of bit cells for accommodating a plurality of multibit words on an integrated circuit, said integrated circuit comprising:

a first input for inputting a key word, a second input for inputting a mask word for the selective deactivation of a part of the input key word by masking, an output for outputting a data word stored in a word location;

first means for comparing a non-masked part of a key word with a corresponding part of a data word stored in a word location;

second means for indicating, for each word location, correspondence detected by said first means and for activating said output for outputting data from a word location for which correspondence occurs, wherein said second means comprise a validity indicator for each word location, having a state "valid" and a state "invalid", for selectively indicating the validity of the word stored at this location, and for each word a correspondence indicator, having a state "correspondence" and a state "non-correspondence", said validity indicator acting as a bit position of the associated word location, so that when the memory is addressed as regards valid word location content, said state "invalid" blocks the associated correspondence indicator for the effective supply of a signal "correspondence", each validity indicator comprising a switch input for selectively setting the indicator, by an externally applied switch signal, to the one or to the other state;

third means for clearing a part of the memory and for switching, under the control of a correspondence signal from the correspondence indicator of one or more word locations, the validity indicator of said one or more word locations to the state "invalid";

a multiple match resolver for forming, in the case of simultaneous appearance of at least two active "correspondence" signals, sequence for accessing the associated word locations, wherein for the writing of a data word in a word location, exclusively the bit position corresponding to the data of the validity indicator remains unmasked by the mask word in order to control, in the position "invalid", the associated correspondence indicator so as to form a position "correspondence", after which the multiple match resolver controls the write enable signal for a single word location thus provided with a correspondence signal;

wherein furthermore said integrated circuit has a mask register for a mask word whose non-masking data location(s) bit-wise activate said first means and whose masking data location(s) bit wise activate said output, wherein said first input, said second input, said output, and an input for inputting a data word to be stored in a word location are connected together, via pins of said integrated circuit which are common for each bit position, to a data bus line.