JPH05289851A - Multiplier - Google Patents

Abstract

(57) [Summary] [Purpose] When a product of two data is obtained, a multiplication device for obtaining a final product by obtaining some partial products and adding the partial products In order to speed up the multiplication, the carry propagation in step 2 is performed quickly. [Constitution] The CPA circuit in the partial product arithmetic circuits 120, 130, 140 composed of the CSA circuit and the CPA circuit is divided into a plurality of parts, and the partial products are calculated in the form of partial sum and carry,
The final products are obtained by adding them by the partial product adding circuits 150 and 160.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiplication device for obtaining a final product by obtaining several partial products of two data when obtaining the product of the data.

When the number of digits of multiplication handled by the multiplication device is large, it is necessary to consider the carry propagation time in the operation of partial sum in order to speed up the multiplication.

[0003]

2. Description of the Related Art FIG. 6 is an explanatory view of a conventional general multiplication logic. Conventionally, in the multiplication of the multiplicand X and the multiplier Y, as shown in FIG.
H, YH and lower XL, YL are divided into partial products Z1,
A method is used in which Z2, Z3, and Z4 are obtained, and then, for each partial product, addition is performed according to each weight to obtain a final product Z.

FIG. 7 shows a general example of a multiplication device which uses this logic and has 8 bytes for each input. This multiplication device is roughly composed of partial product arithmetic circuits 710, 720, 730 and 740 and a partial product addition circuit 750. The partial product calculation circuit is composed of multiple generation circuits 711, 721, 731, 741.
And a 3-input carry save adder circuit (CSA: Carry Save
Adder) 712, 722, 732, 742 and carry propagation adder circuit (CPA: Carry Propagate Adder) of 2 inputs
) 713, 723, 733, 743.

The partial product adder circuit is composed of a 3-input carry save adder circuit (CSA) 751 and a 2-input carry propagation adder circuit (CPA) 752.
The final product is calculated by adding three inputs with a width of 16 bytes.
In addition, these CPAs are based on leading carry systems (CLA:
Carry Look Ahead) is adopted to speed up the calculation.

The multiplication of the input 8 bytes by the multiplication device shown in FIG. 7 is performed as follows. First, the input data is divided into X and Y, and the partial product operation circuits 710 and 72 are divided.
0,730,740. Partial product arithmetic circuit 710
The data sent to the
It is sent to the SA circuit 712 and added by the CPA circuit 713 to obtain the partial product Z1. Z2, Z3 and Z4 are similarly obtained in the partial product arithmetic circuits 720, 730 and 740.

Next, the obtained four partial products are sent to the partial product addition circuit 750. In the partial product addition circuit 750, each partial product is added in the CSA circuit 751 and further in the CPA circuit 752 according to its weight, and the final product Z
Is calculated and stored in the result register 770.

When the multiplication device is actually formed into an LSI,
Due to the degree of integration of the LSI and the limitation of the number of input / output pins, it is difficult to configure the entire LSI with one LSI. for that reason,
It is necessary to divide it into several blocks and configure it with multiple LSIs.

FIG. 8 shows a structure in which the partial product arithmetic circuits are each composed of one LSI, and the partial product addition circuits are composed of two LSIs, that is, a total of six LSIs. LSI1, LSI
2, LSI3 and LSI4 are partial product calculation circuits, and calculate partial products Z1, Z2, Z3 and Z4, respectively. LSI
5, LSI6 is a partial product addition circuit, which performs addition of upper 8 bytes and lower 8 bytes for obtaining the final product 16 bytes.

Since this multiplication device handles 8-byte data, each input / output pin of the LSI has a partial product calculation circuit 71.
In 0 to 740, there are 64 input pins and 64 output pins, and in the partial product addition circuit 850 that receives these inputs, 128 input pins, 64 output pins, and partial product conversion circuit 86.
As for 0, at least 128 input pins and 64 output pins are required.

[0011]

However, when such a configuration is used, when adding partial products,
By the addition in the partial product arithmetic circuit 720, the carry is propagated by 8 bytes in the CPA circuit 723 and then by 4 bytes in the partial product addition circuit 750. That is, the carry propagates as indicated by CP2 in FIG. The same applies to the partial product calculation circuit 730. How fast the carry is propagated in this partial product addition leads to a reduction in the calculation time in this multiplication device.

The present invention focuses on this point, and
For resources, we aim to speed up multiplication by speeding carry propagation in partial product addition.

[0013]

