Abstract:
A fast lookahead carry adder includes adder logic and lookahead carry-path logic coupled to the adder logic. The carry path logic has a main carry path, a carry entrance path and a carry exit path, the carry entrance path separate from the carry exit path.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application is a continuation and claims the priority benefit of U.S. patent application Ser. No. 12/022,721 filed Jan. 30, 2008 and entitled “Fast Carry Lookahead Circuits,” the disclosure of which is incorporated herein by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to digital logic circuits. More particularly, the present invention relates to arithmetic logic circuits and to fast lookahead carry circuits. 
         [0004]    2. The Prior Art 
         [0005]    Adder circuits include provision for producing and propagating a carry bit. A single bit stage of a prior-art ripple-carry adder is shown in  FIG. 1 . Input terms “a” and “b” are presented on input lines  10  and  12  to XOR gate  14 . The “b” input on line  12  is also presented to the “0” input of multiplexer  16 . A carry input (ci) on line  18  is presented to the “1” data input of multiplexer  16 . The output of XOR gate  14  produces a term px that is used to drive the select input of multiplexer  16 . The output of multiplexer  16  is the carry output of the adder presented on carry-out line (co)  20 . The px term and the ci input (shown as the cx input) are presented to XOR gate  22 . The output term of the adder is presented on line  24  at the output of XOR gate  22 . The carry chain is the portion of the circuit of  FIG. 1  contained within the dashed lines  26  of  FIG. 1 . 
         [0006]    Different prior-art adder types use the same logic to create the carry-propagate signal px for a bit x as well as the carry input signal ux, and the XOR gate  22  to create the sum output(s) from the propagate signal px and the local carry output signal cx. 
         [0007]      FIGS. 2-8  focus on alternative implementations of the carry-chain logic between ci, px and ux inputs and co and cx outputs of the carry chain, contained within the dashed lines  26  of  FIG. 1 , in order to compare the prior art with the present invention.  FIGS. 2-8  show different examples of multi-bit adders. 
         [0008]      FIG. 2  is a schematic diagram of a carry chain of a prior-art 2-bit wide ripple-carry adder. The carry-input signal u 0  for bit  0  is presented on line  30  to the “0” input of multiplexer  32 . The carry-in signal ci is presented on line  34  to the “1” input of multiplexer  32 . The propagate signal p 0  for bit  0  is presented on line  36  to the select input of multiplexer  32 . 
         [0009]    The carry-input signal u 1  for bit  1  is presented on line  38  to the “0” input of multiplexer  40 . The output of multiplexer  32  is presented to the “1” input of multiplexer  40 . The propagate signal p 1  for bit  1  is presented on line  42  to the select input of multiplexer  40 . The output of multiplexer  40  is buffered by buffer  44  to produce the carry-out (co) signal on line  46 . The carry-in signal on line  34  is buffered by buffer  48  to produce the local carry-out signal c 0  on line  50 . The output of multiplexer  32  is buffered by buffer  52  to produce the local carry-out signal c 1  on line  54 . 
         [0010]    The buffer  44  at the carry output is optional and could alternatively be an inverter, creating an inverted carry-output and it can be placed after any number of multiplexers to optimize speed. The other buffers  48  and  52  are also optional, and serve to limit the capacitive load on the main carry path. 
         [0011]    Referring now to  FIG. 3 , a schematic diagram shows only the carry chain of a prior-art 2-bit wide carry-lookahead-adder. The carry-input signal u 0  for bit  0  is presented on line  60  to the “0” input of multiplexer  62 . The carry-in signal ci is presented on line  64  to the “1” input of multiplexer  62 . The propagate signal p 0  for bit  0  is presented on line  66  to the select input of multiplexer  62 . 
         [0012]    The carry-input signal u 1  for bit  1  is presented on line  68  to the “0” input of multiplexer  70 . The output of multiplexer  62  is presented to the “1” input of multiplexer  70 . The propagate signal p 1  for bit  1  is presented on line  72  to the select input of multiplexer  70 . The output of multiplexer  70  is buffered by buffer  74 . 
         [0013]    The output of buffer  74  is presented to the “0” input of multiplexer  76 . The carry-in input ci is presented to the “1” input of multiplexer  76 . The propagate signals p 0  and p 1  are combined in AND gate  78 . The output of AND gate  78  is presented to the select input of multiplexer  76 . The output of multiplexer  76  is buffered by buffer  80  to produce the carry-out (co) signal on line  82 . The carry-in signal on line  64  is buffered by buffer  84  to produce the local carry-out c 0  signal on line  86 . The output of multiplexer  62  is buffered by buffer  88  to produce the local carry-out c 1  signal on line  90 . Buffers  74 ,  80 ,  84 , and  88  are optional and buffers  80 ,  84 , and  88  could also be inverters without having to invert any of the signals. 
         [0014]    If both propagate signals p 0  and p 1  within the basic lookahead-unit (2 bits wide in this example) are logic “1,” the carry-input of the entire stage gets propagated to the co output on line  82  by multiplexer  76 . 
         [0015]    Referring now to  FIG. 4 , a schematic diagram shows only the carry chain of a prior-art 3-bit wide carry-lookahead-adder. The carry-input signal u 0  for bit  0  is presented on line  100  to the “0” input of multiplexer  102 . The carry-in signal ci is presented on line  104  to the “1” input of multiplexer  102 . The propagate signal p 0  for bit  0  is presented on line  106  to the select input of multiplexer  102 . 
         [0016]    The carry-input signal u 1  for bit  1  is presented on line  108  to the “0” input of multiplexer  110 . The output of multiplexer  102  is presented to the “1” input of multiplexer  110 . The propagate signal p 1  for bit  1  is presented on line  112  to the select input of multiplexer  110 . 
         [0017]    The carry-input signal u 2  for bit  2  is presented on line  114  to the “0” input of multiplexer  116 . The output of multiplexer  110  is presented to the “1” input of multiplexer  116 . The propagate signal p 2  for bit  2  is presented on line  118  to the select input of multiplexer  116 . The output of multiplexer  116  is buffered by buffer  120 . 
         [0018]    The output of buffer  120  is presented to the “0” input of multiplexer  122 . The carry-in input ci is presented to the “1” input of multiplexer  122 . The propagate signals p 0 , p 1 , and p 2  are combined in AND gate  124 . The output of AND gate  124  is presented to the select input of multiplexer  122 . The output of multiplexer  122  is buffered by buffer  126  to produce the carry-out (co) signal on line  128 . The carry-in signal on line  104  is buffered by buffer  130  to produce the local carry-out signal c 0  on line  132 . The output of multiplexer  102  is buffered by buffer  134  to produce the local carry-out c 1  signal on line  136 . The output of multiplexer  110  is buffered by buffer  138  to produce the local carry-out c 2  signal on line  140 . Buffers  120 ,  126 ,  130   134 , and  138  are optional and buffers  126 ,  130 ,  134 , and  138  could also be inverters without having to invert any of the signals. 
         [0019]    In a manner similar to the operation of the carry chain of the 2-bit wide carry-lookahead-adder of  FIG. 3 , if all three propagate signals p 0 , p 1 , and p 2  within the basic lookahead-unit are logic “1,” the carry-input of the entire stage gets propagated to the co output on line  128  by multiplexer  122 . 
       BRIEF DESCRIPTION 
       [0020]    The present invention reduces the delay of carry-lookahead adders through the main carry-path, as well as the entrance path and the exit path. A fast lookahead carry adder includes adder logic and lookahead carry-path logic coupled to the adder logic. The carry path logic has a carry entrance path and a carry exit path, the carry entrance path separate from the carry exit path. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING FIGURES 
         [0021]      FIG. 1  is a schematic diagram of a prior-art ripple-carry adder. 
           [0022]      FIG. 2  is a schematic diagram showing only the carry chain of a prior-art 2-bit wide ripple-carry adder 
           [0023]      FIG. 3  is a schematic diagram showing only the carry chain of a prior-art 2-bit wide carry-lookahead-adder. 
           [0024]      FIG. 4  is a schematic diagram showing only the carry chain of a prior-art 3-bit wide carry-lookahead-adder. 
           [0025]      FIG. 5  is a schematic diagram showing an illustrative example of a 2-bit wide carry lookahead adder with a separate carry entrance and exit path according to the present invention. 
           [0026]      FIG. 6  is a schematic diagram showing an illustrative example of a 3-bit wide carry lookahead adder with a separate carry entrance and exit path according to the present invention. 
           [0027]      FIG. 7  is a schematic diagram showing another illustrative example of a 3-bit wide carry lookahead adder with a separate carry entrance and exit path according to the present invention. 
           [0028]      FIG. 8  is a schematic diagram showing an illustrative example of the use of a hierarchical approach in a 4-bit wide carry lookahead adder to reduce the number of multiplexers in the entrance and exit paths, even for the 4-bit width. 
       
    
    
     DETAILED DESCRIPTION 
       [0029]    Persons of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons. 
         [0030]    The terms carry-entrance path, carry-exit path and main carry path are used herein. As used herein, the carry-entrance path extends from the u 0  input to the co output; the carry-exit path extends from input ci to the local carry-out c 0 -cx outputs, where x is the most significant bit. The main carry path extends from the ci input to the co output. 
         [0031]    Referring now to  FIG. 5 , a schematic diagram shows an illustrative example of a carry path for a 2-bit wide carry lookahead adder having separate carry-entrance and carry-exit paths according to the present invention. 
         [0032]    The carry-input signal u 0  for bit  0  is presented on line  150  to the “0” input of multiplexer  152 . The carry-in signal ci is presented on line  154  through buffer  156  to the “1” input of multiplexer  152 . The propagate signal p 0  for bit  0  is presented on line  158  to the select input of multiplexer  152 . 
         [0033]    The carry-input signal u 1  for bit  1  is presented on line  160  to the “0” input of multiplexer  162 . The u 0  input on line  150  is presented to the “1” input of multiplexer  162 . The propagate signal p 1  for bit  1  is presented on line  164  to the select input of multiplexer  162 . The output of multiplexer  162  is buffered by buffer  166 . 
         [0034]    The output of buffer  166  is presented to the “0” input of multiplexer  170 . The carry-in (ci) input on line  154  is presented to the “1” input of multiplexer  170 . The propagate signals p 0  and p 1  are combined in AND gate  168 . The output of AND gate  168  is presented to the select input of multiplexer  170 . The output of multiplexer  170  is buffered by buffer  172  to produce the carry-out (co) signal on line  174 . The buffered carry-in signal is buffered by buffer  176  to produce the local carry-out c 0  signal on line  178 . The output of multiplexer  152  is buffered by buffer  180  to produce the local carry-out c 1  signal on line  182 . Buffers  156 ,  166 ,  172 ,  176  and  180  are optional or could be replaced by inverters by changing the polarities of some signals to compensate for the inversion. 
         [0035]    As may be seen from a comparison of the carry paths of  FIGS. 3 and 5 , the carry-exit path from ci to local carry outputs c 0  and c 1  is entirely separate from the carry-entrance path from u 0  to ci. In addition, the use of buffer  156 , formed using small geometry devices, to isolate the remainder of the carry exit path from the ci input reduces the capacitive loading on the ci node. By splitting the carry-entrance and carry—exit paths, the longest carry-entrance path from u 0  to co is through multiplexers  162  and  170 , as compared with the longest carry-entrance path from u 0  to co in  FIG. 3  through multiplexers  62 ,  70 , and  76 . The present invention thus reduces the carry entrance path by one multiplexer, which shortens the propagation delay through the carry chain. By locating multiplexer  152  in the carry-exit path downstream from buffer  156  the capacitive load on the ci input is reduced, thus speeding up the main carry path. 
         [0036]    Referring now to  FIG. 6 , a schematic diagram shows an illustrative example of a carry path for a 3-bit wide carry lookahead adder having separate carry entrance and exit paths according to another embodiment of the present invention. The carry-input signal u 0  for bit  0  is presented on line  190  to the “0” input of multiplexer  192 . The carry-in signal ci is presented on line  194  through buffer  196  to the “1” input of multiplexer  192 . The propagate signal p 0  for bit  0  is presented on line  198  to the select input of multiplexer  192 . 
         [0037]    The carry-input signal u 1  for bit  1  is presented on line  200  to the “0” input of multiplexer  202 . The u 0  input on line  190  is presented to the “1” input of multiplexer  202 . The propagate signal p 1  for bit  1  is presented on line  204  to the select input of multiplexer  202 . 
         [0038]    The carry-input signal u 2  for bit  2  is presented on line  206  to the “0” input of multiplexer  208 . The output of multiplexer  202  is presented to the “1” input of multiplexer  208 . The propagate signal p 2  for bit  2  is presented on line  210  to the select input of multiplexer  208 . The output of multiplexer  208  is buffered by buffer  212 . 
         [0039]    The output of buffer  212  is presented to the “0” input of multiplexer  214 . The unbuffered carry-in signal (ci) on line  192  is presented to the “1” input of multiplexer  214 . The propagate signals p 0 , p 1 , and p 2  are combined in AND gate  216 . The output of AND gate  216  is presented to the select input of multiplexer  214 . The output of multiplexer  214  is buffered by buffer  218  to produce the carry-out (co) signal on line  220 . The buffered carry-in signal is buffered by buffer  222  to produce the local carry-out c 0  signal on line  224 . The output of multiplexer  192  is buffered by buffer  226  to produce the local carry-out c 1  signal on line  228 . The u 1  input on line  200  is presented to the “0” input of multiplexer  230 . The output of multiplexer  192  is presented to the “0” input of multiplexer  230 . The select input of multiplexer  230  is driven by the p 1  signal on line  204 . The output of multiplexer  230  is buffered by buffer  232  to produce the local carry-out c 2  signal on line  234 . Buffers  196 ,  212 ,  218 ,  222 ,  226 , and  232 , are optional or could be replaced by inverters by changing the polarities of some signals to compensate for the inversion. 
         [0040]    As in the embodiment of  FIG. 5 , the carry-exit path from ci to local carry outputs c 0 , c 1 , and c 2  is entirely separate from the carry-entrance path from u 0  to ci. In addition, the use of buffer  196 , formed using small geometry devices, to isolate the remainder of the carry exit path from the ci input reduces the capacitive loading on the ci node. As may be seen by comparing  FIGS. 4 and 6  with  FIGS. 3 and 5 , enlarging the basic unit width by one more bit will increase the length of the delay paths in both the carry-entrance and exit paths by one more multiplexer. The longest carry-entrance path from u 0  to co in  FIG. 6  is through multiplexers  202 ,  208 , and  214 , as compared with the longest carry-entrance path from u 0  to co in  FIG. 3  through multiplexers  102 ,  110 ,  116 , and  122 . Again, the present invention reduces this path by one multiplexer, which shortens the propagation delay through the carry chain. The adder shown in  FIG. 6  expanded to a width of 4 bits would have four multiplexers in the entrance-path as well as in the exit-path. 
         [0041]    Referring now to  FIG. 7 , a schematic diagram shows another illustrative example of a carry path for a 3-bit wide carry lookahead adder having separate carry entrance and exit paths according to another embodiment of the present invention. The embodiment of  FIG. 7  is similar to the one shown in  FIG. 6 , and corresponding elements in  FIGS. 6 and 7  will be identified by like reference numerals. 
         [0042]    The carry-input signal u 0  for bit  0  is presented on line  190  to the “0” input of multiplexer  192 . The carry-in signal ci is presented on line  194  through buffer  196  to the “1” input of multiplexer  192 . The propagate signal p 0  for bit  0  is presented on line  198  to the select input of multiplexer  192 . 
         [0043]    The carry-input signal u 1  for bit  1  is presented on line  200  to the “0” input of multiplexer  202 . The u 0  input on line  190  is presented to the “1” input of multiplexer  202 . The propagate signal p 1  for bit  1  is presented on line  204  to the select input of multiplexer  202 . 
         [0044]    The carry-input signal u 2  for bit  2  is presented on line  206  to the “0” input of multiplexer  208 . The output of multiplexer  202  is presented to the “1” input of multiplexer  208 . The propagate signal p 2  for bit  2  is presented on line  210  to the select input of multiplexer  208 . The output of multiplexer  208  is buffered by buffer  212 . 
         [0045]    The output of buffer  212  is presented to the “0” input of multiplexer  214 . The unbuffered carry-in signal (ci) on line  192  is presented to the “1” input of multiplexer  214 . The propagate signals p 0 , p 1 , and p 2  are combined in AND gate  216 . The output of AND gate  216  is presented to the select input of multiplexer  214 . The output of multiplexer  214  is buffered by buffer  218  to produce the carry-out (co) signal on line  220 . The buffered carry-in signal is buffered by buffer  222  to produce the local carry-out c 0  signal on line  224 . The output of multiplexer  192  is buffered by buffer  226  to produce the local carry-out c 1  signal on line  228 . The u 1  input on line  200  is presented to the “0” input of multiplexer  230 . The ci input on line  194  buffered by buffer  196  is presented to the “1” input of multiplexer  230 . The p 0  and p 1  signals on lines  198  and  204  are combined in AND gate  232 . The output of AND gate  232  drives the select input of multiplexer  230 . The output of multiplexer  230  is buffered by buffer  234  to produce the local carry-out c 2  signal on line  236 . Buffers  196 ,  212 ,  218 ,  222 ,  226 , and  234 , are optional or could be replaced by inverters by changing the polarities of some signals to compensate for the inversion. 
         [0046]    As in the embodiments of  FIGS. 5 and 6 , the carry-exit path in the embodiment of  FIG. 7  from ci to local carry outputs c 0 , c 1 , and c 2  is entirely separate from the carry-entrance path from u 0  to ci. In addition, the use of buffer  196 , formed using small geometry devices, to isolate the remainder of the carry exit path from the ci input reduces the capacitive loading on the ci node. As in the embodiments of  FIGS. 5 and 6 , enlarging the basic unit width by one more bit will increase the length of the delay paths in both the carry-entrance and exit paths by one more multiplexer. The longest carry-entrance path from u 0  to co in  FIG. 7  is through multiplexers  202 ,  208 , and  214 , as compared with the longest carry-entrance path from u 0  to co in  FIG. 3  through multiplexers  102 ,  110 ,  116 , and  122 . Again, the present invention reduces this path by one multiplexer, which shortens the propagation delay through the carry chain. 
         [0047]    According to another aspect of the invention, shown in  FIG. 7 , to which attention is now drawn, a hierarchical approach is used to reduce the number of multiplexers in the entrance path to three and in the exit path to two, even for the 4-bit width shown. 
         [0048]    Referring now to  FIG. 8 , a schematic diagram shows an illustrative example of a carry path using a hierarchical approach for a 4-bit wide carry lookahead adder having separate carry entrance and exit paths according to the present invention. The carry-input signal u 0  for bit  0  is presented on line  240  to the “0” input of multiplexer  242 . The carry-in signal ci is presented on line  244  through buffer  246  to the “1” input of multiplexer  242 . The propagate signal p 0  for bit  0  is presented on line  248  to the select input of multiplexer  242 . 
         [0049]    The carry-input signal u 1  for bit  1  is presented on line  250  to the “0” input of multiplexer  252 . The u 0  input on line  240  is presented to the “1” input of multiplexer  252 . The propagate signal p 1  for bit  1  is presented on line  254  to the select input of multiplexer  252 . 
         [0050]    The carry-input signal u 2  for bit  2  is presented on line  256  to the “1” input of multiplexer  258 . The carry-input signal u 3  for bit  3  is presented on line  260  to the “0” input of multiplexer  258 . The propagate signal p 3  for bit  3  is presented on line  262  to the select input of multiplexer  258 . 
         [0051]    The output of multiplexer  258  is presented to the “0” input of multiplexer  264 . The output of multiplexer  252  is presented to the “1” input of multiplexer  264 . The p 2  and p 3  signals are combined in AND gate  266 . The output of AND gate  266  is presented to the select input of multiplexer  264 . The output of multiplexer  264  is buffered by buffer  268 . 
         [0052]    The output of buffer  268  is presented to the “0” input of multiplexer  270 . The unbuffered carry-in signal (ci) on line  244  is presented to the “1” input of multiplexer  270 . The propagate signals p 0 , p 1 , p 2 , and p 3  are combined in AND gate  272 . The output of AND gate  272  is presented to the select input of multiplexer  270 . The output of multiplexer  270  is buffered by buffer  274  to produce the carry-out (co) signal on line  276 . 
         [0053]    The buffered carry-in signal is buffered by buffer  278  to produce the local carry-out c 0  signal on line  280 . The output of multiplexer  242  is buffered by buffer  282  to produce the local carry-out c 1  signal on line  284 . The output of multiplexer  252  is presented to the “0” input of multiplexer  286 . The buffered carry-in signal is presented to the “1” input of multiplexer  286 . The p 0  and p 1  signals are combined in AND gate  288 . The output of AND gate  288  is presented to the select input of multiplexer  286 . The output of multiplexer  286  is buffered by buffer  290  to produce the local carry-out c 2  signal on line  292 . The carry-input signal u 2  for bit  2  is presented on line  256  to the “0” input of multiplexer  294 . The output of multiplexer  286  is presented to the “1” input of multiplexer  294 . The p 2  signal on line  296  is presented to the select input of multiplexer  294 . The output of multiplexer  294  is buffered by buffer  298  to produce the local carry-out c 3  signal on line  300 . Buffers  246 ,  268 ,  274 ,  278 ,  282 ,  290 , and  298  are optional or could be replaced by inverters by changing the polarities of some signals to compensate for the inversion. 
         [0054]    The hierarchical approach of  FIG. 8  has several advantages. The number of multiplexers in the entrance path is reduced to three and in the number of multiplexers in the exit path is reduced to two, even for the 4-bit width shown. The embodiment of  FIGS. 6 and 7  expanded to four bits would require four multiplexers in the entrance path. The prior-art example of  FIG. 4  expanded to four bits would require five multiplexers in the entrance path. The embodiment of  FIG. 6  expanded to four bits would require three multiplexers in the exit path. The prior-art example of  FIG. 4  expanded to four bits would require three multiplexers in the exit path. The hierarchical approach thus also saves multiplexers in the exit path. 
         [0055]    While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.