JPH0477819A - Multiplier - Google Patents

Abstract

PURPOSE:To obtain a multiplier in a comparatively ;small gate scale by adding in sequence the results of multiplication carried out between the prescribed bits of the multipliers divided by an S/P multiplication means and a multiplicand to the results of multiplication carried out between the precedent divided prescribed bits and the multiplicand through an adder and then adding together these multipliers and the multiplicand. CONSTITUTION:A full adder 8 adds sequentially the results of multiplication carried out between four bits of the multiplier X divided by an S/P multiplica tion means and amultiplicand Y to the results of multiplication carried out between the multiplicand Y and four bits of the multiplier X divided precedently. Then 64 latches 90 - 963 serving as the 1st storage means store successively the prescribed lower rank bits that are decided based on the result of addition of the adder 8. Furthermore a selector 10 and 32 latches 110 - 1131 serving as the 2nd storage means store successively plural remaining undecided bits, i.e., the results of multiplication excluding those decided bits and then give these results of multiplication in sequence to the adder 8 as the precedent results of multiplication. In such a constitution, a multiplier is obtained in a compara tively small gate scale.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a multiplier used for calculations in programmable controllers and the like.

[Prior Art] In a conventional programmable controller, a multiplier shown in FIG. 3 is used for calculation. (difficult) In the multiplier, the multiplier and multiplicand are each divided into 16-bit 1- bits, and 1.6
X 16-bit multiplication is performed four times to multiply a 32-bit multiplier and a 32-bit multiplicand. Specifically, the multiplier and multiplicand are each 32-bit latch 151.15
2, select the upper or lower 16 bits of the multiplier and multiplicand from this latch 151.15□ with the selector 161.16□, and multiply the multiplier of the selected 6 bits by the multiplicand. is repeated four times using a 16 x 16 bit parallel multiplier 17, and the result is
The multiplication results latched in the 2-bit latch 18 are shifted by the shifter 19, and the multiplication results after the shift are sent to the 64-hit adder 20 and the 64-bit latch 21. Add using , 3
This is to obtain a 2×32 bit multiplication result. Note that the selectors 161, t62 and shifter 19 operate according to the switching signal from the 2-bit counter 22.

[Problem to be solved by the invention 1 However, with the above-mentioned conventional multiplier configuration, 6
6 full adders are used to configure the adder 2o of 4 hits l~.
Since four are required, there is a problem in that the scale of each cage becomes large.

The present invention has been made in view of the above points, and an object thereof is to provide a multiplier that can be configured with a relatively small gate scale.

1. Means for Solving the Problems In order to achieve the above object, the present invention divides a multiplier into predetermined bits starting from the lower bits, and performs series-parallel multiplication in which the lower predetermined bits of the divided multiplier are sequentially multiplied by the multiplicand. means and
an addition means for sequentially adding the multiplication result of a predetermined bit of the divided multiplier and the multiplicand by the series-parallel multiplication means to the multiplication result of the previous predetermined bit of the divided multiplier and the multiplicand; A first storage means that sequentially stores lower predetermined bits determined by the result, and a first storage means that sequentially stores the remaining uncertain bits of the multiplication result excluding the determined predetermined bits, and stores the previous multiplication result in the addition means. and a second storage means for sequentially providing the data.

Note that in order to control the multiplier and the latch that stores the multiplicand using the same clock, a multiplier is provided for multiplying each bit of the multiplicand by the predetermined value of the multiplier. Shift l-L, when the number of multiplicands of the serial/parallel multiplication means stored is at least 2 of the number of divided bits of the multiplier.
Just double it.

[Function] As described above, the present invention divides the multiplier into predetermined bits starting from the lower bit 1 using the serial/parallel multiplication means, and repeats the multiplication of the multiplicand by the multiplicand by the number of divided bits,
and-) The result of multiplying the predetermined bits of the divided multiplier by the serial-parallel multiplier and the multiplicand is successively added to the result of multiplying the predetermined bit of the multiplicand by the multiplicand of the previous divided multiplier by an adder, and the multiplier is obtained. By performing addition with the multiplicand, the number of full adders can be made equal to the number of divided bits plus 1, making it possible to configure a multiplier with a relatively small gate scale. It is.

