Arithmetic circuit using a booth algorithm

Details Arithmetic circuit using a booth algorithm Arithmetic circuit using a booth algorithm

1998-10-23

2001-03-13

Lee, Thomas C. (Department: 2182)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S626000

Reexamination Certificate

active

06202078

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a multiplier/adder/subtracter and a digital signal processor using it, which use, for example, booth algorithm.
2. Description of the Prior Art
FIG. 27
is a diagram showing a prior art multiplier/adder/subtracter for computing Z=±(A×B)±C (the order of signs being variable). A, B, C and Z represent binary data expressed by complements of 2, respectively.
As shown in
FIG. 27
, a multiplier A is input into a booth decoder circuit
1
. The multiplier A is decoded in the booth decoder circuit
1
according to a booth algorithm. The decoded result is input to a partial multiplier/partial adder circuit
2
which is also supplied with a multiplicand B to generate partial products and accumulate partial products having the same significance by using the booth algorithm from the multiplier A and the multiplicand B. The partial multiplier/partial adder circuit
2
, however, executes only a part of addition of generated partial products. More specifically, it progresses addition of partial products of respective steps by CSA (carry save adder system) except for addition of the final step. The result of the addition is input to a multiplier final adder circuit
3
.
The multiplier final adder circuit
3
conducts final addition of these partial products. That is, it executes addition of the final step among addition of partial products. For addition of the final step, CLA (carry look ahead adder system), ripple carry system serially connecting all adders, or the like, is used because consideration must be made also on carry from lower positions. It results in all partial products having the same significance having been added in the multiplier final adder circuit
3
, and data as a result of A×B computation is output.
Data resulting from A×B computation is input to a code inverter circuit
4
. The code inverter circuit
4
inverts the sign of A×B in response to a control signal
1
. That is, depending upon the value of the control signal, it outputs A×B in its original form, or outputs −(A×B) by inverting the sign of A×B. The output is input to an adder
5
.
On the other hand, an addend C is input into a code inverter circuit
6
. The code inverter circuit
6
inverts the sign of the addend C in response to a control signal
2
. That is, depending upon the value of the control signal
2
, it outputs C in its original form, or output −C by inverting the sign of C. Also this output is input to the adder
5
.
The adder
5
executes addition of input data from the code inverter circuits
4
and
6
. That is, it conducts addition of data ±(A×B) and data ±C by CLA, for example, and outputs Z as a result of final calculation.
It will be understood from the foregoing explanation that, for calculating Z=±(A×B)±C (the order of signs being variable) in this manner, ±(A×B) must be first calculated before calculating ±C. Therefore, the prior art needs the multiplier final adder circuit
3
and the adder
5
which are the same in function. The multiplier final adder circuit
3
and the adder
5
are normally designed for CLA as mentioned above, and therefore large in circuit scale. Therefore, it was the problem that these two circuits, multiplier final adder circuit
3
and adder
5
, increased the entire circuit area. It was another problem that the number of gate steps contained in the critical path increased and inevitably decreased the calculation speed. The critical path pertains to the path taking the longest time for propagation of a signal between the input terminal and the output terminal. Therefore, the use of two circuits equivalent in function gave no advantage for the calculation speed.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a multiplier/adder/subtracter not requiring two functionally equivalent circuits. More specifically, it is intended to provide a multiplier/adder/subtracter which can omit the adder
5
from the multiplier final adder circuit
3
and the adder
5
. A further object of the invention is to provide a multiplier/adder/subtracter reduced in circuit area and improved in calculation speed.
According to the invention, there is provided a multiplier/adder/subtracter for calculation of Z=±(A×B)±C (the order of signs being variable) for Z, A, B and C as complement data of 2 by using a booth algorithm, comprising:
booth decode execution means changed to decode A in the original form or to decode −A by changing a first control signal depending upon whether A×B or −A×B should be calculated by multiplication;
sign-attached partial product generating means supplied with a result of decoding by the booth decode execution means and B to generate partial products thereof; and
sign-attached adder means for adding partial products generated by the sign-attached partial product generating means, and for adding C as a part of addition of said partial products when C is added to a result of multiplication or adding −C as a part of addition of the partial products when C is subtracted from the result of multiplication.
There is further provided a multiplier/adder/subtracter for calculation of Z=±(A×B)±C (the order of signs being variable) for Z, A, B and C as binary data, comprising:
sign-attached partial product generating means for generating partial products of A×B when multiplication of A×B should be done and for generating partial products of −A×B when multiplication of −A×B should be done; and
sign-attached adder means for executing addition of partial products generated by said sign-attached partial product generating means and for adding C as a part of addition of said partial products when C should be added to the result of multiplication or adding −C as a part of addition of the partial products when C should be subtracted from the result of multiplication.
There is further provided a digital signal processor having a multiplier/adder/subtracter for calculation of Z=±(A×B)±C (the order of signs being variable) for Z, A, B and C as complement data of 2 by using a booth algorithm, the multiplier/adder/subtracter comprising:
booth decode execution means changed to decode A in the original form or to decode −A by changing a first control signal depending upon whether A×B or −A×B should be calculated by multiplication;
sign-attached partial product generating means supplied with a result of decoding by the booth decode execution means and B to generate partial products thereof; and
sign-attached adder means for adding partial products generated by the sign-attached partial product generating means, and for adding C as a part of addition of said partial products when C is added to a result of multiplication or adding −C as a part of addition of the partial products when C is subtracted from the result of multiplication.


REFERENCES:
patent: 5053987 (1991-10-01), Genusov et al.
patent: 5095456 (1992-03-01), Wong
patent: 5163017 (1992-11-01), Wong et al.
patent: 5179530 (1993-01-01), Genusov et al.
patent: 5426599 (1995-06-01), Machida
patent: 5521856 (1996-05-01), Shiraishi
patent: 5600658 (1997-02-01), Qureshi
patent: 5684730 (1997-11-01), Martinez et al.
patent: 5751618 (1998-05-01), Abiko et al.

Affiliated with

Also associated with

Rating

Arithmetic circuit using a booth algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arithmetic circuit using a booth algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic circuit using a booth algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2515846