Abstract:
A miss detector for a content addressable memory has plural input lines connected across points with the memory output lines. The detector input lines are disposed in pairs of true and false lines, and gating circuitry gates together the true and false pairs to provide a miss error message.

Description:
FIELD OF THE INVENTION 
     The present invention relates to a miss detector for a content addressable memory. 
     BACKGROUND OF THE INVENTION 
     Content addressable memories find wide application for example in cache memories. 
     In operation, address information, which may truncated, can be stored in the CAM. At a later stage, information is applied to the CAM and where a match occurs between the applied information and the stored information a so-called “hit” occurs defined by a logic  1  occurring on an output line from the CAM corresponding to the bit position at which the hit occurred. 
     Where there is no match, no hit occurs, and positive indication of this situation is required. 
     SUMMARY OF THE INVENTION 
     According to a first aspect of the present invention there is provided a miss detector for a CAM having m output lines, said detector having n pairs of input terminals, wherein the binary equivalent of m has n digits, each input pair comprising a true input terminal and a false input terminal, circuitry connecting each output line either to a true or a false input terminal of every pair, and gating circuitry coupled to each pair, said gating circuitry having an output indicative of a miss on said output lines of said CAM. 
     According to a second aspect of the present invention there is provided a miss detector for a CAM having m output lines numbered 0 to (m−1), the detector having n pairs of input terminals, each pair comprising a true and a false input terminal, each pair corresponding to a bit position in the binary equivalent of m, connecting circuitry connecting each output line to a true or false input terminal of each pair of input terminals in conformity with the binary equivalent of the number of said output lines, index circuitry coupled to the true input terminals of each pair and having an index output corresponding to the binary equivalent of an output line when a hit occurs on said output line, and gating circuitry having inputs coupled to each pair, said gating circuitry having an output indicative of a miss. 
     Preferably said gating circuitry comprises a two-input OR gate connected to each pair of input terminals. 
     Advantageously said gating circuitry further comprises an n-input output OR gate having an input from each OR gate output. 
     Conveniently said connecting circuitry comprises a respective pull-up device connected to each input terminal and a pull-down device connected to each input terminal wherein said pull-down device has a control terminal connected to said CAM output lines. 
     Advantageously said connecting circuitry further comprises a respective inverter connected between said pull-up/pull-down devices and said input terminals. 
     Preferably said pull-up device comprises a p FET connected to conduct and said pull-down device comprises plural n FETs, each n FET having a gate connected to a CAM output line. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings in which: 
     FIG. 1 shows a block schematic diagram of a miss detector in accordance with the present invention, having four output lines and; 
     FIG. 2 shows a partial block schematic diagram of a miss detector for a CAM having ten output lines. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the various figures like reference numerals refer to like parts. 
     Referring first to FIG. 1 a CAM  10  has four output lines  20 - 23  connecting respective cells of the CAM to a random access memory  11 . A miss circuit comprises two pairs of input lines  30 , 31 ; 32 , 33 . As shown schematically, the input lines  30 , 31 ; 32 , 33  run perpendicular to the output lines  20 - 23 . Each of the input lines has a corresponding pull-up p FET  40 - 43 , the pull-up transistors being arranged to conduct. As shown, conduction is ensured by connecting the pull-up transistor gates to earth although it will be clear to those skilled in the art that such a permanent connection is not essential to the performance of the invention. At certain cross points of the output lines of the CAM with the input lines of the detector, switches are provided in the form of pull-down n FETs  50 - 57  as will later be described. 
     Each of the individual lines  30 , 31 ; 32 , 33  is connected to a respective inverter  60 - 63 . The outputs of the inverters of each bit line pair are connected to the inputs of respective two two-input OR gates  70 ,  71  and the outputs of the OR gates  70 ,  71  are connected to a two input output OR gate  80 . 
     In the illustrated embodiment there are four output lines  20 - 23  and the binary representation of the number four requires two digits. Hence there are two bit line pairs  30 , 31 ;  32 , 33 . Of the first bit line pair  30 , 31  the first bit line  30  is designated as “false” and the second bit line  31  is designated as “true”. 
     Likewise, the second pair  32 , 33  has a first line  32  which is “false” and a second  33  which is “true”. The four output lines  20 - 23  are designated respectively  0 , 1 , 2 , 3  and connections are made to the corresponding input lines  30 - 33  according to the binary equivalent of the number of the line. Thus, line  20  designated as “0” (binary equivalent of 0,0) so that this line is connected by pull-down transistors  50  and  55  to the “false” input lines  30 , 32 . Output line  21  is designated as “1” and is thus connected to the true line  31  of the first pair  30 , 31  by pull-down  52  and to the false line  32  of the second pair  32 , 33 . Similarly line  22  (binary 1,0) is connected to lines  33  and  30 , and line  23  (binary 1,1) is connected to lines  33  and  31 . 
     The detector further has register lines  90 , 91  connected to the outputs of the inverters  61  and  63  respectively of the “true” lines  31 , 33 . 
     In operation, when the CAM  10  has a hit on, for example, the second line  21  (binary 0,1) input line  32  will be pulled down by the action of transistor  54  and the input line  31  will be pulled down by the action of transistor  52 . However, high potentials are applied via the pull-up transistors on lines  30  and  33 . The result is that the register lines  90 , 91  give an output of 01 which corresponds to the binary equivalent of line  21 . In this condition, the output OR gate  80  receives a single  1  at each input, and thus produces a logical  1  indicating that the register line output is valid. 
     If however there are no hits then the fact that each of the output lines is connected to both pairs of input lines of the detector means that inevitably all of the input line pairs will simultaneously produce logic zeros at the inputs to all of the OR gates. This means that no inputs to the OR gates  70 ,  71  will be at logic 1 giving rise to inputs to the output OR gate  80  of logic 0 and an output from the circuit output  81  of logic 0 indicative that a miss has occurred. In this situation the index outputs (which will be at 0,0) must be disregarded. 
     Referring now to FIG. 2, the figurative connections are shown between ten input lines  100 - 109  and the miss detector. 
     In this case there are four input line pairs  200 - 203  each comprising a true (left hand) and false (right hand) line. Again, the output lines  100 - 109  are connected to the input lines at the cross points via pull-down devices such as n FETs and the input lines are pulled up by pull-up devices such as p FETs. The cross point connections are figuratively shown by the symbol “X”. It will be seen that line  100  is connected to all of the four false lines (binary 0,0,0,0) whereas for example line  104  is connected to all of the false lines except in the third from right pair  202  (binary 0,1,0,0). 
     Comparison with FIG. 1 shows that similar inverters  160  are connected to each input line, and that each pair of inverters is connected to a respective two-input OR gate  170 . The OR gate outputs are connected to a four-input output OR gate  180  having an output  181  for providing a miss output. The outputs of each true inverter form an index output. 
     Operation of this circuit is equivalent to that discussed with respect to FIG.  1 . 
     If it is desired to produce an output of logic 1 indicative of a miss, the output or gate  80 ,  180  is replaced by an equivalent NAND gate.