FIG. 1 is a block diagram showing the principle of the present invention. In FIG. 1, 100 is a multiplicand register, 101 is a multiplier register, 110, 1120, 13
0, 140 are partial product arithmetic circuits, 112, 122, 13
2, 142 are carry save adder circuits (hereinafter referred to as CSA circuits), 113, 123, 124, 133, 134, 1
43 and 144 are carry propagation addition circuits (hereinafter referred to as CPA circuits), 150 and 160 are partial product addition circuits, and 170 is a result register.

The partial product arithmetic circuits 110, 120, 130,
Reference numeral 140 denotes a circuit which, when given a multiplicand X and a multiplier Y, calculates a partial product of the multiplicand X and the multiplier Y, which are divided into upper and lower parts, respectively.
It has a circuit.

In the present invention, the partial product arithmetic circuits 120, 13
The CPA circuit in 0 and 140 is divided into the lower CPA
The carry C2 to C4 from the circuit is added to the partial product addition circuit 15
It is configured to send to 0,160. That is, the CPA circuit in the partial product calculation circuit 120 is replaced by the CPA circuit 1
23 and a CPA circuit 124, and a CPA circuit 123
And the carry from the CPA circuit 124 are sent to the partial product addition circuit 150, and the partial sum from the CPA circuit 124 is sent to the partial product addition circuit 160. The same applies to the partial product calculation circuit 130.

Also in the partial product arithmetic circuit 140, the CPA
The circuit is divided into two CPA circuits 143 and 144, and the partial product addition circuit 160 includes the partial sum and C of the CPA circuit 143.
Carrying PA circuit 144 is being sent. Even in the partial product calculation circuit 110 for obtaining partial products of upper ranks, the CPA circuit 1
Although 13 may be divided, it may not be divided in consideration of the trade-off between the calculation speed and the increase in the number of pins when integrated into an LSI.

In the partial product addition circuits 150 and 160, the partial sum and the carry that have been sent are added to obtain the final product.

[0018]

According to the present invention, the CPA circuit is divided so that the operation width in the partial product operation circuit is shortened, and the physical distance for carrying the carrier is shortened, so that the operation speed is increased. Is.

FIG. 2 is an explanatory diagram of the multiplication logic of the multiplication device shown in FIG. The calculation method when the CPA circuit in the partial product calculation circuits 120, 130, 140 is divided into two is as shown in FIG.
As shown in. In the figure, C2, C3, C4
Represent carry output by the CPA circuits 124, 134 and 144, respectively.

As indicated by carry propagation CP1 in FIG. 2, carry C2 from CPA circuit 124 of partial product arithmetic circuit 120 propagates for 4 bytes in partial product arithmetic circuit 120 and 8 in partial product addition circuit 150. Propagate for bytes.

When CP1 shown in FIG. 2 is compared with CP2 shown in FIG. 6 as the prior art, the carry propagates by the same distance and the calculation speeds seem to be the same. However, in practice, both the partial product addition circuit 150 according to the present invention and the conventional partial product addition circuit 750 have a C of 8-byte width.
Since it is calculated by the PA circuit, the carry propagation speeds in the partial product addition circuits 150 and 750 of CP1 and CP2 are the same. Therefore, the carry propagates faster in CP1 having a shorter propagation distance in the partial product calculation circuit 120 than in CP2 as a whole.

[0022]

FIG. 3 is a block diagram of an embodiment of the present invention. In FIG. 3, those having the same reference numerals as those in FIG. 1 correspond to those shown in FIG. 1, 111, 121, 131 and 141 are multiple generation circuits, and 151 and 161 are carry save and add circuits (CSA).
Circuits), 152, 162 are carry propagation addition circuits (CPA)
Circuit 163, 163 represents a carry signal line.

In this multiplication device, the multiplication of the multiplicand X, which is 8-byte data, and the multiplier Y is executed as follows. First, the partial product arithmetic circuits 110, 120, 130, 140 obtain respective partial products of the upper / lower order of X and the upper / lower order of Y. Partial product arithmetic circuits 110, 120, 13
0 and 140 are multiple generation circuits 111, 121, 131,
141, CSA circuits 112, 122, 132, 142 and a CPA circuit, and in particular, the CPA circuits of the partial product operation circuits 120, 130, 140 are divided into two based on the logic shown in FIG.

The partial product calculation circuit 110 outputs Z1 of 8 bytes, and the partial product calculation circuits 120, 130 and 140 respectively output Z2H, Z2L, Z3H, Z3L and Z4H, Z4L of 4 bytes and a carry C2 of 1 bit. , C3
Output C4.

Next, these partial product arithmetic circuits 110, 1
Outputs from 20, 130, and 140 are partial product addition circuits 15
The final product Z is obtained by adding 0,160. In addition,
The 4-byte Z4L output from the CPA circuit 143 is directly input to the final product Z without being input to the partial product addition circuit 160.
It may be the lower 4 bytes.

