Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-01-15
2002-04-02
Chaki, Kakali (Department: 2122)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S007000
Reexamination Certificate
active
06366944
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of digital data processing and, in particular, to a method and apparatus for performing signed/unsigned multiplication.
2. Background Information
The demand for higher performance multimedia applications has prompted the development of faster, more powerful processors that consume less power, and take up less space on a printed circuit board, leaving room for additional feature enhancements. Multiplication is one of the most common, basic tasks needed for computational purposes. Those skilled in the art will appreciate that nearly all multimedia applications such as digital signal processing (DSP), digital filtering, graphics, audio and video rendering require fast, area efficient multipliers. Due to the frequency of multiplication computations, multipliers are not only located within central processing units (CPU) or math co-processors, but in nearly any controller embedded within any digital system. Those skilled in the art will appreciate that unsigned multiplication is performed on numbers represented in floating point format, whereas integer multiplication is performed in a signed, 2's-complement format. Consequently, prior art controllers have typically relied on separate multiplier circuitry, one each for signed and unsigned multiplication.
Simplistically, unsigned multiplication is performed in a controller in much the same way that we learned in elementary school. That is, a multiplicand is multiplied by each digit in the multiplier to create a corresponding number of rows of partial products, which are then summed to produce the final product. Within a controller, multiplication is performed with a series of logic gates, wherein the multiplicand is ANDed with each bit of the multiplier to produce rows of partial products. A number of hierarchically arranged carry-save adders (CSA's) compress the partial products which are then summed to produce the final product. Signed multiplication, however, adds a level of complexity as the sign of each of the multiplicand and multiplier is embedded within the number itself and must be properly carried through the calculation in the partial products. A number of methods have been proposed which deal with the embedded signs inherent in signed multiplication, with the most popular of such methods being Booth's algorithm. A complete description of Booths algorithm can be found, for example, in Hennessy, et al.,
Computer Architecture: A Quantitative Approach
, Second Edition,
Appendix A: Computer Arithmetic
by D. Goldberg, Morgan Kaufman Publishers, San Mateo, Calif., 1996.
Architecturally, a number of alternative multiplier designs exist. Those skilled in the art will appreciate that each of the architecturally unique multipliers have been developed with the goal of decreasing the amount of time (measured in clock cycles) necessary to complete multiplication tasks. Those skilled in the art will appreciate, however, that prior art multiplier circuitry is generally quite large, requiring a large amount of die space on the controller. While some of the prior art solutions for increasing the speed of multiplication may have had a collateral effect of reducing the amount of space consumed by the multiplier circuitry, e.g., the Wallace tree architecture, those skilled in the art will appreciate that such space savings were nominal, at best.
Thus, a method and apparatus for performing signed/unsigned multiplication is required that overcomes the inherent limitations and deficiencies commonly associated with the prior art. Just such a method and apparatus is presented in accordance with the teachings of the present invention that achieves these and other desired results.
SUMMARY OF THE INVENTION
In accordance with the teachings of the present invention, a method and apparatus for performing signed and unsigned multiplication is presented. In particular, in accordance with a first embodiment of the present invention, an apparatus is presented comprising a computation cell to generate a plurality of product terms, a compressor, coupled to the computation cell, and a selector coupled to each of the computation cell and the compressor. The selector, couples one output of the computation cell to an input of the compressor, and selects whether the compressor receives the partial product term from the compressor or an inverse thereof. The compressor is used to generate a pair of product terms from the received plurality of product terms.
REFERENCES:
patent: 3666933 (1972-05-01), Grobert
patent: 4118785 (1978-10-01), Izumi et al.
patent: 4181970 (1980-01-01), Izumi et al.
patent: 4592004 (1986-05-01), Bocker et al.
patent: 4697247 (1987-09-01), Grinberg et al.
patent: 5005150 (1991-04-01), Dent et al.
patent: 5412565 (1995-05-01), Boser et al.
patent: 5555200 (1996-09-01), Chiang
patent: 5701260 (1997-12-01), Nagazumi
patent: 5751619 (1998-05-01), Agarwal et al.
patent: 5841684 (1998-11-01), Dockser
patent: 5862067 (1999-01-01), Mennemeier et al.
patent: 6029187 (2000-02-01), Verbauwhede
patent: 6035316 (2000-03-01), Peleg et al.
Principles of Computer Architecture, An Integrated Approach, Miles Murdocca, Department of Computer Science, Rutgers University and Miletus Research, Copyright © 1997.*
“A Two's Complement Parallel Array Multiplication Algorithm,” Baugh, Charles R., et al., IEEE Transactions on Computers, vol. C-22, No. 12, Dec. 1973, pp. 1045-1047.
“Computer Arithmetic,” Hennessy, J.L., et al., Appendix A of Computer Architecture: A Quantitative Approach 2nd Edition, Morgan Kaufman Publishers, San Mateo, CA 1996, pp. A-7 thru A10, and A-46 thru A-57.
“SPIM: A pipelined 64 × 64-bit Iterative Multiplier,” Santoro, Mark R., et al., IEEE Journal of Solid-State Circuits, vol. 24, No. 2, Apr. 1989, pp. 487-493.
Herbert Jeffrey Charles
Hossain Razak
Blakely , Sokoloff, Taylor & Zafman LLP
Chaki Kakali
Holmes Michael B.
LandOfFree
Method and apparatus for performing signed/unsigned... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing signed/unsigned..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing signed/unsigned... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2880246