Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-22
2001-08-07
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S630000
Reexamination Certificate
active
06272513
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention generally relates to a multiplying device for calculating the product of multiplicand data and multiplier data. This invention particularly relates to a multiplying device which uses Booth's algorithm for generating partial products.
2. Description of the Related Art
In recent years, digital signal processing apparatuses have been required to operate at higher speeds. Each digital signal processing apparatus is composed of parts including multiplying devices (multipliers). High-speed operation of multiplying devices has been desired.
A general multiplying device (a general multiplier) includes a partial product generating circuit and an adding circuit. The partial product generating circuit responds to data representing a multiplicand and data representing a multiplier. The data representing the multiplicand is also referred to as the multiplicand data. In some cases, the multiplicand data is shortened to the multiplicand. The data representing the multiplier is also referred to as the multiplier data. In some cases, the multiplier data is shortened to the multiplier. The partial product generating circuit produces data pieces representative of respective partial products in response to the multiplicand data and the multiplier data. The adding circuit adds the partial product data pieces to generate data representing the final product of the multiplicand and the multiplier. The adding circuit outputs the final product data. As the number of partial products increases, the speed of operation of the adding circuit drops so that the speed of product calculation by the multiplying device also drops.
Booth's algorithm is a method of reducing the number of partial products in a partial product generation stage. Booth's algorithm features that multiplication in a two's complement representation form can be executed without any correction. According to second-order Booth's algorithm, the number of partial products can be reduced to half the number of those required in straight combinatorial multipliers. Thus, in a multiplying device using second-order Booth's algorithm to generate partial products, a stage of adding the partial products can be short, and therefore the speed of multiplication can be high.
In a prior-art multiplying device, adders in a stage preceding a final adding stage are different from each other in number of bits of input data to be added. In the case where such adders are formed by a semiconductor integrated circuit, different bit numbers of the adders are inconvenient for chip layout.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a multiplying device convenient for chip layout.
A first aspect of this invention provides a multiplying device for implementing multiplication between multiplicand data and multiplier data in a two's complement representation form, the multiplicand data and the multiplier data each having n bits, where n denotes a predetermined even number. The multiplying device comprises 1-bit extension means for executing a 1-bit sign extension of the multiplicand data to generate data having n+1 bits, and for outputting the data having n+1 bits; partial product generation means for generating n/2 partial product data pieces on the basis of the data having n+1 bits which is outputted from the 1-bit extension means and on the basis of the multiplier data according to second-order Booth's algorithm, the n/2 partial product data pieces each having n+1 bits; and addition means including a plurality of adders connected and arranged in a tree configuration, the adders adding the n/2 partial product data pieces generated by the partial product generation means, the adders including a final-stage adder which outputs multiplication result data representing a product of the multiplicand data and the multiplier data, the multiplication result data having 2n−1 bits; wherein the adding means includes a plurality of sign extension means for implementing sign extensions of one data pieces, which correspond to lower bits of the multiplier data, in pairs of data pieces inputted into the adders.
A second aspect of this invention is based on the first aspect thereof, and provides a multiplying device wherein the number n is equal to 2
N
where N denotes an integer equal to 3 or greater, and the n/2 partial product data pieces are sequentially grouped into pairs in an order from those corresponding to lower bits of the multiplier data; wherein the addition means has a first stage including 2
N−2
adders corresponding to the respective pairs of the partial product data pieces, and the sign extension means which correspond to the respective 2
N−2
adders implement 2-bit sign extensions of one data pieces, which correspond to lower bits of the multiplier data, in the pairs of the partial product data pieces to generate and output addition-object data pieces each having n+3 bits; wherein each of the 2
N−2
adders adds n+1 higher bits of the related addition-object data piece having n+3 bits and the partial product data piece, which corresponds to a higher bit of the multiplier data, in the related pair of the partial product data pieces, and connects 2 lower bits of the related addition-object data piece having n+3 bits to a lowest bit side of an addition result to generate and output an addition data piece having n+3 bits; wherein addition data pieces outputted from adders in a (K−1)th stage of the addition means are sequentially grouped into pairs in an order from those corresponding to lower bits of the multiplier data, and the addition means has a Kth stage including 2
N−K−1
adders corresponding to the respective pairs of the addition data pieces, and K denotes an integer equal to 2 or greater, and wherein the sign extension means which correspond to the respective 2
N−K−1
adders implement 2
K
-bit sign extensions of one data pieces, which correspond to lower bits of the multiplier data, in the pairs of the addition data pieces to generate and output addition-object data pieces each having P bits, P denoting a number given by an equation as follows:
P
=
n
+
1
+
∑
m
=
0
K
-
1
2
(
K
-
m
)
wherein each of the 2
N−K−1
adders adds P-2
K
higher bits of the related addition-object data piece having P bits and the addition data piece, which corresponds to a higher bit of the multiplier data, in the related pair of the addition data pieces, and connects 2
K
lower bits of the related addition-object data piece having P bits to a lowest bit side of an addition result to generate and output addition data having P bits.
A third aspect of this invention provides a multiplying device for implementing either sign-added multiplication or sign-free multiplication between multiplicand data and multiplier data in response to a change signal, the multiplicand data and the multiplier data each having n bits, where n denotes a predetermined even number. The multiplying device comprises 2-bit extension means for executing a 2-bit sign extension of the multiplicand data in response to a highest bit of the multiplicand data to generate data having n+2 bits, and outputting the data having n+2 bits when the change signal requires sign-added multiplication to be implemented, and for executing a 2-bit 0 extension of the multiplicand data with respect to a highest bit side thereof to generate data having n+2 bits, and outputting the data having n+2 bits when the change signal requires sign-free multiplication to be implemented; partial product generation means for generating n/2 partial product data pieces on the basis of the data having n+2 bits which is outputted from the 2-bit extension means and on the basis of the multiplier data according to second-order Booth's algorithm, the n/2 partial product data pieces each having n+2 bits; addition means including a plurality of adders connected and ar
Douzono Hiroaki
Fukumoto Harutsugu
Tanaka Hiroaki
Denso Corporation
Malzahn David H.
Pillsbury & Winthrop LLP
LandOfFree
Multiplying device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiplying device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplying device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450020