Abstract:
Content addressable memories are disclosed that provide at least three states and are based on existing binary CAM devices. A higher order CAM having at least three states comprises a binary CAM having two binary bits; and a logic circuit to configure the two binary bits as a single CAM bit having said at least three states. The three states include a don&#39;t care state, a logic 0 state and a logic 1 state. The logic circuit may be embodied as two OR gates. The first match search (MS) input and a first wild card (WC) input of the higher order CAM are applied to inputs of the two OR gates and the outputs of the two OR gates are applied to the wild card (WC) inputs of the binary CAM. The match search (MS) inputs of the binary CAM are tied to a power supply voltage.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates generally to content addressable memories (CAMs), and more particularly, to CAMs based on a binary CAM and having bits with at least three states.  
       BACKGROUND OF THE INVENTION  
       [0002]     Content addressable memories, often referred to as associative memories, have memory locations that are identified by the contents of the location or a portion thereof. A CAM can be written to and read from like a traditional memory array, and can also be searched to identify one or more address locations that store a desired value. Generally, when in a search mode, a CAM will return an address containing a given search string (data pattern). A binary CAM is capable of storing information in two different logic states, namely, a binary “0” state or a binary “1” state. A ternary CAM cell provides a “don&#39;t care” logic state, in addition to the binary “0” and binary “1” states.  
         [0003]     Binary and ternary CAM cells are typically implemented using static random access memory (SRAM), dynamic RAM (DRAM), or non-volatile memory technologies. CAM cells based on SRAM technology have become increasingly popular, at least in part due to their relatively fast times for performing write and search operations.  
         [0004]     Increasingly, there is a need for three or four state CAMs that provide at least three states (logic 0, logic 1, and a don&#39;t care state). A further need exists for a hybrid CAM that includes at least one binary CAM bit and at least one higher order CAM bit, such as a ternary CAM bit. Yet another need exists for a three or four state CAM that uses existing binary CAMs without modifying the underlying binary CAM.  
       SUMMARY OF THE INVENTION  
       [0005]     Content addressable memories are disclosed that provide at least three states and are based on existing binary CAM devices. A higher order CAM having at least three states comprises a binary CAM having two binary bits; and a logic circuit to configure the two binary bits as a single CAM bit having said at least three states. The three states include a don&#39;t care state, a logic 0 state and a logic 1 state.  
         [0006]     In one implementation, the logic circuit may be embodied as two OR gates. The first match search (MS) input and a first wild card (WC) input of the higher order CAM are applied to inputs of the two OR gates and the outputs of the two OR gates are applied to the wild card (WC) inputs of the binary CAM. The match search (MS) inputs of the binary CAM are tied to a power supply voltage.  
         [0007]     A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]      FIG. 1  is a schematic block diagram of one column of a conventional binary CAM;  
         [0009]      FIG. 2  is a schematic block diagram of one column of an exemplary ternary CAM incorporating features of the present invention;  
         [0010]      FIG. 3  is a state table corresponding to the ternary CAM of  FIG. 2 ;  
         [0011]      FIG. 4  is a schematic block diagram of one column of an alternate ternary CAM incorporating features of the present invention;  
         [0012]      FIG. 5  is a state table corresponding to the ternary CAM of  FIG. 4 ; and  
         [0013]      FIG. 6  is a schematic block diagram of an exemplary hybrid CAM incorporating features of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0014]      FIG. 1  is a schematic block diagram of a column from a conventional binary CAM  100 . Typically, a binary CAM  100  is comprised of an array of CAM cells (not shown) where each row of the CAM array corresponds to a stored word. Each column is generally associated with a given bit. As shown in  FIG. 1 , each row of the array has an associated word line  150  that allows the row to be accessed (for a read or write operation) by activating the appropriate word line. In a write operation, data would be placed on a data line Dn for a given column. In a read operation, the binary CAM  100  places a data value on the output line Qn for a given column.  
         [0015]     In addition, each row has an associated match line  160  that is activated when the word stored in the corresponding row matches an applied input value during a search mode. Generally, the binary CAM  100  has match search inputs (MSn) and wild card inputs (WCn) for each column that allow the binary CAM  100  to be searched for words having an exact matching pattern or to search a subset of the bits using a mask, respectively. The wild card inputs are used to mask out corresponding bits in the match search string. For example, if a given bit in the wild card string is high, then the corresponding bit will not be compared. Typically, the binary CAM  100  has a priority encoder (not shown) that processes the match lines  160  and determines the first address in the binary CAM  100  that matches the search string.  
         [0016]     According to one aspect of the invention, a three or four state CAM, referred to herein as a higher order CAM, is achieved that uses existing binary CAMs without modifying the underlying binary CAM.  FIG. 2  is a schematic block diagram of a column of an exemplary ternary CAM  200  incorporating features of the present invention. As shown in  FIG. 2 , each column of the ternary CAM  200  comprises two columns (bits) of the binary CAM  100  shown in  FIG. 1 . It is noted that the binary CAM  210  may be embodied as any commercially available binary CAM that allows each bit in a given word to be selectively searched (i.e., provide per-bit wild cards).  
         [0017]     Generally, the ternary CAM  200  configures two bits of a binary CAM  210  to be a single ternary CAM bit with three or four states. Thus, the ternary CAM  200  has MS and WC inputs for the single ternary bit. A state table  300  for the ternary or four state CAM  200  is discussed further below in conjunction with  FIG. 3 . As shown in  FIG. 2 , the match search (MS) and wild card (WC) values for the ternary bit are applied through two OR gates  220 ,  230  to the WC 0  and WC 1  inputs of the binary CAM  210 . In addition, in the implementation shown in  FIG. 2 , the MS inputs of the binary CAM  210  are maintained at logic “0” (for example, by tying the MS inputs to V SS ) and the MS input to the second OR gate  230  is inverted.  
         [0018]      FIG. 3  is a state table  300  corresponding to the ternary CAM  200  of  FIG. 2 . As previously indicated, the ternary CAM  200  configures two bits of a binary CAM  210  to be a single ternary CAM bit with up to four states (logic “1”, “0”, “don&#39;t care” and “don&#39;t match”). It is noted that the “don&#39;t match” logic value is generally considered an invalid state for a ternary (three state) device.  
         [0019]     As shown in  FIG. 3 , where the MS inputs of the binary CAM  210  are maintained at logic “0”, in order to: (i) write a “don&#39;t care” logic value, a 0 must be written to the x column (D 0 ) and a 0 must be written to the y column (D 1 ); (ii) write a “0” logic value, a 0 must be written to the x column (D 0 ) and a 1 must be written to the y column (D 1 ); and (iii) write a “1” logic value, a 1 must be written to the x column (D 0 ) and a 0 must be written to the y column (D 1 ).  
         [0020]     Similarly, in a search mode, if it is desired to search for a logic “0”, a match should occur if there is a logic “0” or a “don&#39;t care” state. Since the “don&#39;t care” state is defined as values of 0 in both the x and y columns for the embodiment of  FIG. 2 , the x column of the CAM  200  should be searched for x columns (WC 0 ) having a value of 0 (which will return either a logic “0” or a “don&#39;t care” state). If it is desired to search for a logic “1”, a match should occur if there is a logic “1” or a “don&#39;t care” state. Thus, the y column of the CAM  200  should be searched for y columns (WC 1 ) having a value of 0 (which will return either a logic “1” or a “don&#39;t care” state). Generally, since the MS inputs of the binary CAM  210  are maintained at logic “0” for the embodiment of  FIG. 2 , and thus define the “don&#39;t care” condition as “00”, the CAM  200  is always searched for values of 0 in the appropriate column (x column for logic 0 and y column for logic 1).  
         [0021]     As previously indicated, the match search (MS) and wild card (WC) values for the ternary bit are applied through two OR gates  220 ,  230  to the WC 0  and WC 1  inputs of the binary CAM  210 , where the MS input to the second OR gate  230  is inverted.. Generally, the OR gates  220 ,  230 , together with the inverted input the second OR gate  230 , provide a column selection mechanism that defines whether column x or column y is searched for a value of 0. The output of the OR gate  220  or  230  that has a value of 0 will indicate the respective column to be searched (and the column associated with the OR gate  220  or  230  that has a value of 1 will not be searched). For example, as indicated above, if it is desired to search for a logic “1”, the y column of the CAM  200  should be searched for values of 0. This is implemented in the CAM  200  of  FIG. 2  by configuring the MS and WC inputs to the ternary CAM  200  to be logic 1 and logic 0, respectively, to ensure that a value of 0 appears at the output of only the OR gate  230 .  
         [0022]      FIG. 4  is a schematic block diagram of an alternative implementation of a column of a ternary CAM  400  incorporating features of the present invention. As shown in  FIG. 4 , each column of the ternary CAM  400  comprises two columns (bits) of the binary CAM  100  shown in  FIG. 1 .  FIG. 5  is a state table  500  corresponding to the ternary CAM  400  of  FIG. 4 . As shown in  FIG. 4 , the match search (MS) and wild card (WC) values for the ternary bit are applied through two OR gates  420 ,  430  to the WC inputs of the binary CAM  410 . In addition, in the implementation of  FIG. 4 , the MS inputs of the binary CAM  410  are maintained at logic “1” (for example, by tying the MS inputs to V DD ) and the MS input to the first OR gate  420  is inverted. The ternary CAM  400  is written and searched in a similar manner to the ternary CAM  200  of  FIG. 2 , using the logic table defined in  FIG. 5 .  
         [0023]      FIG. 6  is a schematic block diagram of a hybrid CAM  600  that configures a binary CAM  610  to operate as a binary, ternary or four state CAM. As shown in  FIG. 6 , the exemplary hybrid CAM  600  comprises a binary CAM  610 , such as the binary CAM  100  shown in  FIG. 1 , where two columns of the binary CAM  610  form a first ternary bit  615 - 1 , two columns of the binary CAM  610  form a second ternary bit  615 - 2  and one column of the binary CAM  610  form a binary bit  620 . In this manner, if a given implementation requires ternary functionality, the ternary bits  615  may be employed as needed and if a given implementation does not require any ternary functionality, only binary bits  620  may be employed.  
         [0024]     As shown in  FIG. 6 , each ternary bit  615  has an associated match search (MS) value and wild card (WC) value that are applied through two OR gates  620 ,  630  to the WC inputs of the corresponding binary CAM  610 , in a similar manner to  FIG. 2 . In the implementation of  FIG. 6 , the MS inputs of the binary CAMs  610  are maintained at logic “0” (for example, by tying the MS inputs to V SS ) and the MS input to the second OR gate  630  is inverted. It is noted that an alternate hybrid CAM  600  can be implemented using the ternary CAMs of  FIG. 4 , where  6 , the MS inputs of the binary CAMs  610  are maintained at logic “1” (for example, by tying the MS inputs to V DD ) and the MS input to the first OR gate  620  is inverted, or a combination of the embodiments shown in  FIGS. 2 and 4  in a single hybrid CAM  600 .  
         [0025]     It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.