Parallel multiplier

Details Parallel multiplier Parallel multiplier

1997-11-24

2002-10-22

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06470371

ABSTRACT:

BACKGROUND OF THE INVENTION
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 1010
2
(10
10
) and 1110
2
(14
10
).
1010
2
<--- multiplicand bits (10
10
)
X 1110
2
<--- multiplier bits (14
10
)
0000
2
<------ 2
0
bit of multiplier is “0” ----- a partial multiplication 1
1010
2
<------ 2
1
bit of multiplier is “0” ----- a partial multiplication 2
1010
2
<------ 2
2
bit of multiplier is “0” ----- a partial multiplication 3
1010
2
<------ 2
3
bit of multiplier is “0” ----- a partial multiplication 4
10001100
2
<--- result (140
10
)
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 (2
0
, 2
1
, . . . , 2
n
) 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(2
1
, . . . , 2
n
) 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 X
0
through X
3
and multiplier bits Y
0
through Y
3
are 4 bits, respectively, includes AND-gates AD
1
through AD
4
for ANDing a bit Y
0
and its corresponding bits X
0
through X
3
, AND-gates AD
5
through AD
8
for ANDing a bit Y
1
and its corresponding bits X
0
through X
3
, a half adder
1
for adding output bits of AND-gates AD
2
and AD
5
, a full adder
2
for adding a carry bit C
0
outputted from a half adder
1
and output bits of AND-gates AD
3
and AD
6
, a full adder
3
for adding a carry bit C
0
outputted from a full adder
2
and output bits of AND-gates AD
4
and AD
7
, a half adder
4
for adding a carry bit C
0
outputted from a full adder
3
and output bits of the AND-gate AD
8
, AND-gates AD
9
through AD
12
for ANDing a bit Y
2
and its corresponding bits X
0
through X
3
, 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 AD
9
, 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 AD
10
, a full adder
7
for adding the sum bit S outputted from the half adder
4
and the output bit of an AND-ate AD
11
, a fill adder
8
for adding the carry bit C
0
outputted from the full adder
7
, the carry bit C
0
outputted from the half adder
4
, and the output bit of the AND-gate AD
12
, AND-gates AD
13
through AD
16
for ANDing a bit Y
3
and its corresponding bits X
0
through X
3
, a half adder
9
for adding the sum bit S outputted from the full adder
6
and the output bit of an AND-gate AD
13
, a full adder
10
for adding the carry bit C
0
outputted from the half adder
9
, the sum bit outputted from the full adder
7
, and the output bits outputted from an AND-gate AD
14
, a full adder
11
for adding the carry bit C
0
outputted from the full adder
10
, the sum bit S outputted from the full adder
8
, and the output bits of an AND-gate AD
15
, and a full adder
12
for adding the carry bit C
0
outputted from the full adder
11
, the carry bit C
0
outputted from the full adder
8
, and the output bits of an AND-gate Ad
16
.
As shown in
FIG. 2A
, each of the half adders
1
,
4
,
5
, and
9
includes an AND-gate AD
17
for ANDing the input bits A and B and for outputting the carry bit C
0
, and an exclusive OR-gate XOR
1
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 A′ and B′, 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 S′, and an OR-gate OR
1
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 AD
1
becomes a least significant bit (LSB). Thereafter, the half adder
1
adds the out bits of the AND-gates AD
2
and AD
5
and outputs bits M
1
. In addition, the full adder
2
adds the out bits of the AND-gates AD
3
and AD
6
and the carry bits C
0
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 AD
9
and outputs bits M
2
. In addition, the full adder
3
adds the output bits of the AND-gates AD
4
and AD
7
and the carry bit C
0
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 AD
10
and the carry bits C
0
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 AD
13
and outputs bits M
13
. The half adder
4
adds the carry bit C
0
outputted from the full adder
3
and the output bits of the AND-gate AD
8
, and the full adder
7
adds the sum bits S outputted from the half adder
4
, the output bits of the AND-gate AD
11
, and the carry bits C
0
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 Ad
14
and the carry bits C
0
outputted from the half adder
9
and outputs bits M
4
. In addition, the full adder
8
adds the carry bits C
0
outputted from the half adder
4
, the output bits of the AND-gate AD
12
, and the carry bits C
0
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 AD
15
, and the carry bits C
0
outputted from the full adder
10
, and outputs bits M
5
. The full adder
12
adds the carry bits C
0
outputted from the full adder
8
, the output bits of the AND-gate AD
16
, and the carry bits C
0
outputted from the full adder
11
and outputs bits M
6
. At this time, the carry bits C
0
outputted from the full adder
12
become bits M
7
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 “n” bits, the required number of the transistor is in propo

Affiliated with

Also associated with

Rating

Parallel multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel multiplier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3000446