FIG. 4 shows a CSA configuration example of the partial product addition circuit 150. CSA of partial product addition circuit 150 shown in FIG.
The circuit 151 performs addition of Z1, Z2H, Z3H, C2 and C3. Since the addition of the least significant bit in the CSA circuit 151 is an addition of 5 bits, the CSA circuit 151 as shown in FIG. 4 is constructed, for example. 40 shown in this figure
Reference numerals 1 to 404 are full adders.

By the full adder 401, Z1, Z2H, Z
Add the least significant bit of 3H. The lower bits of the result and carry C2 and C3 are added by full adder 403. The full adder 402 adds the bit next to the least significant bit of Z1, Z2H, Z3H, and the full adder 404
The output and the carry of full adder 401 are added.

When the circuit configuration as described above is adopted, the switching speed of the gate is high, and the LS is higher than that.
The slower the signal transmission speed in I, the greater the effect. In the above embodiment, the CPA circuit in the partial product calculation circuit is divided into two. As a result, since the carry input / output is required, the number of pins of the partial product arithmetic circuits 110 to 140 is increased by 3 pins as compared with the conventional device shown in FIG. The total number of 160 pins will increase by 3 pins. That is, if the calculation width of the partial sum is halved in the division of the CPA circuit in the partial product calculation circuit, carry from the lower order to the upper order occurs, so that the output of the LSI is 1 each.
Pin increase. For example, if this calculation width is set to 1/4, it will increase by 3 pins each. As a result, the inputs of the partial product addition circuits 150 and 160 are
A total of 9 pins will be added.

The relationship between the carry propagation distance and the increase / decrease in the number of output pins due to the division of the partial product calculation circuit is as shown in FIG. As is clear from FIG. 5, as the CPA circuit is divided and the width of the CLA is made narrower, the carry propagation is faster, but the number of pins of the LSI increases. It is desirable that the number of output pins does not increase so much,
Moreover, the carry propagation distance is sufficiently short in practical use. Considering physical restrictions such as LSI mounting and pin count,
Considering from FIG. 5, it is considered that the bisection is efficient.

As shown in the CSA circuit 151 of FIG. 4, the number of inputs to the partial product addition circuit 150 increases,
The bit addition portion of the A circuit is increased by one stage. However, regarding the delay time problem in the recent LSI design, the propagation speed of the signal in the LSI has become more of a bottleneck than the switching time of the gate. Therefore, even if the CSA in the partial product addition circuit 150 is increased by one stage, the partial product is increased. Arithmetic circuit 1
In the inside of 20, 130, 140, the final product can be obtained faster as a whole by carrying and outputting the carry with a short CLA calculation width.

[0031]

As described above, according to the present invention,
The CPA circuit in the partial product arithmetic circuit is divided, partial products are calculated in the form of partial sum and carry, and the final product is obtained by adding them, so the carry propagation time in the partial product arithmetic circuit is shortened, As a whole, the multiplication result can be obtained at high speed.

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is an explanatory diagram of a multiplication logic of the present invention.

FIG. 3 is a block diagram of an embodiment of the present invention.

FIG. 4 is a diagram showing a CS of the partial product addition circuit according to the embodiment of the present invention.
It is a figure which shows the A structural example.

FIG. 5 is an explanatory view of increase / decrease in carry propagation distance and the number of output pins related to the present invention.

FIG. 6 is an explanatory diagram of a conventional general multiplication logic.

FIG. 7 is a diagram showing an example of a conventional multiplication device.

FIG. 8 is a diagram showing an example of a conventional multiplication device.

[Explanation of symbols]

100 Multiplicand register 101 Multiplier register 110, 120, 130, 140 Partial product arithmetic circuit 112, 122, 132, 142 Carry save addition circuit 113, 123, 124, 133, 134, 143, 1
44 Carry propagation addition circuit 150, 160 Partial product addition circuit 170 Result register

Claims (1)

[Claims] 1. A partial product operation having a carry save adder circuit (CSA) and a carry propagation adder circuit (CPA) for calculating a partial product of a multiplicand X and a multiplier Y divided into upper and lower parts, respectively. In a multiplication device comprising a circuit (110, 120, 130, 140) and a partial product addition circuit (150, 160) for adding the outputs of the partial product calculation circuit, the carry propagation addition circuit (CPA) in the partial product calculation circuit is configured by dividing. Then, the multiplication device is characterized in that the partial sum and the carry which are the outputs of the divided carry propagation addition circuit (CPA) are input to the partial product addition circuit for obtaining the final product and added.