Further, the number of latches for shifting the multiplicand of the series/parallel multiplication means is provided for multiplying the predetermined bit of the multiplier by each bit of the multiplicand, and temporarily stores the multiplicand while sequentially shifting the multiplicand from the lower bits. By providing at least twice the number of divided bits of the multiplier, there is a period during which the predetermined bit of the multiplier is shifted according to the clock between the multiplication of the predetermined bit of the multiplier and the multiplicand and the multiplication of the next predetermined bit of the multiplier with the multiplicand. It is also possible to control the latches that store the multiplier and the multiplicand using the same clock.

[Example]-1 FIG. 1 shows an example of the present invention. The multiplier of this embodiment divides the multiplier X into 4 bits 1 to 4 bits starting from the lowest, and multiplies the divided multiplier Perform series-parallel multiplication and add the multiplication results while aligning the digits to create 32 bits x 3
The result is a 2-bit multiplication. This multiplier consists of a latch 1 that stores a 32-bit multiplier The four latches 3°-33 and the lower 4 bits X0 to X3 of the multiplier X output from latch 1, respectively.
and 1 of the multiplicand Y stored in the latches 3° to 33.
AND gates 4° to 43 that perform AND with the bits are connected to the outputs of AND gates 4° to 43, respectively, and delay the outputs of AND gates 4° to 43 by the number of clocks corresponding to the digit of the divided bit of multiplier X. Latch 5°・5. and multiplier X
1 of the multiplier X and the multiplicand Y provided for each digit of the divided bits of
A full adder 60 that performs bit-by-bit addition. -63, and latches 7o to 73 for holding the addition results of full adders 6° to 61I by one tarlock, and each of these gates 1 to constitutes a series/parallel multiplication means. Furthermore, in this multiplier, in order to obtain a 32x32-bit multiplication result by digit-aligning and adding the multiplication results of the series/parallel multiplier described in item 1, the 4 bits of the multiplier A full adder 8 serves as an addition means that sequentially adds the result of multiplication with the multiplicand Y to the result of multiplication between the 4 bits of the previously divided multiplier 64 latches 9° to 9 as storage means for sequentially storing lower predetermined bits (4 bits since the number of divided hits of the multiplier X is 4 bits)
63, the result of multiplication excluding (1) determined predetermined bits (4 bits) and the remaining uncertain multiple bits (4 bits of multiplier Therefore, the selector 10 and 32 latches serve as a 2nd y+ storage means, which sequentially stores the uncertain numbers 1 to 32 bits, and sequentially supplies them to the full adder 8 as the previous multiplication result. ]-1°~1]3
1. In this multiplier, the final 32 bits x 32 bits (64 bits) multiplication result is obtained from latches 9° to 96°.

The operation of the multiplier of this embodiment will be explained below.

First, when the tarokku TLl is input, the least significant bit data Y0 of the multiplicand Y stored in the latch 2 is transferred to the latch 31.
．． When the clock T1 is inputted next time, the bit data Y held in the latch 3° is stored. is the latch 3.
, and latch 3.degree. temporarily stores the next cut data Y1 of multiplicand Y, and so on. ~
3. The bit data of the multiplicand Y is stored while sequentially performing cloth storage according to the tarokku] 11. This situation is shown in the table below. Here, at the time when clock T is input, the above Y by Antogame 1-4 is input. and the least significant bit data X0 of the multiplier X, that is, the result of multiplying the least significant bit of the multiplier X and the multiplicand Y (X, Yo) is input to the latch 5°.

