Patent Publication Number: US-6341327-B1

Title: Content addressable memory addressable by redundant form input

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a content addressable memory suitable for use with redundant form input signals. 
     It is a goal of memory systems to fulfill requests for stored data with as little delay as possible. Often, the requesting agent cannot achieve forward progress without the requested information. This principle holds true for content addressable memories (“CAMs”). 
     However, increasingly, arithmetic operations are included as part of a memory operation. That is, a request for data defines one or more arithmetic operations whose result is to be applied to a memory as an address. Any time spent completing an arithmetic operation is delay introduced to a memory request that includes the arithmetic operation. Thus, it becomes a goal of memory systems to reduce the time required to perform any arithmetic operations included in a memory request. 
     FIG. 1 illustrates a traditional adder circuit. There, an addition performed on two multi-bit values X (X=X 0− X 3 ) and Y (Y=Y 0− Y 3 ) generates a multi-bit sum S (S=S 0− S 3 ) and a carry out C out . The traditional adder includes an internal carry chain wherein a carry from a first bit position i may affect the value of the sum at a second bit position i+1. Carries must propagate through the entire length of the adder before true results may be obtained therefrom. The internal carry chain causes the traditional adder to be slow. There is a need in the art for a memory system that improves the processing speed of memory requests that require mathematical preprocessing operations. 
     Redundant form adders are known to be faster than traditional adders. Shown in FIG. 2, a redundant form adder omits the internal carry chain that characterizes the traditional adder. Instead, for each bit position i of inputs X, Y and Z, the redundant form adder generates a multi-bit sum Ŝ i . The output Ŝ (Ŝ=Ŝ 0− Ŝ n ) is said to be in “redundant form” because two bits are used per bit position rather than a single bit to represent a sum result that may be more efficiently represented by only a single bit. To reduce the redundant form result Ŝ to non-redundant form, the two bits of each “bit position” Ŝ i  may be input to a traditional adder, such as the adder of FIG.  1 . 
     The redundant form adder provides significant processing advantages over traditional adder, particularly where a number of additions are performed in sequence. For a plural number of sequential adds, the traditional adder must complete the carry chain of each add before it may begin a subsequent add. However, redundant form processing permits quick additions to be performed. A carry chain may be omitted until a redundant form sum is obtained from the final addition. When the redundant form sum is obtained, it may be converted to non-redundant form by use of only a single carry chain. 
     No known memory system retrieves data based on redundant form input data. 
     Content addressable memories are known per se. A block diagram of a known CAM  100  is shown in FIG.  3 . The CAM  100  includes a plurality of registers  110  each of which stores data. When input data is applied to the CAM  100 , it generates an output identifying which registers, if any, store data having the same value as the input data. Typically, the CAM  110  generates an output signal having a one-bit flag per register position in the CAM. For example, the flag may be enabled if the register stores data that is equal to the input signal and disabled otherwise. 
     The CAM  100  contains match logic  120  associated with each register  110 . The match logic  120  performs a bit-by-bit comparison of the input data and the data stored in the register  110 . As shown in FIG. 4, it includes selection switches  130 - 160 , one provided for each bit position C 0 -C 3  of data in the register  110 . Each switch  130 - 160  is controlled by the value of the associated bit position in the register  110 . The output of each selection switch  130 - 160  is input to an AND gate  170 . 
     Typically, for each bit position D i  in the input signal, the match logic generates its complement, Di# (not shown). D i  and Di# are input to the switch associated with register it position i. The value of the data stored in the register at bit position i controls which of D i  and Di# are output to the AND gate  170  from the switch. 
     The AND gate  170  generates a signal representing a logical AND of the values output from each of the selection switches  130 - 160 . The AND is a logical 1 only when the signal input to the CAM  100  has the same value as the data stored in the register  110 . 
     No known memory system operates on redundant form input data. Accordingly, there is a need in the art for a content addressable memory system that reduces latency of memory requests when those requests include arithmetic operations. Further, there is a need in the art for a content addressable memory that operates on redundant form input data. 
     SUMMARY OF THE INVENTION 
     Embodiments of the present invention provide a content addressable memory addressable by redundant form input data. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a known traditional adder. 
     FIG. 2 is a block diagram of a known redundant form adder. 
     FIG. 3 is a block diagram of a known content addressable memory. 
     FIG. 4 is a block diagram of match logic conventional form content addressable memories. 
     FIG. 5 is a block diagram of a content addressable memory constructed in accordance with an embodiment of the present invention. 
     FIG. 6A is a logic diagram of a data decoder stage constructed in accordance with a first embodiment of the present invention. 
     FIG. 6B is a logic diagram of a data decoder stage constructed in accordance with a second embodiment of the present invention. 
     FIG. 7 is a block diagram of match detection logic constructed in accordance with a first embodiment of the present invention. 
     FIG. 8 is a block diagram of match detection logic constructed in accordance with a second embodiment of the present invention. 
     FIG. 9 illustrates how an adder of the prior art may be omitted according to use of the content addressable memory of FIG.  5 . 
    
    
     DETAILED DESCRIPTION 
     The present invention provides a content addressable memory that compares the value of redundant form input data to non-redundant form values stored therein. The CAM decodes the redundant form data in a data decoder. Thereafter, the CAM performs match detection on the decoded data. The present invention performs decoding and match detection more quickly than traditional adders and even more quickly than complete redundant form adders. 
     FIG. 5 illustrates a CAM  200  constructed in accordance with an embodiment of the present invention. The CAM  200  includes a data decoder  210  and a plurality of registers  220 . The data decoder  210  receives redundant form input data Ŝ [Ŝ=Ŝ m− Ŝ m+n ] and decodes it into data signals. The decoded redundant form data is input to match detection logic (not shown in FIG. 5) associated with each register. The CAM  200  generates an output representing which registers, if any, store data having the same value as the redundant form input data. 
     The data decoder  210  is a multi-bit decoder. It is populated by several stages of redundant form decoding circuits. The CAM  200  is adapted for use with predetermined bits of Ŝ, Ŝ m− Ŝ m+n . Match detection logic of CAM  200  may be different for cases where m=0 and where m≠0. A first embodiment of a redundant form decoding circuit is appropriate use with each redundant form “bit position” Ŝ i  for i≠0. For Ŝ 0 , a second embodiment of the redundant form decoding circuit is appropriate. 
     FIG. 6A illustrates a redundant form decoder circuit  300  for bit position Ŝ i  (i≠0) constructed in accordance with an embodiment of the present invention. The decoder circuit  300  generates address signals Z ia , Z ib , Z ic  and Z id  based upon the values of Ŝ i  (A i , B i ) and Ŝ i−1  (A i−1  and B i−1 ). Values A i , B i , A i−1  and B i−1  are input to the decoder  300  on inputs  302 ,  304 ,  306  and  308  respectively. Address signals Z ia , Z ib , Z ic  and Z id  are output from the decoder  300  on outputs  310 ,  312 ,  314  and  316  respectively. 
     A i  and B i  are input to a first XOR gate  320 . XOR gate  320  generates an output on line  322 . Line  322  is input to a pair of XOR gates  324  and  326 . XOR gate  324  generates the first differential pair of address signals Z ia  and Z ib . XOR gate  326  generates the second differential pair of address signals Z ic  and Z id . 
     A i−1  and B i−1  are input to an AND gate  328  and to an OR gate  334 . AND gate  328  generates an output on line  332  which is input to XOR gate  324 . The OR gate  334  generates an output on line  338  which is input to XOR gate  326 . 
     The redundant form decoder circuit  300  resembles a traditional adder to a great degree. Line  322  represents a non-redundant sum that would be obtained by adding A i  to B i . Lines  332  and  338  represent carries from position i−1 under appropriate circumstances: 
     The signal on line  332  represents the carry from position i−1 when S i−1 =1 (as described later). 
     The signal on line  338  represents the carry from position i−1 when S i−1 =0 (as described later). 
     Thus, either Z ia  or Z ic  represents the non-redundant sum bit S i . Identification of the one address line that carries the correct value, of S i  is determined based on additional information. This is discussed in connection with FIG. 7 below. 
     A traditional adder, however, requires an internal carry chain that propagates through every bit position in the addition. The redundant form decoder circuit  300  does not include any carry in from position i−2. 
     The redundant form decoder circuit  300  may be but one stage of a multi-bit decoder. The gates shown in FIG. 6A may be shared with other stages to form a complete multi-bit decoder. For example, additional gates  340  and  342  (shown in phantom) illustrate gates that would be provided to interconnect inputs A i  and B i  to the i+1 position decoder. They correspond to gates  328  and  334  in the i th  position decoder. Gate  330  (also in phantom) may be used in an i−1 position decoder. 
     FIG. 6B illustrates a redundant form decoder circuit  400  constructed in accordance with an embodiment of the present invention. The decoder circuit  400  is suitable for use with redundant form bit Ŝ 0 . Again, for notational purposes, the two bits of Ŝ 0  are represented as A 0  and B 0  respectively. They are input to the decoder circuit  400  at input terminals  402  and  404 . The decoder circuit  400  generates a single differential pair of address lines Z 0a  and Z 0b  on output terminals  406  and  408 . 
     A 0  and B 0  are input to an XOR gate  410 . XOR gate  410  generates an output on line  412 . A carry in C in , if provided for bit position  0 , is input at input terminal  416 . A second XOR gate  414  receives inputs from line  412  and terminal  416 . The second XOR gate  414  generates Z 0a  and Z 0b  on outputs  406  and  408 . If no carry in C in  is provided, the second XOR gate  414  may be omitted. Z 0a  and Z 0b  may be generated directly from the first XOR gate  410 . 
     FIG. 7 illustrates match detection logic  500  constructed in accordance with a first embodiment of the present invention. The match detection logic  500  may substitute for the match detection logic  230  of FIG.  5 . The match detection logic  500  includes a selection switch  510 - 540  provided for each bit position in the register. For each bit position i=0, four data signals Z ia −Z id  are input to the selection switch  510 - 530 . For bit position i=0, the two data signals Z 0a -Z 0b  are input to selection switch  540 . The output of each selection switch  510 - 540  is input to an AND gate  550 . AND gate  550  generates an enabled output only if all selection switches  510 - 540  output a logical “1” signal. 
     For each bit position i≠0, the associated selection switch  510 - 530  is controlled by the values stored in the register at bit positions i and i−1. Thus, switch  510  is controlled by values C3 and C2, switch  520  is controlled by the values of C2 and C1 and switch  530  is controlled by the values of C1 and C0. Switch  540 , however, is controlled solely by the value of C0. 
     Specifically, the address signals Z ia -Z id  from the decoder circuit  300  are connected to the selection switch of position i as follows: 
     Z ia  is connected to the switch input that is selected when Ci and Ci−1 are “11;” 
     Z ib  is connected to the switch input that is selected when Ci and Ci−1 are “01;” 
     Z ic  is connected to the switch input that is selected when Ci and Ci−1 are “10;” and 
     Z id  is connected to the switch input that is selected when Ci and Ci−1 are “00.” Thus, Ci−1 is an additional “known” quantity described above with respect to FIG.  6 A. For each bit position i≠0, the decoder assumes that S i−1 , is the value of Ci−1 actually stored in the memory register. The assumption is justifiable because, if it were not true, then one of the selection switches  220 - 250  would route a 0 to the AND  260  gate and prevent it from erroneously signaling a match. 
     Table  1  illustrates the signal values Z ia -Z ib  take for all possible permutations of A i , B i , A i−1  and B i−1  and Ci−1. It also shows the non-redundant values that Ci will take under each circumstance. Highlighting in the table demonstrates that, for the various combinations of A i , B i , A i−1 , B i−1 , and Ci−1 only one Of Z ia  and Z ic  represent Ci. 
     
       
         
           
               
             
               
                 TABLE 1 
               
             
            
               
                   
               
               
                 Decoded Data Signals Based On S i  and S i-1   
               
            
           
           
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
            
               
                 A i   
                 B i   
                 A i-1   
                 B i-1   
                 C i-1   
                 C i   
                 Z ia   
                 Z ib   
                 Z ic   
                 Z id   
                 A i   
                 B i   
                 A i-1   
                 B i-1   
                 C i-1   
                 C i   
                 Z ia   
                 Z ib   
                 Z ic   
                 Z id   
               
               
                   
               
               
                 0 
                 0 
                 0 
                 0 
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                 0 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                 0 
                 1 
                 1 
                 0 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                 1 
                 0 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 1 
                 0 
                 1 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                 1 
                 1 
                 0 
                 0 
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 0 
                 0 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
               
               
                 0 
                 1 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
               
               
                 1 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 0 
                 0 
                 0 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 0 
                 1 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
               
               
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 1 
                 0 
                 0 
                 1 
               
               
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 1 
                 1 
                 1 
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                   
               
            
           
         
       
     
     Z ib  and Z id  are provided because, for the AND gate  550  to indicate a match it must receive inputs that are entirely 1. If Z ia =Ci=0, Z ib  is input to the AND gate  550 . Similarly, if Z ic =Ci=0, Z id  is input to the AND gate  550 . 
     Interconnection of Z 0a  and Z 0b  to switch  540  is straightforward: 
     Z 0a  is connected to the switch input that is selected when S 0  is “1,” and 
     Z 0b  is connected to the switch input that is selected when S 0  is “0.” Based on a redundant form input signal, the CAM  200  of the present invention decodes the redundant form signal and determines whether non-redundant data stored in any of the registers  220  equals the value of the input signal. It generates an output identifying those registers storing the same value. 
     The data decoder  210  of the present invention does not possess a carry chain that characterizes the traditional adder of FIG.  1 . Thus, while it is traditionally viewed that redundant form data must be input to a traditional adder (having a carry chain) before non-redundant data may be obtained, the present invention provides improved processing over such a scheme. Here, the decoded data signals Z ia -Z id  are generated based only on values of the redundant form data at Ŝ i  and Ŝ i−1 . The data decoder is properly viewed, not as propagating a carry chain through all bit positions, but rather as generating signals Z ia -Z id  based on possible assumptions of the value of a carry in to the bit position. The actual values of data stored in the register demonstrate which of the assumptions actually is true. 
     FIG. 8 illustrates match detection logic  600  constructed in accordance with a second embodiment of the present invention. The match detection logic  600  may substitute for the match detection logic  230  of FIG.  5 . Here, the least significant bit position of the redundant form input data does not correspond to a bit position stored in a register  220 . Instead, redundant form bits Ŝ m −Ŝ m+n  are input to the CAM  200  (m≠0). The match detection logic  600  provides one selection switch  610 - 640  for each bit position i (i=m to m+n) of data stored in the register  220 . Each selection switch  610 - 640  receives decoded data signals Z ia -Z id  associated with the bit position i. An output from each selection switch  610 - 640  is input to an AND gate  650 . The AND gate  650  generates an output signal representative of whether the input redundant form data signal has a value equal to the data stored in the register  220 . 
     The selection switches  610 - 630  of each bit position i (i≠m) is controlled by the value of data stored in the register at bit positions i and i−1. Selection switch  640  is controlled by the value of data stored in bit position i=m and by a carry in C in . The carry in, C in , is to be the binary value of S m−1 . There are two ways that S m−1  may be obtained. The first way, a complete addition is performed in bit positions  0  through m−1 to directly compute S m−1 . However, S m−1  may be computed indirectly. External logic may be arranged so that, unless S m−1  has a predetermined value (0 or 1), the result of the CAM match is irrelevant. In an embodiment, the external logic will require S m−1  to be Cin for the CAM result to be relevant. If it is not (if S m−1 ≠C in ), then some other input to gate  650  will be low and prevent the gate from generating a false match signal. This indirect computational method likely will be faster than the direct computation of S m−1 . 
     Thus, the present invention provides for a content addressable memory responsive to redundant form inputs. The CAM may perform redundant form decoding on any redundant form data pattern and may receive, but need not receive, the least significant bit S 0  of the redundant form input. Where the least significant bit is not input to the data decoder, a carry in derived from the lower significant bits of the redundant form value is input to the match detection logic to control one of the selection switches. 
     Returning to FIG. 2, the example of redundant form adders illustrate a three input add. The adder of FIG. 2 may be known to some as a “three to two compressor.” 
     In a special case, it may be possible to omit arithmetic preprocessing altogether from a memory operation. Where a memory request is posted as a single arithmetic operation to be performed on two non-redundant inputs A and B (Ŝ=A+B), the addition may be omitted entirely. Instead, the inputs A and B may be input directly to the data decoder  210 . As shown in FIG. 9, no processing is required to “add” two non-redundant values in redundant form. The values A and B may be input without preprocessing directly to the data decoder  210 . 
     Accordingly, the CAM  200  of the present invention receives the two non-redundant values as a redundant form input. That is, the two non-redundant values are merged as a redundant form number and input to the data decoder  210 . The data decoder  210  performs redundant form decoding as described above. Based upon the decoded data output from the data decoder  210 , the match detection logic  230  addresses the values stored in the CAM registers  220 . 
     As has been described above, the present invention provides a content addressable memory that is addressable by redundant form input data. The CAM decodes the redundant form input data and, based upon the decoded data, performs match detection with data stored in the CAM registers. 
     Several embodiments of the present invention are specifically illustrated and described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.