Abstract:
An integrated multiplier circuit includes an array of one-bit adders, organized into a plurality of stages with a plurality of bit positions in each stage. Each one-bit adder has a carry input terminal and a pair of addend input terminals, and receives a carry signal and two addend signals. The carry signal is normally generated in the preceding bit position in the preceding stage of the array, and is received at the carry input terminal, but if the carry signal arrives with less delay than one of the two addend input signals, it is input at the corresponding addend input terminal, and the more delayed addend input signal is input at the carry input terminal. This input arrangement reduces the total time needed to complete a multiplication operation.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a high-speed multiplier circuit in which a plurality of one-bit adders are connected in an array and operate simultaneously so that addition is performed in different bit positions in a temporally overlapping manner. More particularly, the invention relates to a method of increasing the multiplication speed by changing the interconnections of the one-bit adders.  
           [0003]    2. Description of the Related Art  
           [0004]    It is known that multiplication can be performed by logic circuits: for example, by a multiplier circuit comprising a single adder, a plurality of registers (for storing the multiplicand, the multiplier, the product, etc.), and a control circuit for shifting bit positions. It is also known that when the multiplier circuit is implemented in an integrated circuit, the multiplication operation can be carried out at a higher speed by using an array of one-bit adders that perform addition in different bit positions in a temporally overlapping manner. In this type of multiplier, each adder in the array receives a pair of addends (conventionally denoted x and y) and a carry input signal (c-in), and generates a sum signal (s) and a carry output signal (c-out)  
           [0005]    In general, in any circuit that performs an arithmetic or logic operation, the operation is accompanied by a certain temporal delay. This is also true of an adder. In a multiplier circuit comprising an array of adders, the delays generated by the individual adders add up so that the completion of the multiplication is delayed by an even greater amount.  
           [0006]    The delays add up because even if the adders perform multiplication in a temporally overlapping manner, when an operation (addition) is performed in an upper bit position or a later stage of the array, it is necessary to wait for a carry signal from the preceding bit position or a sum signal from the preceding stage of the array, or in many cases for both of these signals. In a multiplier circuit comprising an array of one-bit adders, each additional adder entails an additional wait, so the total delay increases toward higher bit positions, and toward later stages in the array. The speed of an integrated multiplier circuit is therefore normally determined by the delay of the adder in the highest bit position in the last stage of the array.  
           [0007]    The one-bit adders in the array can be interconnected in various ways. FIG. 6 shows the structure of a conventional multiplier circuit with an array of the carry save type.  
           [0008]    The multiplier (a) is a five-bit binary number comprising bits a 0 , a 1 , a 2 , a 3 , a 4 , of which a 0  is the least significant bit (LSB). The multiplicand (b) is another five-bit binary number comprising bits b 0 , b 1 , b 2 , b 3 , b 4 , of which b 0  is the LSB. The product (z) is a ten-bit binary number comprising bits z 0  (the LSB), z 1 , z 2 , z 3 , z 4 , z 5 , z 6 , z 7 , z 8 , z 9 .  
           [0009]    The multiplier circuit in FIG. 6 has five stages with four adders each. The five stages correspond to bits b 1 -b 4 , with one additional final stage. The twenty adders are denoted F(i), where i is a positive integer. Adder F(i) receives addend bits x(i) and y(i) and a carry signal c(i)-in as inputs, and generates a sum bit s(i) and a carry signal c(i)-out as outputs. The first adder F( 1 ), for example, has the following inputs: 
             x ( 1 )= a ( 1 )* b ( 0 ) 
             y ( 1 )= a ( 0 )* b ( 1 ) 
             c ( 1 )=0 
           [0010]    For brevity, F(i), x(i), y(i), s(i), and c(i)-in are denoted Fi, xi, yi, si, and ci in FIG. 6. The notations with and without parentheses will be used interchangeably below.  
           [0011]    Each one-bit adder F(i) has, for example, the structure shown in FIG. 7, comprising two logical exclusive-OR gates (EX-OR1, EX-OR2), two logical AND gates (AND1, AND2), and one logical OR gate (OR). The EX-OR1 logic gate receives addends x(i) and y(i), performs a logical exclusive OR operation, and supplies the result to the EX-OR2 and AND2 logic gates. The EX-OR2 logic gate receives the result output from EX-OR1 and the carry input signal c(i)-in, performs a logical exclusive OR operation, and outputs the sum s(i). The AND1 logic gate receives addends x(i) and y(i), performs a logical AND operation, and supplies the result to the OR logic gate. The AND2 logic gate receives the result output from the EX-OR1 logic gate and the carry input signal c(i)-in, performs a logical exclusive OR operation, and supplies the result to the OR logic gate. The OR logic gate receives the results output from the AND1 and AND2 logic gates, performs a logical OR operation, and outputs the result as the carry output signal c(i)-out.  
           [0012]    In comparison with the AND1, AND2, and OR logic gates, the logical exclusive-OR gates EX-OR1 and EX-OR2 require a longer time to perform a logical operation on the input values and to output the result. The required time is referred to below as a delay. In the subsequent description, the delay of the AND1, AND2, and OR gates is assumed to be 1t while the delay of EX-OR1 and EX-OR2 is assumed to be 2t.  
           [0013]    The path from x(i) to s(i) accordingly has a 4t delay. The path from y(i) to s(i) also has a 4t delay. The paths from c(i)-in to s(i), from x(i) to c(i)-out, from y(i) to c(i)-out, and from c(i)-in to c(i)-out have a 2t delay. The path with the longest delay in a circuit is referred to as the critical path.  
           [0014]    Adder F 1  in FIG. 6 outputs a sum s 1  with a 4t delay (the critical-path delay within the adder), and outputs a carry signal c 5  with a 2t delay. The carry output signal c 5  becomes a carry input signal to adder F 5 . Adder F 2  outputs a sum s 2  with a 4t delay (the critical-path delay within the adder), and outputs a carry signal c 6  with a 2t delay.  
           [0015]    Adder F 5  receives addends x 5  and y 5 , of which x 5  has a 4t input delay, and carry signal c 5  with a 2t input delay, and outputs a sum s 5  and a carry signal c 9  with longer delays. The delay of s 5  is the sum of the 4t input delay of addend x 5  and the critical-path delay in the adder F 5 , or 8t in total. The delay of the carry output signal c 9  is the sum of the 4t delay of the addend x 5  and the delay of the carry signal in the adder F 5 , or 6t in total. In the subsequent description, the delay of a signal means the delay on the critical path for that signal, unless otherwise specified.  
           [0016]    [0016]FIG. 8 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 6. Because the adders in each stage generate additional delays, the final delay Z 0  of the output of adder F 20 , which produces the most significant bit in the final stage, is 28t, as indicated in FIGS. 6 and 8. This 28t delay is the time that the multiplier circuit F(i) requires to complete the multiplication operation.  
         SUMMARY OF THE INVENTION  
         [0017]    An object of the present invention is to increase the speed of an integrated multiplier circuit.  
           [0018]    The invented integrated multiplier circuit, like the conventional integrated multiplier circuit described above, comprises an array of one-bit adders, organized into a plurality of stages with a plurality of bit positions in each stage. Each one-bit adder has a carry input terminal and a pair of addend input terminals, and receives a carry input signal and two addend input signals.  
           [0019]    In the second and subsequent stages of the array, the carry input signal is normally generated as a carry output signal in the preceding bit position in the preceding stage of the array. In at least one adder, however, this carry output signal is received with less delay than one of the addend input signals, and is interchanged with that addend input signal. That is, the carry output signal from the preceding bit position in the preceding stage is brought to an addend input terminal, and what would otherwise have been an addend input signal is brought to the carry input terminal.  
           [0020]    Since the carry input to an adder is processed with less internal delay than the addend inputs, the invention reduces the maximum delay of the signals output from the adder. As a result, the multiplication operation is completed in less time than required by the conventional integrated multiplier circuit.  
           [0021]    The invention also provides a method of interconnecting the one-bit adders in an integrated multiplier circuit of the above general type, in which each adder has three input terminals, one of the three inputs is processed with less internal delay than the other two inputs, and each interconnection is from an adder in one stage to an adder in either a later stage or a higher bit position in the same stage. The adders are considered one by one, preceding from the first stage to the last stage of the array and from the lowest bit position to the highest bit position in each stage. The delays of the three signals received by the adder under consideration are compared, and if one of the three signals is received with a greater delay than the other two signals, it is connected to the input terminal having the least internal processing delay. Then the delays of the signals output from the adder under consideration are calculated. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0022]    In the attached drawings:  
         [0023]    [0023]FIG. 1 is a truth table describing the operation of adder circuits used in the present invention;  
         [0024]    [0024]FIG. 2 is a block diagram of a multiplier circuit comprising an array of one-bit adders, illustrating a first embodiment of the invention;  
         [0025]    [0025]FIG. 3 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 2;  
         [0026]    [0026]FIG. 4 is a block diagram of a multiplier circuit comprising an array of one-bit adders, illustrating a second embodiment of the invention;  
         [0027]    [0027]FIG. 5 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 4;  
         [0028]    [0028]FIG. 6 is a block diagram of a conventional multiplier circuit comprising an array of one-bit adders;  
         [0029]    [0029]FIG. 7 shows the internal logic structure of a one-bit adder; and  
         [0030]    [0030]FIG. 8 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 6. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0031]    Embodiments of the invention will now be described with reference to the attached drawings, in which like elements are indicated by like reference characters.  
         [0032]    First, the operation of an adder will be described with reference to the truth table in FIG. 1. This truth table applies in general to the adders used in integrated circuits, including, for example, any one of the adders F(i) in the conventional array shown in FIG. 6. As was shown in FIG. 7, adder F(i) has input terminals for a pair of addends x(i), y(i) and a carry input signal c(i)-in generated by an operation in the preceding bit position, and has output terminals for a carry output signal c(i)-out, which is used in the addition operation performed in the next higher bit position, and the sum s(i). The logic values at these input and output terminals are indicated in separate columns in FIG. 1.  
         [0033]    The first row (L 1 ) in FIG. 1 indicates that when the input values are x(i)=0, y(i)=0, and c(i)-in=0, the output values are s(i)=0 and c(i)-out=0. The last or eighth row (L 8 ) in FIG. 1 indicates that when the input values are x(i)=1, y(i)=1, and c(i)-in=1, the output values are s(i)=1 and c(i)-out=1. That is, when the three input values are all 0, the two output values are both 0, and when the three input values are all 1, the two output values are both 1.  
         [0034]    The remaining rows (L 2  to L 7 ) in FIG. 1 cover the other two output combinations: s(i)=1 and c(i)-out=0; and s(i)=0 and c(i)-out=1. As these rows show, when the three input values are not identical, the two output values are different.  
         [0035]    The second row (L 2 ), third row (L 3 ), and fifth row (L 5 ) in FIG. 1 indicate three different input combinations that yield a single output combination: s(i)=1 and c(i)-out=0 (condition 1). The fourth row (L 4 ), sixth row (L 6 ), and seventh row (L 7 ) indicate three other input combinations that yield another single output combination: s(i)=0 and c(i)-out=1 (condition 2).  
         [0036]    In any row, it is possible to interchange any two of the inputs without changing the combination of output values. This implies that even if the corresponding input terminals are interchanged in one or more of the adders in the conventional multiplier circuit  6 , the sum and carry output signal will not change.  
         [0037]    For example, L 2  and L 5 , which show the same output combination in FIG. 1, both have addend y(i)=0, but L 2  has addend x(i)=0 and carry input signal c(i)-in=1, whereas L 5  has addend x(i)=1 and carry input signal c(i)-in=0. The sum and carry output signals of this adder will not change if the input terminals for addend x(i) and carry input signal c(i)-in are interchanged.  
         [0038]    Similarly, L 1  and L 6  in FIG. 1 both have addend y(i)=0, but the two other input values (addend x(i) and carry input signal c(i)-in) are both 0 in L 1  and both 1 in L 6 . Because these two input values are the same, interchanging the input terminals for addend x(i) and carry input signal c(i)-in will, of course, not affect the sum and carry output signals.  
         [0039]    The examples given above indicate that the input terminals for addend x(i) and carry input signal c(i)-in are interchangeable when addend y(i)=0. The examples given below will indicate that the input terminals for addend x(i) and carry input signal c(i)-in are also interchangeable when addend y(i)=1.  
         [0040]    L 4  and L 7 , which show the same output combination in FIG. 1, both have addend y(i)=1, but L 4  has addend x(i)=0 and carry input signal c(i)-in=1, whereas L 7  has addend x(i)=1 and carry input signal c(i)-in=0. The sum and carry output signals accordingly will not change if the input terminals for addend x(i) and carry input signal c(i)-in are interchanged.  
         [0041]    L 3  and L 8  in FIG. 1 also have addend y(i)=1, but the two other input values (addend x(i) and carry input signal c(i)-in) are both 0 in L 3  and both 1 in L 8 . Because these two input values are the same, interchanging the input terminals for addend x(i) and carry input signal c(i)-in will, of course, not affect the sum and carry output signal.  
         [0042]    Therefore, if the input terminals for addend x(i) and carry input signal c(i)-in of an adder F(i) in the conventional multiplier circuit shown in FIG. 6 are interchanged, then in the truth table shown in FIG. 1, L 2  and L 5  are mutually interchanged, and L 4  and L 7  are mutually interchanged. However, the sum and carry output signals indicated in the truth table do not change. In other words, the result of multiplication by the multiplier circuit is unaffected even if the input terminals for addend x(i) and carry input signal c(i)-in of an adder F(i) are interchanged (condition 3).  
         [0043]    It has been explained above that the input terminals for addend x(i) and carry input signal c(i)-in are. interchangeable both when addend y(i)=0 and when addend y(i)=1. It will be shown below that the input terminals for addend y(i) and carry input signal c(i)-in are interchangeable both when addend x(i)=0 and when addend x(i)=1.  
         [0044]    L 2  and L 3 , which show the same output combination in FIG. 1, both have addend x(i)=0, but L 2  has addend y(i)=0 and carry input signal c(i)-in=1, whereas L 3  has addend y(i)=1 and carry input signal c(i)-in=0. The sum and carry output signals therefore will not change if the input terminals for addend y(i) and carry input signal c(i)-in are interchanged.  
         [0045]    L 1  and L 4  in FIG. 1 also have addend x(i)=0, but the two other input values (addend y(i) and carry input signal c(i)-in) are both 0 in L 1  and both 1 in L 4 . Because these two input values are the same, interchanging the input terminals for addend x(i) and carry input signal c(i)-in will, of course, not affect the sum and carry output signal.  
         [0046]    The examples given above indicate that the input terminals for addend y(i) and carry input signal c(i)-in are interchangeable when addend x(i)=0. The examples given below will indicate that the input terminals for addend y(i) and carry input signal c(i)-in are also interchangeable when addend x(i)=1.  
         [0047]    L 6  and L 7 , which show the same output combination in FIG. 1, both have addend x(i)=1, but L 6  has addend y(i)=0 and carry input signal c(i)-in=1, whereas L 7  has addend y(i)=1 and carry input signal c(i)-in=0. The sum and carry output signals will therefore not change if the input terminals for addend y(i) and carry input signal c(i)-in are interchanged.  
         [0048]    L 5  and L 8  in FIG. 1 also have addend x(i)=1, but the other input values (addend y(i) and carry input signal c(i)-in) are both 0 in L 5  and both 1 in L 8 . Because these two input values are the same, interchanging the input terminals for addend x(i) and carry input signal c(i)-in will, of course, not affect the sum and carry output signal.  
         [0049]    Therefore, if the input terminals for addend y(i) and carry input signal c(i)-in of an adder F(i) in the conventional multiplier circuit shown in FIG. 6 are interchanged, L 2  and L 3  are mutually interchanged, and L 6  and L 7  are mutually interchanged in the truth table shown in FIG. 1. However, the sum and carry output signals indicated in the truth table do not change. In other words, the results of multiplication by the multiplier circuit are not affected even if the input terminals for addend y(i) and carry input signal c(i)-in of an adder F(i) are interchanged (condition 4).  
         [0050]    From condition 3, the result of multiplication by a multiplier circuit is not affected even if the input terminals for addend x(i) and carry input signal c(i)-in of an adder F(i) are interchanged, and from condition 4, the result of multiplication by the multiplier circuit is not affected even if the input terminals for addend y(i) and carry input signal c(i)-in of an adder F(i) are interchanged. It follows that the sum generated by any adder F(i) in the conventional multiplier circuit shown in FIG. 6 is not affected even if the input terminals for addend x(i) and carry input signal c(i)-in or the input terminals for addend y(i) and carry input signal c(i)-in are interchanged (condition 5).  
         [0051]    The delay in each adder F(i) differs depending on the path taken from input to output, as shown in FIG. 7. The paths from the input of addends x(i) and y(i) leading through two comparatively complex logic operations to the output of sum s(i) both have a 4t delay, while the path from the input of carry input signal c(i)-in leading through only one of these logic operations to the output of sum s(i) has a 2t delay. The paths from the input of addends x(i) and y(i) leading through two comparatively simple operations to the output of carry signal c(i)-out have a 2t delay. The path from the input of carry input signal c(i)-in leading through similar simple logic operations to the output of carry signal c(i)-out also has a 2t delay. As will be described below, the present invention exploits the fact that the 2t delay of the path from the input of carry input signal c(i)-in to the output of the sum s(i) is only half of the 4t delay of the paths from the input of addends x(i) and y(i) to the output of sum s(i).  
         [0052]    The conventional multiplier circuit shown in FIG. 6 will next be studied further, together with the conditions described above and the difference in delays indicated in FIG. 7. The final delay Z 0  of adder F 20  generating sum s 20  and carry output signal c 24  is 28t, as indicated in FIG. 6. In a multiplication operation, operations are carried out in ascending order of bit position, and a carry output signal from a given bit position is output to the next higher bit position. Therefore, the delays of individual adders in the multiplier circuit will be compared and studied in ascending order of stage and bit position, or in ascending order of bit position in the multiplier and multiplicand.  
         [0053]    In the first stage, adders F 1  to F 4  receive carry input signal c(i)-in=0, and output sums s 1  to s 4  with a 4t delay and carry output signals c 5  to c 8  with a 2t delay, as shown in FIG. 8.  
         [0054]    Adders F 5  to F 7  in the next stage receive addends x 5  to x 7  with a 4t delay and carry input signals c 5  to c 7  with a 2t delay, as generated by the adders in the preceding stage. For adders F 5  to F 7 , the delay of the carry input signal c(i)-in is smaller than the delay of the input addend x(i). Adders F 5  to F 7  output sums s 5  to s 7  with an 8t delay and carry signals c 9  to c 11  with a 6t delay, as indicated in FIG. 6. Adder F 8  in the same stage receives addend x 8  without delay and carry signal c 8  with a 2t delay. Because the delay of the addend is smaller than the delay of the carry input signal, the corresponding input terminals will not be interchanged.  
         [0055]    If the input terminals for addends x 5  to x 7  and the input terminals for carry input signals c 5  to c 7  are interchanged in adders F 5  to F 7  because of the differences in delay indicated in FIG. 7, under the conditions described above, adders F 5  to F 7  will output sums s 5  to s 7  with a 6t delay and carry output signals c 9  to c 11  with a 6t delay. The delay of sums s 5  to s 7  is reduced from 8t to 6t by interchanging the input terminals.  
       First Embodiment  
       [0056]    [0056]FIG. 2 is a block diagram of a multiplier circuit comprising an array of one-bit adders, illustrating a first embodiment of the invention. FIG. 3 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 2.  
         [0057]    Elements in FIGS. 2 and 3 having the same function as elements in the conventional multiplier circuit shown in FIGS. 6 and 8 are indicated by identical reference characters; redundant descriptions will be omitted. The delays of the following inputs are all zero: addends x 1  to x 4 , x 8 , x 12 , x 16 , x 20 , and y 1  to y 17 , and carry input signals c 1  to c 4 . Some delays have been reduced by interchanging the input terminals as described above. The reduced delays are italicized in FIG. 2.  
         [0058]    In the first embodiment, the input terminals of addend x(i) and carry input signal c(i) are interchanged in some cases to reduce the delay.  
         [0059]    The first embodiment illustrated in FIG. 2 differs from the prior art illustrated in FIG. 6 in that the input terminals for addends x 5  to x 7  and the input terminals for carry input signals c 5  to c 7  are interchanged in adders F 5  to F 7 , and the input terminals for addend x 13  and carry input signal c 13  of adder F 13  are interchanged. In other respects, the first embodiment is configured in the same manner as the prior art illustrated in FIG. 6.  
         [0060]    Box A in FIG. 2 indicates that the input terminals for addends x 5  to x 7  and the input terminals for carry input signals c 5  to c 7  are interchanged in adders F 5  to F 7 .  
         [0061]    In the third stage, adders F 9  and F 10  receive addends x 9  and x 10  with a 6t delay, which has been reduced by interchanging the input terminals for addends x 5  to x 7  and the input terminals for carry input signals c 5  to c 7  in adders F 5  to F 7 , as indicated in box A of FIG. 2. Because this delay is the same as the 6t delay of carry input signals c 9  and c 10 , the corresponding input terminals do not need to be interchanged. Adder F 11  receives addend x 11  with a 4t delay and carry input signal c 11  with a 6t delay. Because the delay of addend x 11  is not larger than the 6t delay of the carry input signal c 11 , the corresponding input terminals do not need to be interchanged. Adder F 12  receives addend x 12  without delay and carry input signal c 12  with a 4t delay. Because the delay of the carry input signal is longer, the input terminals do not need to be interchanged.  
         [0062]    In the fourth stage, adder F 13  receives addend x 13  with a 12t delay and carry input signal c 13  with a 10t delay, from the adders in the preceding stage. Because the delay of addend x 13  is larger than the delay of carry input signal c 13 , the corresponding input terminals have been interchanged, as indicated in box B in FIG. 2.  
         [0063]    Adder F 14  in the fourth stage receives addend x 14  with an 8t delay and carry input signal c 14  with an 8t delay. Because the delays are the same, the corresponding input terminals do not need to be interchanged. Adder F 15  receives addend x 15  with a 6t delay and carry input signal c 15  with an 8t delay. Because the delay of addend x 15  is smaller than the delay of carry input signal c 15 , the corresponding input terminals do not need to be interchanged. Adder F 16  receives addend x 16  without delay and carry input signal c 16  with a 6t delay. Because the delay of the carry output signal is larger, the input terminals need not be interchanged.  
         [0064]    In the last stage, adder F 17  receives addend x 17  with a 12t delay and carry input signal c 17  with a 12t delay, and adder F 18  receives addend x 18  with a 10t delay and carry input signal c 18  with a 10t delay. Because the delays are the same, the corresponding input terminals do not need to be interchanged. Adder F 19  receives addend x 19  with an 8t delay and carry input signal c 19  with a 10t delay. Because the delay of addend x 19  is smaller than the delay of the carry input signal, the corresponding input terminals do not need to be interchanged. Adder F 20  receives addend x 20  without delay and carry input signal c 20  with an 8t delay. Because the delay of the carry input signal is larger, the input terminals do not need to be interchanged.  
         [0065]    As a result of interchanging the input terminals for addend x(i) and carry input signal c(i)-in of adders F 5  to F 7  and F 13 , the delay of the carry output signals c 21  to c 24  of adders F 17  to F 20  can be reduced by 2t, and the delay of the sum signals s 18  to s 20  output from adders F 18  to F 20  can be reduced by 2t. The final delay Z 1  of the multiplier shown in FIG. 2 becomes 26t, which is 2t smaller than the 28t delay of the conventional multiplier indicated in Z 0  of FIG. 6.  
         [0066]    In the integrated multiplier circuit of the first embodiment, a plurality of one-bit adders are disposed in an array with a plurality of stages and a plurality of bit positions, so that the bits of the multiplier and multiplicand are input to different adders in positional sequence, and each adder outputs a sum to the adder in the same bit position in the next stage and a carry signal to the adder in the next-higher bit position of the next stage. If the delay of the sum generated by an adder of the preceding stage is larger than the delay of the carry signal generated by the adder in the next-lower bit position of the preceding stage, the input terminals for the sum and carry signal are interchanged. In order to determine whether the input terminals for the sum and carry signal should be interchanged, the delays of the sum and carry signal input to each adder are compared in ascending order of bit position of the multiplier and multiplicand. The delay of this integrated multiplier circuit is thereby reduced.  
       Second Embodiment  
       [0067]    In the first embodiment described above, the delay of the integrated multiplier circuit was reduced by interchanging the input terminals for addend x(i) and carry input signal c(i)-in of some one-bit adders. The input terminals for addend y(i) and carry input signal c(i) could also be interchanged, but in almost all cases, specifically in adders F 1  to F 17 , this is not necessary, because the delays of addends y 1  to y 17  are all zero, and thus do not exceed the delay of the carry input signal c(i)-in.  
         [0068]    In the second embodiment, the delay is further reduced by interchanging the input terminals for addend y(i) and carry input signal c(i)-in of adders F 18  to F 20 .  
         [0069]    [0069]FIG. 4 is a block diagram of a multiplier circuit comprising an array of one-bit adders, illustrating the second embodiment of the invention. FIG. 5 lists the inputs and outputs of the adders in the multiplier circuit shown in FIG. 4.  
         [0070]    The second embodiment illustrated in FIGS. 4 and 5 differs from the first embodiment illustrated in FIGS. 2 and 3 in that the input terminals for addends y 18  to y 20  and the input terminals for carry input signals c 18  to c 20  are interchanged in adders F 18  to F 20 , as indicated in box C of FIG. 4.  
         [0071]    Adder F 18  receives addend y 18  with a 14t delay and carry input signal c 18  with a 10t delay. Because the 14t delay of addend y 18  is larger than the 10t delay of carry input signal c 18 , the corresponding input terminals are interchanged to reduce the delay in adder F 18 . The delays of carry signal c 22  and sum s 18  output from adder F 18  with interchanged input terminals are reduced by 2t and 4t respectively, in comparison with the first embodiment.  
         [0072]    Adder F 19  receives addend y 19  with a 16t delay and carry input signal c 19  with a 10t delay. Because the 16t delay of addend y 19  is larger than the 10t delay of carry input signal c 19 , the corresponding input terminals are interchanged to reduce the delay in adder F 19 . The delays of carry output signal c 23  and sum s 19  output from adder F 19  with interchanged input terminals are both reduced by 4t, in comparison with the first embodiment.  
         [0073]    Adder F 20  receives addend y 20  with an 18t delay and carry input signal c 20  with an 8t delay. Because the 18t delay of addend y 20  is larger than the 8t delay of carry input signal c 20 , the corresponding input terminals are interchanged to reduce the delay in adder F 20 . The delays of carry output signal c 24  and sum s 19  output from adder F 20  with interchanged input terminals are both reduced by 6t, in comparison with the first embodiment.  
         [0074]    In the integrated multiplier circuit of the second embodiment, a plurality of one-bit adders are disposed in an array with a plurality of stages and a plurality of bit positions, so that the bits of the multiplier and multiplicand are input to different adders in positional sequence, and each adder outputs a sum to the adder (if any) in the same bit position in the next stage and a carry signal to the adder in the next-higher bit position of the next stage. Each adder thus receives sum and carry signals from adders in the preceding stage. Normally the sum signal is received at an addend input terminal and the carry signal at a carry input terminal, but if the carry signal is received with less delay than the sum signals, the two input terminals are interchanged, thereby reducing the total critical-path delay, as in the first embodiment.  
         [0075]    The carry signal from an adder in the final stage is routed to the adder in the next-higher bit position in the same final stage. Thus a typical adder in the final stage receives the carry signal generated by the adder in the next-lower bit position of the preceding stage and the carry signal generated by the adder in the next-lower bit position in the final stage. Normally, the carry signal from the preceding stage is brought to the carry input terminal and the carry signal from the final stage is brought to an addend input terminal of the adder, but if the delay of the carry signal from the preceding stage is less than the delay of the carry signal from the final stage, these two input terminals are interchanged. In order to determine whether these two inputs should be interchanged, the delays of the carry signals input to the adders are compared in ascending order of bit position of the multiplier and multiplicand. The critical-path delay of the integrated multiplier circuit is thereby further reduced.  
         [0076]    The adders in the first and second embodiments may have the internal logic structure indicated as an example in FIG. 7, or a different internal logic structure. FIGS. 2 and 4 indicate exemplary circuits for a five-bit multiplier, but the invented multiplier can have any number of bits. In the embodiments described above with reference to FIGS. 2 and 4, the input terminals of adders F 5  to F 7 , F 13 , and F 18  to F 20  are interchanged, but the adders may be configured in a different manner, depending on the bit configuration, and the input terminals of adders in different bit positions may be interchanged on the basis of comparisons between the delays of either addend and the carry input signal.  
         [0077]    The scope of the invention should accordingly be determined from the appended claims.