Abstract:
Circuitry accepting a first input value and a second input value, and outputting (a) a first sum involving the first input value and the second input value, and (b) a second sum involving the first input value and the second input value, includes a first adder circuit, a second adder circuit, a compressor circuit and a preprocessing stage. The first input value and the second input value are input to the first adder circuit to provide the first sum. The first input value and the second input value are input to the preprocessing stage to provide inputs to the compressor circuit, which provides first and second compressed output signals which in turn are input to the second adder circuit to provide the second sum. The preprocessing stage may include circuitry to programmably zero the first input value, so that the first sum is programmably settable to the second input value.

Description:
FIELD OF THE INVENTION 
     This invention relates to circuitry that can be used to combine the initial adder of a high-radix multiplier with an optional pre-adder. 
     BACKGROUND OF THE INVENTION 
     Certain types of circuits that perform mathematical operations may require multiple adder circuits, such as carry-propagate or ripple-carry adders, which are inefficient. For example, in a symmetrical finite impulse response (FIR) filter, inputs may be added prior to being multiplied, which reduces the number of multipliers. However, that addition requires a pre-adder, and then the multiplication itself may include a compressor followed by another adder. The provision of multiple adders consumes a substantial amount of integrated circuit device area, and is of particular concern in programmable logic devices such as field-programmable gate arrays (FPGAs). 
     Moreover, large multiplication problems, such as those encountered in FIR filters, may require large compressor trees. The size of the compressor tree can be reduced by increasing the radix of the multiplier, but that in turn may require non-power-of-two manipulations of the inputs, which cannot be performed by simple shifting (as can be done for power-of-two manipulations), and may introduce the need for still more adders. 
     SUMMARY OF THE INVENTION 
     In accordance with embodiments of the present invention, the initial adder, or pre-adder, of an adder-multiplier-adder structure, which might itself include multiple adders (e.g., an adder-multiplexer-adder structure), can be simplified by providing a compressor followed by adders (e.g., a compressor-adder-adder structure). And because the adders will be adjacent one another, they can be combined into a single adder. 
     Therefore, in accordance with embodiments of the present invention there is provided circuitry accepting a first input value and a second input value and outputting (a) a first sum involving the first input value and the second input value, and (b) a second sum involving the first input value and the second input value. The circuitry includes a first adder circuit, a second adder circuit, a compressor circuit and a preprocessing stage. The first input value and the second input value are input to the first adder circuit to provide the first sum. The first input value and the second input value are input to the preprocessing stage to provide inputs to the compressor circuit. The compressor circuit provides first and second compressed output signals. The first and second compressed output signals are input to the second adder circuit to provide the second sum. 
     The preprocessing stage may include circuitry to programmably zero the first input value, so that the first sum is programmably settable to the second input value. 
     The compressor circuit may include respective separate circuitry for processing respective bit positions. For a respective bit position, the respective separate circuitry may have as inputs respective bits of each of the first and second input values, and respective next-less-significant bits of each of the first and second input values, and may further include an exclusive-OR gate combining the respective bits of each of the first and second input values. Output of the exclusive-OR gate in the respective separate circuitry for that respective bit position may be shared with respective separate circuitry for a next-more-significant bit position. 
     In the respective separate circuitry for the respective bit position, the respective next-less-significant bits of each of the first and second input values may be borrowed from respective separate circuitry for a next-less-significant bit position. 
     The first adder circuit may include a prefix tree having as inputs respective bits of the first and second input values, and providing as outputs respective carry values for each bit position. The first adder circuit also may include respective exclusive-OR gates for each bit position, each respective exclusive-OR gate having as inputs the respective carry value for that respective bit position, and the output of the exclusive-OR gate in that respective separate circuitry for that respective bit position. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Further features of the invention, its nature and various advantages will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which: 
         FIG. 1  shows a simplified representation of a digital signal processing (DSP) block; 
         FIG. 2  shows an example of input processing circuitry that may be provided in an input stage of a DSP block to provide an input and that input multiplied by ‘3’; 
         FIG. 3  shows input processing circuitry according to an embodiment of the present invention; 
         FIG. 4  shows an example of the internal structure of a portion of a compressor circuit; 
         FIG. 5  shows the internal structure of a portion of a first embodiment of a compressor circuit according to the present invention; 
         FIG. 6  shows the internal structure of a portion of a second embodiment of a compressor circuit according to the present invention; 
         FIG. 7  shows an example of the internal structure of a carry-propagate adder; 
         FIG. 8  shows a portion of a Kogge-Stone prefix tree; 
         FIG. 9  shows the internal structure of an embodiment of a carry-propagate adder according to the present invention; 
         FIG. 10  shows an example of how the generate output and the propagate output may be determined at each node in the first level of a Kogge-Stone prefix tree; 
         FIG. 11  shows an example of how the generate output and the propagate output may be determined at each node in each level beyond the first level of a Kogge-Stone prefix tree; 
         FIG. 12  shows how the generate and propagate structures of  FIGS. 10 and 11  may be combined in a particular case according to an embodiment of the present invention; 
         FIG. 13  shows how the generate and propagate structures of  FIG. 12  may be simplified according to an embodiment of the present invention; and 
         FIG. 14  is a simplified block diagram of an exemplary system employing a programmable logic device incorporating the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The discussion that follows will be based on an example of a programmable integrated circuit device such as an FPGA. However, it should be noted that the subject matter disclosed herein may be used in any kind of fixed or programmable device. 
       FIG. 1  shows a simplified representation of a digital signal processing (DSP) block  100  of the type that may be found in many types of integrated circuit devices, including, e.g., a programmable device such as an FPGA. DSP block  100  may include a plurality of multipliers  101  followed by adder/accumulator circuitry  102  that may include multiple adders  112  and registers  122 , as well as the ability to route out individual multiplication results without further combination. In addition, an input stage  103  may include various kinds of circuits for pre-multiplication manipulation of input signals, such as registers, shifters, multiplexers and adders (not shown). 
     As discussed above, it may be desirable to increase the radix of multipliers  101 . A radix-4 multiplier with inputs X and Y would also need inputs 2X and 2Y. Such inputs could easily be provided by left-shifting of X and Y by one bit position. However, a radix-8 multiplier, which is commonly used in higher-radix operations, would require 3X and 3Y, which cannot be provided by shifting. 
       FIG. 2  shows an example of input processing circuitry  200  that may be provided in input stage  103  to provide both an input, and that input multiplied by ‘3’, without using a further multiplier. This example further includes pre-addition of two inputs, as may be used in the symmetrical filter implementation discussed above. Thus, the inputs A and B shown in  FIG. 2  should not be considered the equivalent of inputs X and Y discussed above. Rather, the outputs of  FIG. 2  correspond to either input X or input Y; that is, both input X and input Y could have been processed by such circuitry. 
     Adder  201  adds inputs A and B. Multiplexer  202  selects as its input either that sum  211  (A+B), or input B. Output  212  of input processing circuitry  200  therefore is either (A+B) or B, depending on the selection made by multiplexer  202 . Output  212  also is routed both to adder  203  and to shifter  204 . Shifter  204  shifts output  212  one bit to the left, effectively multiplying output  212  by ‘2’. Shifter output  214  is added to output  212  by adder  203 . Output  213  is therefore either 3(A+B) or 3B, depending on the selection made by multiplexer  202 . 
     While input processing circuitry  200  achieves the desired result of providing the product of ‘3’ and another input, where the input may be a single number, or two added numbers (as in the symmetrical filter example), its adder-multiplexer-adder structure is inefficient, consuming significant device area. 
     Improved input processing circuitry  300  according to an embodiment of the invention is shown in  FIG. 3 , and includes a compressor  301  followed by two adders  302 ,  303  which may be, e.g., carry-propagate adders. Input processing circuitry  300  also has a preprocessing stage including shifters  304  to provide inputs 2A and 2B from inputs A and B, as well as an AND-gate  305  to provide the selection function of multiplexer  202 . AND gate  305  has a second input (not shown) which enables it to be used as a switch by inputting either a ‘0’ or a ‘1’ to that second input. 
     If AND-gate  305  is turned ON (by inputting ‘1’ to its second input), compressor  301  compresses inputs 2A, A, 2B and B to provide redundant-form sum and carry vectors  311 ,  321  representing 3(A+B), which are added by carry-propagate adder  302  to provide the output 3(A+B). If AND-gate  305  is turned OFF (by inputting ‘0’ to its second input, thereby programmably zeroing the ‘A’ input), adder  302  provides the output 3B. 
     At the same time, if AND-gate  305  is turned ON, adder  303  provides the output A+B, while if AND-gate  305  is turned OFF, adder  303  provides the output B. Although adder  303  may be a standard carry-propagate adder as noted above, it may be modified, as discussed in more detail below. Such modifications may require the input of A XOR B, which optionally may be provided at  331  by compressor  301 , in a manner described below. 
     The structure shown in  FIG. 3  replaces the adder-multiplexer-adder structure of  FIG. 2  with a more efficient compressor-and-parallel-adders structure. In accordance with further implementations of embodiments of the invention, the circuitry may be made even more efficient. 
       FIG. 4  shows an example of the internal structure of three bits  401 ,  402 ,  403  of a 4-2 compressor for adding four inputs, as in  FIG. 3 , according to a known compressor architecture. While the compressor architecture shown in  FIG. 3  is relatively efficient, efficiency can be improved for the particular operation at issue here, because the relationship of the inputs is such that adjacent bit positions share certain inputs. For example, XOR-gates  411  and  422  have the same inputs. Therefore, in the structure  500  shown in  FIG. 5 , XOR-gate  411  can be eliminated in favor of connection  501 . Similarly, XOR-gates  412  and  423  have the same inputs, meaning that in structure  500 , XOR-gate  412  can be eliminated in favor of connection  502 . And XOR-gate  413  shares inputs with an unseen XOR-gate in the next bit to the right (in the orientation of the drawing), so that XOR-gate  413  can be eliminated in favor of connection  503 . In the same way, connection  504  can eliminate an unseen XOR-gate in the next bit to the left. 
     In a further optimization shown in  FIG. 6 , the common inputs referred to in the previous paragraph may be replaced by connections  601 ,  602 ,  603 ,  604 . Specifically, instead of inputting A x-1  and B x-1  to both bits  401 ,  402 , A x-1  and B x-1  can be input to bit  402 , and conducted to bit  401  by conductors  601 . Similarly, instead of inputting A x-2  and B x-2  to both bits  402 ,  403 , A x-2  and B x-2  can be input to bit  403 , and conducted to bit  402  by conductors  602 . Likewise, conductors  603  can bring the unseen A x-3  and B x-3  inputs to bit  403  from the unseen bit to the right of bit  403 , and conductors  604  can bring the A x  and B x  inputs from bit  401  to the unseen bit to the left of bit  401 . 
     As described above,  FIG. 3  includes two carry-propagate adders  302 ,  303 , one of which (carry-propagate adder  302 ) adds the sum and carry vectors representing 3(A+B) (or 3B), and one of which (carry-propagate adder  303 ) adds A and B. A conventional carry-propagate adder with inputs X and Y might have the structure  700  shown in  FIG. 7 , in which the various bits of M ( 710 ) and N ( 720 ) are input to prefix tree  701  (a Kogge-Stone prefix tree  800  is shown in  FIG. 8 , although many other prefix tree architectures may be suitable and may be used; the choice of prefix tree architecture may depend on the particular design) to provide carry outputs  711 . The bits of M ( 710 ) and N ( 720 ) also are XORed together by XOR-gates  702 , and that XOR result  712  is further XORed by XOR-gates  703  with the carry outputs  711 . In the case of a carry-propagate adder following a compressor as in  FIG. 3 , the various M and N inputs would be the bits of the sum and carry outputs S and C, respectively. 
     In accordance with another embodiment of this invention, carry-propagate adder  303  can be simplified by eliminating XOR-gates  702 , because the XOR results  712  for the A+B calculation are already available in compressor  301  at XOR-gates  421 ,  422 ,  423 . Carry-propagate adder  303  would therefore have the structure shown in  FIG. 9 , in which the various M and N inputs would be the bits of A and B (cf., A x , B x , A x-1 , B x-1 , A x-2 , B x-2 , etc. in  FIG. 6 ), respectively, and the various P inputs would be the bits of A XOR B (cf., AB x , AB x-1 , AB x-2 , etc. in  FIG. 6 ). 
     Another embodiment of this invention relies on the fact that the inputs to carry-propagate adder  203  have a known relationship to each other—viz., that a second input is twice a first input or, in other words, the second input is the first input shifted left one bit. Thus each bit position of the second input can be represented by the next leftmost bit position of the first input, or each bit position of the first input can be represented by the next rightmost bit position of the second input. According to this embodiment, carry-propagate adder  203  can be simplified by altering its prefix tree as discussed below. 
     Referring again to Kogge-Stone prefix tree  800  shown in  FIG. 8 , each dot in  FIG. 8  represents a generate node and propagate node. Typically, the propagate nodes are not output, while the generate nodes provide carry outputs  711  that are input to XOR-gates  703 , as shown in  FIG. 7 .  FIG. 10  shows examples of structures used in the first row of prefix tree  800 . The two input bits at each bit position in that first row are used to create a generate output  1011  and a propagate output  1021 . As shown in  FIG. 10 , generate output  1011  may be created by ANDing of the two inputs at  1010 , and propagate output  1021  may be created by ORing of the two inputs at  1020 .  FIG. 10  is drawn showing the example of bit position 2 with inputs X 2 , Y 2 , but is the same for any bit position n (with inputs X n , Y n ). 
     Each subsequent node in prefix tree  800  may include structures as shown in  FIG. 11  to calculate its generate output  1111  and its propagate output  1121  using the logic structures of  FIG. 11 . (In  FIGS. 10 and 11 , the index—(0, N, N+1)—refers to the level of prefix tree  800 —i.e., the row in  FIG. 8 , where the top row has index 0—and the subscript refers to the bit position—i.e., the column in  FIG. 8 , where the rightmost row is bit position 0. As previously noted above,  FIG. 10  represents any bit position n, with n=2 being shown. Similarly,  FIG. 11  represents any bit position x, which is not the same as input X of  FIG. 10 .) 
     In the case where X+Y=A+2A, these structures can be simplified. To avoid confusion, let A=C, so that A+2A=C+(C&lt;&lt;1) (where “&lt;&lt;” denotes a left-shift operation, which for binary numbers is equivalent to multiplying by two). In such an addition, the bits of the two inputs would line up as follows: 
                           ⁢       C   5     ⁢     C   4     ⁢     C   3     ⁢     C   2                     C   5     ⁢     C   4     ⁢     C   3     ⁢     C   2                 
