Content addressable memory

Claim 2

A content addressable memory having a plurality of substantially identical content addressable memory units, the units in use storing data and producing and storing status digits indicating the occurrence of matches to an input key code wherever they occur amongst the data stored therein, means for applying to all of the units substantially simultaneously an input key code to be matched, and gating and storing means responsive to the status digit outputs from the memory units to produce and store higher level status digits and a highest level single status digit indicating the presence or absence of a match to the input key code in the entire memory, the status digits and their storage being such that the location in the memory of all matches to an input key code can be derived from them.

Claim 3

A memory according to claim 1 in which each memory unit is a single integrated circuit having input means for the input key code and means for producing the status digit output indicating whether or not matches to the input key code occur in the data stored in the particular memory unit.

Claim 4

A memory according to claim 1 in which the gating means includes a plurality of levels of OR-gates, the outputs of the gates of one level forming the inputs of the gates of the next higher level, and the outputs of the gates of the different levels also being applied to the storing means to record therein status digits corresponding to the different levels of gates.

Claim 5

A content addressable memory including a plurality of substantially identical memory units each having input means for an input group of digits to be matched by the data stored in the particular unit and producing a status digit output indicating whether or not a match for the input group has been found, means for applying a key code including at least one input group to the input means of each unit, logical combining means responsive to the status digit output of each unit to produce a single status indicating whether or not the input key code is matched by the data stored anywhere in the memory, and storage means for the logically combined status digit outputs, each memory unit including a plurality of storage elements accessible in blocks, each block including the same number of elements in a plurality of equal groups, addressing means for selecting a block of elements and reading therefrom the data stored in it, comparator means having a plurality of data bit comparators respectively corresponding to the storage elements in a block, the comparators being in groups each of the same number as the digits in the input group, each comparator having first and second inputs and producing a data bit match indication as to whether or not the data bits applied to the two inputs are the same, the first inputs being connected to receive signals from the selected block of elements and the second inputs of each group of comparators being connected to receive from the input means the input group of digits, assesement means responsive to the match indications from the comparators group by group to produce a first level status output for each group indicating whether or not the input group matches the data from the storage elements of the corresponding group of the selected block, logic means for combining the status outputs to produce one or more higher levels of status output, finally producing the status digit output, and storage means for storing the status outputs of all levels produced in the unit whereby the stored status outputs enable the address in the memory of any matches to the input key code to be derived.

Claim 6

A content addressable memory including a plurality of substantially identical memory units each having input means for an input group of digits to be matched by the data stored in the particular unit and producing a status digit output indicating whether or not a match for the input group has been found, means for applying a key code including at least one input group to the input means of each unit, logical combining means responsive to the status digit output of each unit to produce a single status indicating whether or not the input key code is matched by the data stored anywhere in the memory, and storage means for the logically combined status digit outputs, each memory unit including a plurality of storage elements accessible in blocks, each block including the same number of elements in a plurality of equal groups, addressing means for selecting a block of elements and reading therefrom the data stored in it, comparator means having a plurality of data bit comparators respectively corresponding to the storage elements in a block, the comparators being in groups each of the same number as the digits in the input group, each comparator having first and second inputs and producing a data bit match indication as to whether or not the data bits applied to the two inputs are the same, the first inputs being connected to receive signals from the selected block of elements and the second inputs of each group of comparators being connected to receive from the input means the input group of digits, assesement means responsive to the match indications from the comparators group by group to produce a first level status output for each group indicating whether or not the input group matches the data from the storage elements of the corresponding group of the selected block, logic means for combining the status outputs to produce one or more higher levels of status output, finally producing the status digit output, and storage means for storing the status outputs of all levels produced in the unit whereby the stored status outputs enable the address in the memory of any matches to the input key code to be derived.

Claim 7

A memory according to claim 4 wherein the assessment means includes inputs for mask data indicating which, if any, digits of a group can be ignored in the matching of the input group to the stored data, and arrangements of logic gates responsive to the mask data and the match indications from the comparators to produce the first level status outputs.

Claim 8

A memory according to claim 4 wherein the assessment means is responsive to a further input to the memory indicating the number of digit matches required in a group for a group of stored data to be a match to the input group so as to produce the first level status outputs in response to the bit match indications taking into consideration the required number of digit matches as indicated by the further input.

Claim 9

A memory according to claim 4 for an input key code including more than one input group including means for applying the input groups in sequence to all of the units and means for combining the resulting stored status outputs from all of the units to provide an indication of the presence or absence of a match to the entire input key code in the memory.

Claim 10

A memory according to any of claims 4 wherein each unit includes means for producing a further output when only one match is found to part or all of an input key code after a search of any part or all of the memory contained in the unit.

Claim 11

A memory according to claim 8 including means for logically combining the further outputs of the units to produce a single output from the memory indicating whether or not only one match has been found to part or all of an input key code.

Claim 12

A memory according to claim 9 for an input key code including more than one input group, the memory including means for terminating a search, before the entire input key code has been applied to the units, in response to the generation of the single output indicating that only one match has been found in the entire memory to the part of the input key code so far applied, the terminating means also enabling the output of the address of the only one match found.

Claim 13

A memory according to any of claims 4 including means for counting the number of matches found to part or all of an input and for producing a particular output when only one match has been found after a search of any part or all of the entire memory.

Claim 14

A memory according to any of claims 4 wherein each memory unit is made in the form of a single integrated circuit.

Claim 15

A memory according to any of claims 4 wherein in each memory unit at least part of the storage means for storing the status outputs of all levels produced in the unit are of the same type as the storage elements used to store data, and the addressing means for the storage elements can be used in accessing the storage means for storing the status outputs.

Claim 16

A memory according to any of claims 4 wherein an input group of digits consists of 8 binary digits.

Claim 17

A memory according to claim 14 wherein each memory unit includes 32K bytes of storage elements functionally arranged in 512 rows and columns, and a block of storage elements comprises a row of 512 elements.