Next, when the tarlock T2 is input, the multiplication result (xoy, . . . ) held in the latch 5° is input to the full adder 6°, and the full addition result is stored in the latch 7°. However, since this full adder 6° is the least significant digit and there is no carry input, latch 7° receives the output of AND gate 4° (X
o Y o > will be stored as is. At this time, the multiplication result (X OY l
) is the latch 5. The multiplication result (x+yo>) by the AND gate 41 is input to the latch 51.

When the clock T3 is input, the full adder 6 adds the addition result (X o Y a > held in the latch 7°) and the multiplication result held in the latch 52. When T3 is input, latch 51
to latch 52 and gate 4. Multiplication result (XIY
o) is only shifted l~, and the multiplication result is not input to the full adder 6I from the latch 52, so the addition result of the full adder 6I is X. Y, and this addition result (x OY
o) is held by latch 7.

2, the multiplication result (XoYl) of the AND gate 4° is newly inputted to the full adder 6° from the latch 5°, and X is input to the latch 7 as the addition result of the full adder 6°. Y is retained. At the same time, the new multiplication result (X o Y 2 ) of the AND gate 4 o is input to the latch 5°, and the latch 5. The multiplication result (XIYo) held in latch 5
At the same time, the new multiplication result (x+y+) of AND gate 4 is shifted to latch 5. is input to latch 5.
The multiplication result (X2'1'0) of the AND gate 42 is input to.

When the clock T is input, the full adder 6□ adds the addition result (xoy,) held in the latch 7 and the latch 55.
Addition is performed with the multiplication result held in . However, when this clock T is input, latch 5. The multiplication result (X2YO) stored in latch 5. Since the latch 55 does not input the multiplication result to the full adder 62, the addition result of the full adder 62 is X. Yo
The addition result <XoYLl> is held in the latch 7□. At this time, in the full adder 61, the latch 7
(The addition result (X oY + ) held in + and the multiplication result (X IY o) held in the latch 52 is performed, and the addition result (XIYO+XoY,) is held in the latch 7. Furthermore, the multiplication result (X, Y,) of the AND gate 4° is newly inputted to the full adder 6° from the latch 5°, and X, Y2 is held in the latch 7° as the addition result of the full adder 6°. At the same time, the multiplication result (XoY]> is applied to the latch 5°, and the multiplication result (XIY) is applied to the latch 51.
2) is input, the multiplication result (X1Y1) is input to the latch 52, the multiplication result (X2Y1) is input to the latch 53, and the multiplication result (X2Y1) is input to the latch 53. The multiplication result (x2YO) is input to the latch 56, and the multiplication result (X:1YO) by the AND gate 43 is input to the latch 56.

When the clock T is input, the addition result of the full adder 6 is "X" in the same way as in the double case. Y.

This addition result (xoYo) is held in the latch 73. Also, full adder 6. Then, the addition result held in latch 7 (x + y o + x OY I The addition result of 6□ is X, + Y o + X o Y 1, and this addition result is held in latch 7. In full adder 6, the addition result held in latch 7° is χ.Y2)
and the multiplication result (XIYI> held in the latch 52), and this addition result (x + y + + x
OY 2 ) is held by latch 7. The addition result of the full adder 6° at this point is X. Y3, and this addition result is input to the latch 7o. Furthermore, at the same time, latches 50.5+ and 53.5G are connected to X, Y, , X, respectively.
, Y, , X2Y2, x3y are input, and the latch 52 .
5-. 55.57 to X, I ¥3, X 2 Y 1.
X 2 Y o , X 3Y + are cysted.

When the tally clock T6 is input, the addition results of the full adders 63 to 6 degrees, X, Yo-1-X, Y, , X 2 Y
o 10XIY1+XoY2, X, Y2+XOY,,X
o Y 4, and the lower 4 bits of the multiplier X are serially and parallel multiplied with the multiplicand Y in the same manner, and the calculation results shown in Table 2 are obtained. Then, when the above-mentioned series-parallel multiplication is completed, after shifting the multiplier The series-parallel multiplication with the multiplicand Y is repeated up to the upper 4 bits of X a total of 8 times.

-/l- The addition result held in the latch 73, which is the result for each digit of serial-parallel multiplication of the 4 bits of the multiplier . Now, suppose we are performing series-parallel multiplication with the multiplicand Y to the lower four bits 1 of the multiplier data is also not stored. Therefore, the result of the full adder 8 becomes the serial/parallel multiplication result held in the latch 73 as it is.

By the way, in this embodiment, the multiplier X has 4 bits.

The series/parallel multiplication of the multiplicand (x) and the multiplicand (l) is the data P of the lower 4 bits as a result of serial/parallel multiplication of the lower 4 bits of the multiplier X and the multiplicand Y. . . P is determined without waiting for the result of serial-parallel multiplication between the 4 bits of the multiplier X above it and the multiplicand Y. Therefore, in the case of this embodiment, the lower 4 bit data P is the confirmed hit data. ~P3 is stored in the latch 9°~963. Then, the remaining bit data is selected by the selector 10 and stored in the latches 11° to 1131. , 2 irons, 4 hits x 32 bits, the result of the multiplication is 36 bits, so if we exclude the definite bits of the above 4 bits, we get
32 bits of data are stored in latches 1.1o to 113. will be stored sequentially.

After that, when serial-parallel multiplication is performed between the next 4 bits of the multiplier . At this time, the lower 4 bits data P,
~P7 is determined without waiting for the series-parallel multiplication of the higher-order 4 bits l~ of the multiplier X and the multiplicand Y, so this data P,
・F”7 is stored in latches 9° to 963, and the remaining data is stored in latches llo to 113. via the selector 10. If the calculation is repeated in this way, the top four The last 36-bit data P211 to F'63 are determined by series-parallel multiplication of the bits and the multiplicand Y, and the data stored in the latches 9o to 963 becomes the multiplication result of 32 bits of the multiplier X x 32 bits of the multiplicand Y. If the multiplier of this embodiment is configured, the number of full adders can be reduced to five, and the multiplier can be configured with a relatively small gate scale.

[Example 2] FIG. 2 shows another example of the present invention. In this example, four latches 3 are installed after the latches 3 to 33 of the first embodiment.
．． 37 are added, and the other configurations are completely the same as the first embodiment.

In the case of the first embodiment described above, at the end of the serial/parallel multiplication of the 4 bits of the multiplier X and the multiplicand Y, the multiplier Therefore, latch 1.
The clock timings of latches 1.2 and 2 must be made different, which complicates the control of latch 1.2. Therefore, in order to improve this point, in this embodiment, as described above, the latch 3°
4 latches after 3 3. ~37 was added. In this way, before serial-parallel multiplication of the next 4 bits of the multiplier X and the multiplicand Y, it is possible to
(Refer to 39) It is possible to set the data in the latches 33 and -33 to 0, and if the four clocks during this time are used as tarlocks for shifting the bits of the multiplier χ, the latches 1 and 2
[Effects of the Invention] As described above, the present invention is a series-parallel multiplication method in which a multiplier is divided into predetermined bits starting from the lower bits, and the multiplicand is sequentially multiplied from the lower predetermined bits of the divided multiplier. means, an addition means for sequentially adding the result of multiplication of a predetermined bit of the divided multiplier and the multiplicand by the series-parallel multiplication means to the result of multiplication of the predetermined bit of the previous divided multiplier and the multiplicand; a first storage means for sequentially storing lower predetermined bits determined by the addition result by the means; and a first storage means for sequentially storing lower predetermined bits determined as a result of the addition by the means; Since the means is equipped with a second storage means that sequentially supplies the result of the previous multiplication to the means, the number of full adders can be reduced to the number of divided bits plus 1, and the gate size is relatively small. Multipliers can be configured.

In addition, the number of latches for shifting the multiplicand of the series/parallel multiplication means provided for multiplying the predetermined bit of the multiplier by each bit of the multiplicand and temporarily storing the multiplicand while sequentially shifting the multiplicand from the lower bits is set at least. If twice the number of divided bits of the multiplier is provided, a period during which a predetermined bit of the multiplier is shifted according to the clock between the multiplication of a predetermined bit of the multiplier and the multiplicand and the multiplication of the next predetermined bit of the multiplier and the multiplicand. can be provided, and the latches that store the multiplier and the multiplicand can be controlled with the same clock.

[Brief explanation of drawings]

FIG. 1 is a block diagram of one embodiment of the present invention. FIG. 2 is a block diagram of another embodiment, and FIG. 3 is a block diagram of a conventional example. X times multiplier, Y is multiplicand, 1.2.31~3y, 5o~5
5,7o~73.90~9+13.1.10~]-1,
, is a latch, 4° to 43 is an and gate, 6o to 61,
8 is a full adder, ]0 is a selector, and 3o to 37 are latches. Agent Patent Attorney Ishi 1) Choshichi

Claims (2)

[Claims] (1) A series/parallel multiplication means that divides a multiplier into predetermined bits starting from the lower bits and sequentially multiplies the divided multiplier by a multiplicand starting from the lower predetermined bits, and predetermined bits of the multiplier divided by the series/parallel multiplication means. Adding means for sequentially adding the result of multiplication with the multiplicand to the multiplication result of the predetermined bits of the previously divided multiplier and the multiplicand, and sequentially storing lower predetermined bits determined by the addition result by the addition means. 1st
and a second storage means that extracts and sequentially stores the remaining uncertain bits of the multiplication result excluding the determined predetermined bits, and sequentially supplies the same to the addition means as the previous multiplication result. Multiplier. (2) Number of latches for shifting the multiplicand of the series/parallel multiplication means, which are provided for multiplying the predetermined bit of the multiplier by each bit of the multiplicand, and temporarily store the multiplicand while sequentially shifting the multiplicand from the lower bits. Claim 1 characterized in that the number of divided bits of the multiplier is at least twice as large as the number of divided bits of the multiplier.
Multiplier as described.