Abstract:
Combination circuitry for combining a plurality of multi-bit partial product terms includes at least one stage arranged to receive a first number of input bits. At least one stage includes at least one combiner having: a first logic device comprising an input arranged to receive a first set of the first number of input bits and an output arranged to output a first combined result; a second logic device comprising a first input arranged to receive a second set of the first number of input bits, a second input connected to receive the first combined result, a first output arranged to output a second combined result, and a second output arranged to output a first combined bit group; and a third logic device comprising an input connected to receive the second combined result and an output arranged to output a second combined bit group, whereby the first combined bit group is available for a further stage of the combination circuitry before the second combined bit group.

Description:
TECHNICAL FIELD OF THE INVENTION  
       [0001]     The present invention relates to combination circuitry, particularly but not exclusively for multiplication circuitry.  
       BACKGROUND OF THE INVENTION  
       [0002]     A typical binary multiplier for multiplying two binary numbers together comprises a series of processing stages, such as an operand encoder, a partial product generator, a product term compressor, and a final addition stage.  
         [0003]     The operand encoder encodes the first operand and reduces the number of terms representing the operand. Thus, for example, a 32-bit number may be reduced using a Booth code to 17 terms or fewer.  
         [0004]     The partial product generator multiplies the second operand by each of the encoded terms to produce a partial product term. Thus, for a 32-bit multiplier where the first operand is encoded as 17 terms, a total of 17 partial product terms are produced.  
         [0005]     The product term compressor adds together (or as otherwise known compresses) the many partial products to form a pair of terms.  
         [0006]     Finally, the final term addition stage adds the pair of terms together to form the final product value.  
         [0007]      FIG. 1  shows a typical 32-bit multiplier structure whereby first and second operands  151  and  153  are input into a “Booth recoding” stage  101 , which carries out the operand encoding stage and the partial product generation stage to generate 17 partial product terms  157 . The 17 partial product terms  157  are fed into the compression circuitry, shown as “17 terms to 2” compressor  103  to output two 64-bit terms  159 .  
         [0008]     The 64-bit output terms  159  are passed to the final term addition stage, the “add  64 ” block  105 , to produce a final product value  161 .  
         [0009]     Compression circuitry, such as the “17 terms to 2” compressor  103  shown in  FIG. 1 , has typically been designed to produce all of the possible partial product terms generated by the operand to form 2 terms within the smallest number of consecutive stages. Conventionally, the compression circuitry is arranged in terms of columns of compression stages. Each compression stage column operates in combining term bits having the same binary weighting (i.e. 2 n ).  
         [0010]     Conventional compressor stage columns are made up from full adders arranged in such a way that all of the input terms are required at essentially the same time, and the output terms are output at essentially the same time. These conventional stages comprising full adders lack flexibility in both input timing and output timing, requiring the timing of inputs to be strictly controlled and therefore producing strict demands on the circuitry generating the prior stages and also producing the partial product terms initially input to the compression circuit.  
       SUMMARY OF THE INVENTION  
       [0011]     To address the above-discussed deficiencies of the prior art, an object of the present invention is to reduce the severity of the timing requirements of the inputs and therefore lessening the timing constraints imposed on previous stages of the binary multiplier with respect to multiplication of binary numbers.  
         [0012]     There is provided according to the invention combination circuitry for combining a plurality of multi-bit partial product terms. The combination circuitry comprises at least one stage arranged to receive a first number of input bits. At least one stage comprises at least one combiner. The at least one combiner comprises a first logic device comprising an input arranged to receive a first set of the first number of input bits and an output arranged to output a first combined result; a second logic device comprising a first input arranged to receive a second set of the first number of input bits, a second input connected to receive the first combined result, a first output arranged to output a second combined result, and a second output arranged to output a first combined bit group; and a third logic device comprising an input connected to receive the second combined result and an output arranged to output a second combined bit group, whereby the first combined bit group is available for a further stage of the combination circuitry before the second combined bit group.  
         [0013]     Embodiments of the invention described in the following have the advantage of lowering the timing constraints imposed on the use of the combined bit groups, as the first combined bit group is produced by circuitry before the production of the second combined bit group. This allows the further combination circuit stages to take advantage of the early supply of combined bits to produce timing advantages for the data flow path.  
         [0014]     The combination circuitry may comprise a further stage which comprises a further stage combiner arranged to receive and combine the first and second combined bit groups. The further stage combiner comprises: a further stage combiner first logic device comprising an input arranged to receive the first combined bit group and an output arranged to output a first combined result; and a further stage combiner second logic device comprising a first input arranged to receive the second combined bit group, a second input connected to receive the first combined result from the further stage combiner first logic device, and an output arranged to output a further combined bit group.  
         [0015]     The further stage combiner second logic device further may comprise a second output arranged to output a second combined result. Also, the further stage combiner may further comprise a third logic device comprising an input connected to receive the second combined result of the further stage combiner second logic device and an output arranged to output a second further combined bit group, wherein the further combined bit group is available for an additional stage of the combination circuitry before the second further combined bit group.  
         [0016]     Embodiments of the invention described hereafter have the further advantage whereby the arrangement of the stages benefits from the staggering of the inputs and outputs between stages to significantly reduce the critical path length for compression data.  
         [0017]     The at least one stage combiner is possibly a 5:3 compression cell arranged to receive two bits of the first set of the first number of input bits and three bits of the second set of the first number of input bits and to output one bit of the first combined bit group and two bits of the second combined bit group.  
         [0018]     The first logic device may further comprise an XOR gate, and the first logic device first combined result may comprise a first output bit from the XOR gate and a second output bit from one of the first set of input bits.  
         [0019]     The second logic device may further comprise: a first XOR gate; a second XOR gate; and a multiplexer.  
         [0020]     The third logic device may comprise an XOR gate and a multiplexer.  
         [0021]     According to a second aspect of the present invention, there is provided a method for combining a plurality of multi-bit partial product terms, comprising the steps of: receiving a first set of a first number of input bits; receiving a second set of the first number of input bits; and combining the received first and second sets of input bits to produce a first combined bit group and a second combined bit group. The step of combining comprises the steps of: combining the first set of input bits prior to receiving the second set of input bits, and producing the first combined bit group prior to producing the second combined bit group.  
         [0022]     The method may further comprise the steps of: receiving the first and second combined bit groups; and further combining the first and second combined bit groups to produce a further combined bit group, wherein the step of further combining may further comprise the step of further combining the first combined bit set prior to receiving the second combined bit group.  
         [0023]     The step of further combining may further comprise the step of producing a first part of the further combined bit group prior to producing a second part of the further combined bit group.  
         [0024]     Before undertaking the DETAILED DESCRIPTION OF THE INVENTION below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; and the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term “apparatus” and “controller” may be used interchangeably and mean any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular apparatus or controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0025]     For a better understanding of the present invention and to show how the same may be carried into effect, reference will now be made by way of example only to the accompanying drawings, in which like reference numerals represent like parts, and in which:  
         [0026]      FIG. 1  shows a schematic view of a typical multiplier as known in the art;  
         [0027]      FIG. 2  shows a schematic view of a typical 10-bit compressor column comprising conventional full adders as used in  FIG. 1 ;  
         [0028]      FIG. 3  shows a schematic view of an improved 10-bit compressor column;  
         [0029]      FIG. 4  shows a schematic view of an improved full adder circuit as shown in  FIG. 3 ;  
         [0030]      FIG. 5  shows a schematic view of an improved 5:3 compression cell as shown in  FIG. 3 ; and  
         [0031]      FIG. 6  shows a schematic view of a further improved compressor column circuit comprising compression cells as shown in  FIG. 4  and full adders as shown in  FIG. 5 .  
     
    
     DETAILED DESCRIPTION  
       [0032]      FIGS. 2 through 6 , discussed below, and the various embodiments used to describe the principles of the present invention in this patent document are by way of illustration only and should not be construed in any way to limit the scope of the invention. Those skilled in the art will understand that the principles of the present invention may be implemented in any suitably arranged circuitry.  
         [0033]     The encoding, partial product generation, and addition stages of the multiplication circuits as known in the art are not described in further detail. For the examples described with reference to  FIGS. 2 and 3 , a compression column circuit is shown which receives the output from a Booth encoding algorithm, which generates 10 partial products. With reference to  FIG. 6 , a compression column circuit receives an output from a Booth encoding algorithm which generates 25 partial products.  
         [0034]     As appreciated by a person skilled in the art, the examples described below with reference to 10 and 25 term compression circuits are examples only, and compression circuits with columns capable of receiving any number of terms would be possible using the same techniques.  
         [0035]     Furthermore, although described as being a compression circuit for handling partial products from a Booth encoding algorithm, the present invention can be applied to the compression or addition of terms irrespective of their origin.  
         [0036]     As has been described previously and will be shown below, a product term compression circuit carries out the compression of the partial product terms in a series of compression stages. The compression circuit comprises a plurality of columns of compression cells, each column arranged in stages. Each compression stage of a column groups together bits of terms with the same weighting, compresses them, and passes them to the next compression stage.  
         [0037]     The bits of each term are input to compression cells where the bits are compressed to a smaller number of bits. Each compression stage of a column outputs at least one sum output with the binary weighting the same as the current column (i.e. 2 n ) and at least one carry output with the binary weighting one greater than the current column (i.e. 2 n+1 ). The outputs, where there are more than two of them, are passed to the next compression stage. Most of the current compression stage ‘sum’ outputs are passed to the next compression stage within the same column (i.e. 2 n ) and most of the current compression stage column carry outputs are passed to the next compression stage of a column with a binary weighting one greater than the current column (i.e. 2 n+1 ) Also, the compression stage within the same column is arranged to receive at least one of the current compression stage ‘carry’ outputs from a column with a binary weighting one less than the current column (i.e. 2 n−1 ).  
         [0038]      FIG. 2  shows three typical columns  291 ,  293 ,  295  of compression stages comprising full adder compression cells forming part of the compression circuit. Each column compresses 10 bits of the same weighting as described above. The central column  291  shown in  FIG. 2  is the compression column for bits with a binary weighting of 2 n . The left column  295  shown in  FIG. 2  is the compression column for the bits with a binary weighting of 2 n+1 . The right column  293  shown in  FIG. 2  is the compression column for the bits with a binary weighting of 2 n−1 . For simplicity, only the interactions between the central column  291  and the right and left columns  293  and  295  are described. However, it would be appreciated that the left and right columns comprise similar structures and perform similar interactions between themselves and their adjacent columns.  
         [0039]     The central column  291  shown comprises 5 compression stages. The central column first compression stage  201  receives 10 partial product terms  202   a , . . . ,  202   i  and outputs 7 terms. The central column first compression stage  201  comprises 3 full adders, each of which receives 3 partial product term bits. Each of the first compression stage adders outputs a sum bit, which is passed to the central column second compression stage  203 , and a carry bit  251 , which is passed to the left column second compression stage  233  (i.e. the column with a higher binary weighting 2 n+1 ). Similarly, the carry outputs  253  from the right column first compression stage  241  (i.e. from the column with a lower binary weighting 2 n−1 ) are passed to the central column second compression stage  203 . In this example, the number of carry output terms passing to the left column  295  (the adjacent column with a higher binary weighting) is equal to the number of carry outputs received from the right column  293  (the adjacent column with a lower binary weighting).  
         [0040]     The central column second compression stage  203  comprises 2 full adders compressing 6 received term bits (3 bits from the sum outputs of the central column first stage full adders and 3 bits from the carry outputs of the right column first compression stage  241  full adders i.e. the adjacent lower binary weighting column) to 5 terms. Each of the central column second stage full adders outputs a sum bit, which is passed to the central column third compression stage  205 , and a carry bit  255 , which is passed to the left column third compression stage  235  (i.e. to the adjacent column with a higher binary weighting).  
         [0041]     The central column third compression stage  205  comprises 2 full adders compressing the 5 terms received (2 bits from the sum outputs from the central column second stage  203  full adders, 2 bits from the right column second stage  243  carry outputs  257 , and 1 remaining partial product bit) to 4 terms. As there are only 5 bits for a possible 6 inputs, one input of one of the central column third compression stage two full adders is tied to ground to prevent any interference or noise propagation. Each of the central column third compression stage  205  full adders outputs a sum bit, which is passed to the central column fourth compression stage  207 . One of the central column third compression stage  205  full adders passes a carry bit  259   a  to the left column fourth compression stage  237 , and the other central column third compression stage  205  full adder passes a carry bit to the left column fifth compression stage  239 .  
         [0042]     The central column fourth compression stage  207  comprises a full adder compressing 3 received terms (2 bits from the sum outputs from the central column third stage  205 , and one bit  261  from a carry output from the right column third stage) to two terms. The central column fourth compression stage full adder outputs a sum bit, which is passed to the central column fifth compression stage  209 , and a carry bit  263 , which is passed to the left column fifth compression stage  239 .  
         [0043]     The central column fifth compression stage  209  comprises a full adder compressing 3 received terms (1 bit from the central column fourth stage  207  full adder, 1 bit from the remaining unused right column third compression stage carry output  265 , and 1 bit from the right column fourth compression stage carry output  267 ) to 2 terms. The central column fifth stage full adder outputs a sum bit, which is passed as the central column first output term  269 , and a carry bit  273 , which is passed to the left column to form one of the two output terms. The central column second output term  271  is the received carry output  275  from the right column fifth compression stage.  
         [0044]     Data passing through a circuit as shown in  FIG. 2  has to pass through 5 compression stages (the path taken by the input terms  202   a  to  202   i ). This creates a critical path delay through the compression circuit of 5 full adders. As the critical path through a known full adder circuit is two XOR gates, the total critical path is 10 logic gates. Furthermore, as all except the input  202   j  are required at essentially the same time, strict timing control of the circuitry driving the inputs is required.  
         [0045]     With reference to  FIG. 3 , an improved 10-bit compression column is shown. The compression column forms an improved compression circuit. As shown and described earlier, a compression column has adjacent compression columns (not shown in  FIG. 3  for clarity). The principle of the ‘carry’ inputs and outputs is the same for the improved circuit as for the traditional circuit. ‘Carry’ outputs from each of the shown compression column compression cells are passed to the compression column which compresses bits with a binary weighting higher than the shown compression column. Furthermore, the shown compression column receives ‘carry’ outputs from the adjacent compression column, which compresses bits with a binary weighting lower than the shown compression column. Although the adjacent columns are not shown, the interconnections between the columns are shown in  FIG. 3 .  
         [0046]     The improved compression column comprises 4 stages. In the first compression stage  501 , the 10 partial product terms are compressed to 6 terms. The first compression stage  501  comprises two 5:3 compression cells  401   a ,  401   b , each of which receives 5 partial product term bits.  
         [0047]     As will be described in more detail below, each 5:3 compression cell has 2 ‘early’ inputs and 3 ‘late’ inputs. The ‘late’ inputs are not required until after the ‘early’ inputs in order for the 5:3 compressor circuit to perform its task of compressing or adding the inputs to produce the output values. The output values are also produced at different times, with the ‘early’ outputs produced before the ‘late’ outputs. The 5:3 compression cell produces a ‘late’ sum output having the same binary weighting as the inputs, an ‘early’ carry output having a binary weighting one greater than the inputs, and a ‘late’ carry output also having a binary weighting one greater than the inputs.  
         [0048]     For the example described below, the partial product bits  502   a ,  502   b ,  502   e ,  502   f ,  5029 ,  502   j  are connected to the ‘late’ inputs of the two 5:3 compression cells, and the remainder of the bits  502   c ,  502   d ,  502   h ,  502   i  are connected to the ‘early’ inputs.  
         [0049]     The first compression stage 5:3 compression cells  401   a ,  401   b  output two sum bits  551   a ,  551   b  which are passed to the second compression stage  503 , two ‘early’ carry bits  552   a ,  552   b , and two ‘late’ carry bits  554   a ,  554   b . One ‘late’ carry bit  554   a  is passed to the higher binary weighting column (2 n+1 ) second compression stage (not shown), and the other ‘late’ carry bit  554   b  is passed to the higher binary weighting column third compression stage (not shown).  
         [0050]     The second compression stage  503  comprises a single 5:3 compression cell  401   c , compressing 5 received term bits (the first compression stage compression cell two sum bits  551   a ,  551   b , the two lower binary weighting compression column first compression stage ‘early’ carry bits, and one lower binary weighting compression column first compression stage ‘late’ carry bit) to three term bits. The two sum bits  551   a ,  551   b  and the ‘late’ carry bit are connected to the three ‘late’ inputs, and the two ‘early’ carry bits are connected to the two ‘early’ inputs.  
         [0051]     The second stage 5:3 compression cell  501   c  outputs a sum bit  555 , which is passed to the third compression stage  505 , and an ‘early’ carry bit  556  and a ‘late’ carry bit  558 , which are both passed to the higher binary weighting column third compression stage (not shown).  
         [0052]     The third compression stage  505  comprises a single 5:3 compression cell  401   d , compressing 4 received term bits (the second compression stage sum bit  555 , the remaining lower binary weighting compression column first compression stage ‘late’ carry bit, and the lower binary weighting compression column second compression stage ‘early’ and ‘late’ carry bits) to 3 term bits. The second stage sum bit  555 , the lower binary weighting compression column second compression stage ‘late’ carry bit, and a grounded signal are input as the three ‘late’ inputs. The ‘early’ inputs are formed from a bit from the remaining inputs, the lower binary weighting compression column first compression stage ‘late’ carry bit, and the lower binary weighting compression column second compression stage ‘early’ carry bit.  
         [0053]     The third stage 5:3 compression cell  401   d  outputs a sum bit  557 , which is passed to the fourth compression stage  505 , and an ‘early’ carry bit  562  and a ‘late’ carry bit  560  to the higher binary weighting compression column fourth compression stage (not shown).  
         [0054]     The fourth compression stage  507  comprises an improved full adder  351   c . The implementation of the improved full adder will be described in more detail below. The improved full adder  351   c  receives two ‘early’ inputs, which are the lower binary weighting compression column third compression stage ‘early’ and ‘late’ carry outputs (not shown). The improved full adder  351   c  receives a ‘late’ input from the third compression stage sum output  557 .  
         [0055]     The carry output  563  from the improved full adder  351   c  is passed to a higher binary weighting compression column (not shown) to form a first output bit term. The first output bit  556  for the shown column is received from the lower binary weighting compression column fourth compression stage carry output. The fourth compression stage improved full adder sum output  568  forms the second output bit.  
         [0056]     As can be seen from above and with reference to  FIG. 3 , the interconnections between stages are kept, as much as possible, so that an ‘early’ output from one stage is connected to an ‘early’ output from the following stage and similarly a ‘late’ output is connected to a ‘late’ input. By connecting stages together in this manner, the advantage in producing early signals and only requiring later inputs can be fully exploited to produce a reduction in data timing delay, which can also be seen in  FIG. 3  with respect to the partial tessellation of the compression cells.  
         [0057]     The improved compression column shown features a critical delay path of only 4 stages, which as shown in  FIG. 3  is a total delay of only 9 logic gates. Furthermore, the minimum logic path is only 7 gates long. This is a clear advantage over the conventional known circuit shown in  FIG. 2 , which has a critical delay path of 10 gates, i.e. 2 gates per full adder and 5 full adder stages. The shortest data path of the conventional structure is also slower than the improved column shown in  FIG. 3 , with the conventional structure shortest path having a minimum of 8 gates delay.  
         [0058]     A further advantage with the improved structure as shown in  FIG. 3  is that 6 of the 10 input bits are only required after the first 4 ‘early’ inputs. This allows the multiplier circuit designer using the improved compression columns in a compression circuit as part of a multiplier to design the Booth encoding circuitry knowing that over half of the input bits are not initially required and can be supplied at a later time.  
         [0059]     With reference to  FIG. 4 , a schematic view of an improved full adder  351  as used in embodiments of the present invention is described further. The full adder  351  comprises three inputs  353   a ,  353   b ,  353   c  and two outputs  355   s  (the sum output) and  355   c  (the carry output). The inputs  353   a  and  353   b  are input to a first XOR gate  301 , and the output of the first XOR gate  301  is input along with the third input c to the second XOR gate  303 . The second XOR gate  303  output is connected to the sum output ( 355   s ) of the full adder  351 . The first input  353   a  and the third input  353   c  are connected to the two inputs of a 2-bit multiplexer  305 . The selection input of the multiplexer  305  is connected to the output of the first XOR gate  301 . The output of the 2-bit multiplexer is arranged so that if the inputs  353   a  and  353   b  are the same, then the value of  353   a  is selected. However, if the inputs  353   a  and  353   b  are different, then the input of  353   c  is selected to be output. The 2-bit multiplexer output is connected to the carry output of the adder  351 .  
         [0060]     Furthermore, as shown schematically on the right hand side, the inputs  353   a  and  353   b  are ‘early’ inputs, and the input  353   c  is a ‘late’ input. In other words, the correct result is produced even when the input  353   c  is received after the inputs  353   a  and  353   b . In the example shown in  FIG. 4 , the input  353   c  can be received up to 1 gate period later than inputs  353   a  and  353   b  without any delay in producing the correct result.  
         [0061]     With reference to  FIG. 5 , a 5:3 compression cell  401  as used within the improved compression circuit column is shown. The 5:3 compression cell  401 , which is logically identical to a conventional 4:2 compression cell, comprises 2 improved full adders  351   a ,  351   b  as described previously with regard to  FIG. 4 . The 5:3 compression cell  401  comprises 5 inputs  403   a ,  403   b ,  403   c ,  403   d ,  403   e  and 3 outputs  405   s ,  405   c   1 ,  405   c   2 . The two improved full adders  351   a  and  351   b  are arranged such that the 5:3 compression cell input bits  403   a ,  403   b  are connected to the 2 ‘early’ inputs of the first improved full adder  351   a , the 5:3 compression cell input  403   c  is connected to the ‘late’ input of the first improved full adder  351   a , and the 5:3 compression cell inputs  403   d  and  403   e  are connected to the ‘early’ inputs of the second improved full adder  351   b.    
         [0062]     The carry output of the first improved full adder  351   a  forms the second carry output  405   c   2  of the 5:3 compression cell  401 . The sum output of the first improved full adder  351   a  is connected to the ‘late’ input of the second improved full adder  351   b . The sum and carry outputs of the second improved full adder  351   b  form the ‘late’ sum output  405   s  and the ‘late’ carry output  405   c   1  of the 5:3 compression cell  401 .  
         [0063]     This 5:3 compression cell  401  has a first advantage over a conventional 5:3 or 4:2 compression cell wherein two of the five inputs are required before the remaining three of the inputs. This as shown above enables an optimisation of the compression circuit.  
         [0064]     Furthermore, one of the carry outputs  405   c   2  is produced “early” when compared to the other two outputs. Thus, this ‘early’ production also allows an optimisation of the data flow through a compression circuit as shown above.  
         [0065]     Furthermore, the path from  403   a ,  403   b  to  405   c   1 , the critical path, is through two improved full adders and has a delay of three logic gates. A traditional structure 4:2 or 5:3 compression cell comprising two full adders typically passes through two complete full adders with a critical delay path of 4 gates.  
         [0066]     With regards to  FIG. 6 , a further example of the improved compression column structure is shown. The example shown in  FIG. 6  compresses 25 term bits to produce a 2 term bit output. Once again, the principles of adjacent columns and the passing and receiving of the ‘carry’ outputs between columns are the same as the previous examples described earlier. To further simplify the circuit in this example, the adjacent columns and the interconnects between the columns defining the explicit passing of carry terms bits will not be described in further detail.  
         [0067]     The column comprises five stages of compression. The first stage  601  comprises five 5:3 compression cells as described previously. The first stage  601  compresses 25 term bits to produce 5 early term bits and 10 late term bits.  
         [0068]     The second stage  603  comprises three 5:3 compression cells. The second stage receives 5 ‘early’ inputs with the remaining unused ‘early’ input tied to ground and 9 ‘late’ inputs and compresses these to produce 3 early outputs and 6 late outputs.  
         [0069]     The third stage  605  comprises two 5:3 compression cells. The third stage  605  accepts 3 ‘early’ inputs and 6 ‘late’ inputs from the second stage  603  with the final ‘early’ input from the unused ‘late’ output from the first stage  601 . The third stage produces 2 ‘early’ outputs and 4 ‘late’ outputs.  
         [0070]     The fourth stage  607  comprises 2 improved full adders and receives 4 ‘early’ inputs and 2 ‘late’ inputs to produce 4 outputs.  
         [0071]     The fifth stage  609  comprises two separate improved full adders. The fifth stage  609  first improved full adder receives three inputs from the fourth stage  607 . The fifth stage second improved full adder receives the sum output of the first full adder, the carry input from the adjacent lower weighting column, and the remaining carry output from an adjacent lower weighting fourth stage improved full adder (not shown).  
         [0072]     The fifth stage  609  second improved full adder produces the sum and carry outputs following weighting rearrangement of the outputs.  
         [0073]     As can be seen in  FIG. 6 , the addition of 25 terms has only a maximum logic delay of 11 gates and a minimum of 10. The conventional compression column structure required data to be passed through a maximum of 7 full adders (with a maximum logic delay of 14 gates and a minimum of 13 gates). It can therefore be seen that the improvement in terms of critical path delay is apparent for large numbers of terms, and also appears to increase as the number of input terms increases.  
         [0074]     It is intended that the present invention encompass such changes and modifications as fall within the scope of the appended claims.