1. Field of the Invention
The present invention relates to a parallel multiplier, and particularly to an improved parallel multiplier capable of operating an addition operation by connecting a plurality of dividers sequentially, thus providing more simple circuit and reducing operating time thereof.
2. Description of the Conventional Art
Generally, in case of multiplying the multiplicand bits and multiplier bits which are expressed in a binary form, a partial multiplication of the multiplicand bits and multiplier bits is performed, and the partial multiplication is shifted to the left by a bit, and the shifted partial multiplication is performed. Therefore, the speed of such multiplication operation depends on the speed of an addition operation. The procedure of such partial multiplication can be expressed as follows with an example of binary 10102(1010) and 11102(1410).
According to the above-described procedure of the multiplication, a parallel multiplier differs from a serial multiplier. The serial multiplier includes an adder capable of storing n-bits with respect to each digit (20, 21, . . . , 2n) of a multiplier and registers for storing a partial sum so as to perform an addition operation sequentially.
Such as a serial multiplier is relatively simple in its construction and requires a clock pulse in each operation step and has lengthy operation time, so that it is not used for an operation apparatus which requires a high speed operation.
Meanwhile, the parallel multiplier uses an addition operation apparatus having a plurality of n-bit with respect to each digit(21, . . . , 2n) of a multiplication so as to perform a multiplication operation, so that since it has a high speed performance, it is available for a high speed apparatus.
Referring to FIG. 1, a conventional parallel multiplier, in case that multiplicand bits X0 through X3 and multiplier bits Y0 through Y3 are 4 bits, respectively, includes AND-gates AD1 through AD4 for ANDing a bit Y0 and its corresponding bits X0 through X3, AND-gates AD5 through AD8 for ANDing a bit Y1 and its corresponding bits X0 through X3, a half adder 1 for adding output bits of AND-gates AD2 and AD5, a full adder 2 for adding a carry bit C0 outputted from a half adder 1 and output bits of AND-gates AD3 and AD6, a full adder 3 for adding a carry bit C0 outputted from a full adder 2 and output bits of AND-gates AD4 and AD7, a half adder 4 for adding a carry bit C0 outputted from a full adder 3 and output bits of the AND-gate AD8, AND-gates AD9 through AD12 for ANDing a bit Y2 and its corresponding bits X0 through X3, a half adder 5 for adding a sum bit S outputted from the full adder 2 and the output bits outputted from the AND-gate AD9, a full adder 6 for adding the carry bit CO outputted from the half adder 5, the sum bit S outputted from the full adder 3, and the output bits of an AND-gate AD10, a full adder 7 for adding the sum bit S outputted from the half adder 4 and the output bit of an AND-ate AD11, a fill adder 8 for adding the carry bit C0 outputted from the full adder 7, the carry bit C0 outputted from the half adder 4, and the output bit of the AND-gate AD12, AND-gates AD13 through AD16 for ANDing a bit Y3 and its corresponding bits X0 through X3, a half adder 9 for adding the sum bit S outputted from the full adder 6 and the output bit of an AND-gate AD13, a full adder 10 for adding the carry bit C0 outputted from the half adder 9, the sum bit outputted from the full adder 7, and the output bits outputted from an AND-gate AD14, a full adder 11 for adding the carry bit C0 outputted from the full adder 10, the sum bit S outputted from the full adder 8, and the output bits of an AND-gate AD15, and a full adder 12 for adding the carry bit C0 outputted from the full adder 11, the carry bit C0 outputted from the full adder 8, and the output bits of an AND-gate Ad16.
As shown in FIG. 2A, each of the half adders 1, 4, 5, and 9 includes an AND-gate AD17 for ANDing the input bits A and B and for outputting the carry bit C0, and an exclusive OR-gate XOR1 for exclusively ORing the input bits A and B and for outputting the sum bits S.
In addition, as shown in FIG. 2B, the full adders 2, 3, 6, 7, 8, 10, 11, and 12 each include a half adder 20 for adding input bits Axe2x80x2 and Bxe2x80x2, a half adder 21 for adding the sum bits S outputted from the half adder 20 and the carry bits Ci and for outputting the sum bits Sxe2x80x2, and an OR-gate OR1 for ORing the carry bit Co outputted from the half adder 21 and the carry bits 20 outputted from the half adder 20.
The operation of the conventional parallel multiplier will now be explained with reference to FIGS. 1 and 2.
To begin with, the bit MO outputted from the AND-gate AD1 becomes a least significant bit (LSB). Thereafter, the half adder 1 adds the out bits of the AND-gates AD2 and AD5 and outputs bits M1. In addition, the full adder 2 adds the out bits of the AND-gates AD3 and AD6 and the carry bits C0 outputted from the half adder 1, and the half adder 5 adds the sum bits S outputted from the full adder 2 and the AND-gate AD9 and outputs bits M2. In addition, the full adder 3 adds the output bits of the AND-gates AD4 and AD7 and the carry bit C0 outputted from the full adder 2, and the full adder 6 adds the sum bits S outputted from the full adder 3, the output bits of the AND-gate AD10 and the carry bits C0 outputted from the half adder 5. The half adder 9 adds the sum bits S outputted from the full adder 6 and the out bits of the AND-gate AD13 and outputs bits M13. The half adder 4 adds the carry bit C0 outputted from the full adder 3 and the output bits of the AND-gate AD8, and the full adder 7 adds the sum bits S outputted from the half adder 4, the output bits of the AND-gate AD11, and the carry bits C0 outputted from the full adder 6, and the full adder 10 adds the sum bit S outputted from the full adder 7, the output bits of the AND-gate Ad14 and the carry bits C0 outputted from the half adder 9 and outputs bits M4. In addition, the full adder 8 adds the carry bits C0 outputted from the half adder 4, the output bits of the AND-gate AD12, and the carry bits C0 outputted from the full adder 7, and the full adder 11 adds the sum bits S outputted from the full adder 8, the output bits of the AND-gate AD15, and the carry bits C0 outputted from the full adder 10, and outputs bits M5. The full adder 12 adds the carry bits C0 outputted from the full adder 8, the output bits of the AND-gate AD16, and the carry bits C0 outputted from the full adder 11 and outputs bits M6. At this time, the carry bits C0 outputted from the full adder 12 become bits M7 of a most significant bit (MSB).
The above-described parallel multiplier performs an multiplication operation in parallel not using registers for storing the results of a partial multiplication and a partial addition, so that a parallel multiplier has more speedy operation compared with a serial multiplier.
However, since the speed of partial addition is very slow, the operation speed is generally subject to the adders rather than the time required for the operation of the partial multiplication by the AND-gate. In case that the multiplier bits and multiplicand bits include xe2x80x9cnxe2x80x9d bits, the required number of the transistor is in proportion to n2, so that the manufacturing cost increases.
Meanwhile, there have been many studies is reducing the time required in addition operations. Among the parallel multipliers, a parallel multiplier using a wallace tree is the most speedy operation apparatus, and a modified wallace tree is generally used for the parallel multiplier.
Here, the wallace tree, as shown in FIG. 3, receives bits A, B, and Ci each of 2n digit in case of having 3-bit input and outputs a sum bit S of 2n and a carry bit of Cn+1. That is, as shown in FIG. 3B, the bits A1, B, and C are added, and the carry bit C0 and the sum bit S which have the same function as a full adder are outputted.
As a result, the function of the wallace tree having 3 input bits is the same as in a full adder, and the function of the wallace having 2 input bits has the same function as in a half adder, and the wallace tree corresponding to the remaining input bits includes a plurality of full adders and half adders.
In addition in case that a wallace tree includes 2n input bits, N+1 bits are outputted, and the outputted bits have digits of 2n, 2n+1, . . . , 20.
The wallace tree requires additional full adders as the number of input increases. As shown in FIG. 4A, in case that a general wallace tree has 7 input bits, it includes a wallace tree 30 and a wallace tree 31 each receiving 3-bit of 2n digit, a wallace tree 32 for receiving the sum bit S of the wallace tree 30 and the sum bit S of the wallace tree 31 and for outputting the sum bit S of 2n digit, and a wallace tree 33 for receiving the carry bit C0 of the wallace tree 31 and the carry bit C0 of the wallace tree 30 and for outputting the sum bit S of 2n+1 digit and the carry bit C0 of 2n+2 digit.
As shown in FIG. 4B, in the above-described wallace tree, the number of xe2x80x9c1xe2x80x9d among the 7 input bits can be expressed in binary digit, and sums the input bits having the same digit and outputs the sum. That is, the number contained in the input bits is the same as the sum of the input bits.
FIG. 5 shows a construction sequentially connecting a plurality of wallace trees each having 16-bit input. That is, a wallace tree 35 receives a 16-bit of 2n digit and outputs 5-bit of 2n+4, 2n+2, 2n+1, and 2n. Thereafter, a wallace tree 36 receives the 16-bit of 2n+1 having 2n+1 digit outputted from the wallace tree 35 and outputs 5-bit of 2n+5, 2n+4, 2n+3, and 2n+2, and 2n+1. In addition, a wallace tree 37 receives bits of 2n+2 outputted from the wallace tree 35 and 16-bit of 2n+2 including bits of 2n+1 outputted from the wallace tree 36 and outputs 5-bit of 2n+6, 2n+5, 2n+4, and 2n+3, and 2n+2.
If a plurality of wallace trees connected with one another in the above-described manner are used in an addition of a parallel multiplier, the speed of the addition can be increased and the operation speed of the parallel multiplier can be increased.
A parallel multiplier using a wallace tree can increase the operation speed more compared with a standard parallel multiplier, however it has different constructions from one another in accordance with the number of outputted carry bits. In addition, the parallel multiplier has much time delay due to the carry bits outputted from wallace trees. Moreover, in case that a multiplier bit and a multiplicand bit are xe2x80x9cnxe2x80x9d bits, respectively, the number of required transistors is in proportion to n2 logn, so that the construction of required circuit becomes complicated, and it is hard to design the circuit, and thus the manufacturing cost increases.
Accordingly, it is an object of the present invention to provide a parallel multiplier, which overcome the problems encountered in a conventional parallel multiplier.
It is another object of the present invention to provide an improved parallel multiplier capable of operating an addition operation by connecting a plurality of dividers sequentially, thus providing more simple circuit and reducing operating time thereof.
To achieve the above objects, there is provided a parallel multiplier, which includes NXM AND-gates each for ANDing each multiplier bit ranging from a least significant bit to a most significant bit with each multiplicand bit in case of multiplying xe2x80x9cNxe2x80x9d multiplicand bits and xe2x80x9cMxe2x80x9d multiplier bits and for performing a partial multiplication and for outputting a least significant bit as a result of the multiplication; and a plurality of input-bits dividers, having 2-, 3-, and 4-input-bits dividers, for receiving an output bit of a corresponding location among a rearranged output bit and a quotient bit outputted from a proceeding input bit in case that the output bits of the AND-gates is shifted to the left by a bit in accordance with a conventional binary multiplication method and for outputting a quotient bit and a remaining bit corresponding to each bit of a multiplication result.