Multiplier sign extension

Details Multiplier sign extension Multiplier sign extension

1997-09-04

2001-02-06

Malzahn, David H. (Department: 2787)

Boots, shoes, and leggings

36

Reexamination Certificate

active

06183122

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
Reference is made to copending application entitled “MULTIPLIER POWER SAVING DESIGN,” Ser. No. 08/923,133, filed Sep. 4, 1997, and copending application entitled “SMALL AREA MULTIPLIER,” Ser. No. 08/923,693, filed Sep. 4, 1997 which are hereby incorporated by reference.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
TECHNICAL FIELD OF THE INVENTION
The present invention pertains to digital multipliers, and, more particularly, to sign extension circuitry in parallel digital multipliers.
BACKGROUND OF THE INVENTION
The modified-Booth algorithm (as described, for example, in A. D. Booth, “A Signed Binary Multiplication Technique,” Quart. J. Mech. AppL Math, vol. 4, pt. 2, pp. 236-240, 1951; and in O. L. MarcSorley, “High-Speed Arithmetic in Binary Computers,” IRE Proc, vol. 49, pp. 67-91, Jan. 1961) is widely used to implement multiplication in DSP systems and other applications. Although this type of multiplier is not the fastest multiplier design, it does reduce the number of product terms to be added by half when compared to an array multiplier, and also allows a regular layout.
Modified Booth Algorithm
The modified Booth algorithm works essentially as follows: Given two numbers A and B, the algorithm analyzes the multiplier data A (taking three bits at a time) to determine whether to add zero, B,−B, 2B, or −2B based on the entire three bits. Table I shows the operation to be realized according to the three bits being analyzed. Ri is the accumulated result up to the current iteration.
TABLE 1
Modified Booth Algorithm
A
2i + 1
A
2i
A
2i − 1
Operation
0
0
0
R
i
= R
i − 1
/4
0
0
1
R
i
= (R
i − 1
+ B)/4
0
1
0
R
i
= (R
i − 1
+ B)/4
0
1
1
R
i
= (R
i − 1
+ 2B)/4
1
0
0
R
i
= (R
i − 1
+ 2B)/4
1
0
1
R
i
= (R
i − 1
− B)/4
1
1
0
R
i
= (R
i − 1
− B)/4
1
1
1
R
i
= R
i
− R
i − 1
/4
Row 1 and Row 8 of table 1 will be called NOOP (NO OPERATION) since from the algorithm perspective no addition is performed, only a division by 4 (i.e, a shift). For the radix-4 modified Booth algorithm (i.e., analyzing 3 bits at a time with 1 bit of overlap) it can be observed that in comparison with an array multiplier the number of rows is reduced by half. A carry save array is used to add the partial products and a fast adder is used to add the final two words (i.e., carry and sum) producing the final product.
From table 1 it can be observed that the implementation of the modified Booth algorithm requires a 5:1 mux in order to add B, −B, 2B, −2B or zero to the partial product.
A significant improvement can be achieved to reduce the rows of the multiplier if a higher radix is used for the multiplier data (see, for example, H. Sam and A. Gupta, “A Generalized Multibit Recoding of Two's Complement Binary Numbers and Its Proof with Application in Multiplier Implementations,” IEEE Transactions on Computers, vol. 39, pp. 1006-1015, 1990). The problem associated with this approach is that term 3B needs to be generated which is very difficult (i.e., time consuming). G. Bewick and M. J. Flynn (“Binary Multiplication Using Partially Redundant Multiples,” Stanford University Technical Report, no. CSL-TR-92-528, 1992) propose the use of small adders to generate this term in a partially redundant form. Still this approach adds overhead to the multiplier and breaks the regular structure of the multiplier.
A. Y Kwentus, H. Hung, and A. N. Willson, Jr. (“An Architecture for High Performance/Small Area Multipliers for Use in Digital Filtering Applications,” IEEE Journal of Solid-State Circuits, vol. 29, pp. 117-121, 1994) present the architecture of a multiplier where the terms 0, B, 2B, 3B are used. The main advantage of this multiplier is the reduction of the multiplexer from 5:1 (modified-Booth) to 4:1. The main disadvantage is that the 3B term needs to be pre-computed and stored in memory or generated with a fast adder.
TABLE 2
Kwentus Encoding
A
2i + 1
A
2i
Operation
0
0
R
i
= (R
i − 1
)/4
0
1
R
i
= (R
i − 1
+ B)/4
1
0
R
i
= (R
i − 1
+ 2B)/4
1
1
R
i
= (R
i − 1
+ 3B)/4
SUMMARY OF THE INVENTION
In accordance with the invention, a digital multiplier for multiplying multiplier data by multiplicand data to provide a product utilizes a multiplier data parsing circuit to parse the multiplier data on a group basis to form a first plurality of groups, and to select one of a second plurality of coefficients for factoring the multiplicand to form a first plurality of factored multiplicands. The product is the sum of the factored multiplicands plus two additional bits for a each of a third plurality of factored multiplicands plus a logic 1 added in the position of the sign bit of the factored multiplicand with the least significant bit position of all of the respective sign bits of the factored multiplicands. The two additional bits for each of the second plurality of factored multiplicands are a logic 1 followed by the inverse of the sign bit of the respective factored multiplicand, and are placed in the two next most significant sign positions of the respective factored multiplicand.


REFERENCES:
patent: 3691359 (1972-09-01), Dell et al.
patent: 4575812 (1986-03-01), Kloker et al.
patent: 4791601 (1988-12-01), Tanaka
patent: 4807175 (1989-02-01), Tokumuru et al.
patent: 5251167 (1993-10-01), Simmonds et al.

Affiliated with

Also associated with

Rating

Multiplier sign extension does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2611376