It should be noted that in this example, while only four bits of each input are shown (from C 5  down to C 2 ), bits down to the 0th bit extend to the right and bits up to the highest bit required extend to the left. From here, it can be seen that any pair of the X n , Y n  inputs in  FIG. 10  becomes C n , C n-1 .
 
     Taking then as an example bit position n=5, and inputting A 5  and A 4  (A=C as noted above) to the structures shown in  FIG. 10  for row 0 of prefix tree  800 , and then substituting those structures into the structures shown in  FIG. 11  for row 1 of prefix tree  800 , yields the logic structures shown in  FIG. 12  for bit position n=5 for the combination of row 0 and row 1. Simplifying the logic structures of  FIG. 12  yields the logic structures of  FIG. 13 . Thus, for the case where the two inputs of an adder are a number and twice that number, then the initial rows of the prefix tree can be substantially reduced, in terms of device area, to the structures of  FIG. 13 . 
     As can be seen from  FIG. 8 , a Kogge-Stone prefix tree has many more nodes in its early rows than in its later rows. It will be appreciated, then, that where an adder is built using a Kogge-Stone prefix tree, or any prefix tree with a similar architecture, the simplification of the initial rows according to the embodiment implemented in  FIGS. 10-13  can reduce the overall device area consumed by the prefix tree by between about 15% and about 25%, depending on the particular prefix tree architecture used. 
     Thus it is seen that for implementing certain kinds of arithmetic operations, such as a choice between addition, and pre-addition for a multiplier, adder circuitry can be provided having reduced area, based on logical simplification or sharing of logic. 
     A PLD  180  configured to include arithmetic circuitry according to any implementation of the present invention may be used in many kinds of electronic devices. One possible use is in an exemplary data processing system  1800  shown in  FIG. 14 . Data processing system  1800  may include one or more of the following components: a processor  1801 ; memory  1102 ; I/O circuitry  1803 ; and peripheral devices  1804 . These components are coupled together by a system bus  1805  and are populated on a circuit board  1806  which is contained in an end-user system  1807 . 
     System  1800  can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, Remote Radio Head (RRH), or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD  180  can be used to perform a variety of different logic functions. For example, PLD  180  can be configured as a processor or controller that works in cooperation with processor  1801 . PLD  180  may also be used as an arbiter for arbitrating access to a shared resources in system  1800 . In yet another example, PLD  180  can be configured as an interface between processor  1801  and one of the other components in system  1800 . It should be noted that system  1800  is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims. 
     Various technologies can be used to implement PLDs  180  as described above and incorporating this invention. 
     It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.