Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-19
2002-07-16
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S625000
Reexamination Certificate
active
06421699
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for data processing or information handling systems in general and, in particular, to a method and system for a multiplier implementing multiplication in a computer system. Still more particularly, the present invention relates to a method and system for overlapping the process of partial product reduction when implementing multiplication in a computer system.
2. Description of the Prior Art
Applications of modern computer systems are requiring greater speed and data handling capabilities for uses such as multimedia and scientific modeling. Multimedia and scientific modeling require massive data manipulation and an extraordinary amount of high-performance arithmetic and vector-matrix operations. One such operation is the classical multiplier implementing multiplication between two bit registers. One such prior art hard-wired multiplication scheme for implementing multiplication is shown in FIG.
1
. The hard-wired multiplication scheme is basically divided into two parts. The first part produces, using a multiplier
20
, multiplicand
22
and a Booth encoder
24
a matrix of partial product rows
26
. These partial product rows
26
are then reduced to two rows (sum and carry)
34
by some kind of counter or Wallace tree
32
, shown in
FIG. 1
using a 4/2 carry save adder (CSA) compressor
28
(and by way of example may use a 3/2 or 7/3 compressor). The second part reduces the two rows to one by using a big 2/1 adder
30
, such as Carry Propagate Adder (CPA) or Carry-Select Adder (CSA) resulting in a final product
36
. Prior art multipliers normally implement these two parts separately, and in many cases they are in separate pipeline stages. To reduce the propagation delay, one possible approach is to combine the two parts such that the final adder can start its calculation before the CSA tree finishes its tournament.
One such prior art solution for combining the two parts such that the final adder can start its calculation before the CSA tree finishes its tournament is shown in FIG.
2
. As shown in
FIG. 2
, the addition of the lower 30 bits
38
utilizing a 16-bit carry select adder
42
are overlapped with the reduction of the partial product array
40
. However, this 30-bit addition overlap does not provide a speed gain, since the left over 76 bits
44
will need the same number of logic stages
46
(8 stages) to complete the final addition as the original 106 bits do.
Therefore, there is a need for a method and system to overlap the final addition on the higher order bits as well as the lower order bits to reduce the propagation time effectively. Additionally, it would be desirable to reduce the number of left-over bits so that the final addition on these bits requires fewer logic stages to complete its process, and thus reduce the propagation delay. The subject invention herein solves these problems in a new and unique manner that has not been part of the art previously.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for performing multiplication utilizing a speedup multiplier in a computer system or information handling system.
It is another object of the present invention to provide an improved method and system when performing multiplication by overlapping the process of partial product reduction in a computer system or information handling system.
The foregoing objects are achieved as is now described. The method and system of the present invention overlaps the process of partial product reduction and the final adder in both higher- and lower-order bits when performing multiplication. The method and system reduces the number of left-over bits such that the final addition on these bits requires fewer logic stages to complete its process thereby reducing the propagation delay.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5291431 (1994-03-01), Ho et al.
patent: 5818743 (1998-10-01), Lee et al.
patent: 5870322 (1999-02-01), Kim
patent: 6021424 (2000-02-01), Chu
patent: 6183122 (2001-02-01), De Angel
Dhong Sang Hoo
Lin Perng Shyong
Silberman Joel Abraham
LandOfFree
Method and system for a speedup of a bit 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 Method and system for a speedup of a bit multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for a speedup of a bit multiplier will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2819290