Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-02-21
2004-03-16
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S620000
Reexamination Certificate
active
06708193
ABSTRACT:
TECHNICAL FIELD
This invention relates in general to multipliers, and in specific to a multiplier that comprises a linear summation array for performing both signed and unsigned multiplication using a modified Baugh-Wooley algorithm.
BACKGROUND
Circuitry for multiplying two or more operands is commonly implemented within many electronic circuits of the prior art. For example, microprocessors typically include some type of multiplier circuitry. In prior art multipliers, the well-known “Booth” encoding algorithm is commonly implemented for performing signed and unsigned multiplication. However, the Booth encoding algorithm is a dynamic solution. High-speed multipliers are commonly implemented with “Booth” encoding dynamic circuitry to meet the high frequency goals (such as for a 1 GHz microprocessor). Generally, a dynamic multiplier consumes more power, adds significant clock load, and requires much more design effort to implement and verify electrical reliability than is required for a static multiplier design. The dynamic Booth encoding algorithm of prior art multipliers generally requires a complex multiplexer (“MUX”) structure to be implemented to encode input operands before the partial products of the operands form a multiplier array. The “Booth” encoding MUXes are utilized to minimize the number of partial products for the multiplier. Additionally, all the encoding lines of prior art Booth encoding multipliers are typically very complex and heavy loaded. A multiplier utilizing a Booth encoding algorithm is a standard, well-known implementation for multipliers of the prior art, and therefore is discussed only briefly hereafter.
Generally, a multiplier array is utilized within the Booth encoding algorithm to accomplish multiplication. As a simple example, shown in
FIG. 1
is a multiplier array
40
that results from the multiplication of operands X[3:0] and Y[
3
:
0
]. As shown, the multiplier array of
FIG. 1
includes the partial product elements
42
of the operands and a sign extension
44
for signed mutliplication. As is well known in the art, a multiplier typically includes circuitry to AND each element
42
of the multiplier array
40
, such as element X
0
*Y
0
, to produce a partial product (e.g., the product of X
0
*Y
0
). The partial products of the multiplier array
40
are then input to a CSA array included within the multiplier to generate the final results (i.e., the final sum output and final carry output). The final output for multiplication (i.e., the product of the two operands) is then generated by summing the final sum and carry in an adder. The Booth algorithm is commonly used in prior art multipliers to achieve high speed, parallel multiplication.
A linear summation multiplier uses a CSA array directly, without Booth encoding. For example, as shown in
FIG. 2A
, AND gates, such as AND gates
32
,
34
, and
36
may be included within a multiplier to each receive an input bit from X[
3
:
0
] and from Y[
3
:
0
] to produce an element of the multiplier array
40
as input. For instance, AND gate
36
may receive X
2
and Y
0
as input to produce the partial product for element X
2
*Y
0
of multiplier array
40
as its output. Similarly, AND gate
34
may receive X
1
and Y
1
as input to produce the partial product for element X
1
*Y
1
of multiplier array
40
as its output. Likewise, AND gate
32
may receive X
0
and Y
2
as input to produce the partial product for element X
0
*Y
2
of multiplier array
40
as its output. Of course, additional AND gates may be included within a multiplier to produce the partial products for all of the elements of multiplier array
40
in a like manner. As shown in
FIG. 2A
, the partial products are fed to a CSA array of the multiplier, including CSAs such as CSA
38
, to sum the partial products to generate the final sum and final carry. Once the final sum and final carry are generated by the CSA array, they are added to produce the final product to be output by the multiplier. For example, as shown in
FIG. 2B
, a linear summation multiplier consists of two components, a multiplier CSA array
200
and an adder
202
. In such a linear summation multiplier, multiplier CSA array
200
generates a final sum and carry, which are summed in adder
202
. In a preferred embodiment, adder
202
outputs the final result for the multiplication of the operands.
On the other hand, an example of a Booth encoding multiplier is shown in FIG.
2
C.
FIG. 2C
illustrates a 16-bit by 16-bit Booth encoding multiplier that receives two 16-bit operands (shown as X[
15
:
0
] and Y[
15
:
0
]) and outputs the product of the two operands. The exemplary Booth encoding multiplier of
FIG. 2C
consists of three components: Booth encoding MUXes
270
to minimize the number of partial product terms, a CSA array
272
, and an adder
274
to sum up the final result for the multiplication operation. All three components are implemented with dynamic circuits. For example, to perform 16-bit by 16-bit multiplication (i.e., multiplying two 16-bit operands), a prior art multiplier typically utilizes a dynamic Carry-Save-Adder (CSA) circuitry, such as that of
FIG. 2A
, with the Booth encoding algorithm. In the Booth encoding dynamic solution of the prior art, 16-bit by 16-bit multiplication results in a multiplier array having six columns of CSA for sign extension (e.g., sign extension
44
of
FIG. 1
) in addition to the 16 columns of CSA for the partial product elements (e.g., elements
42
of
FIG. 1
) in the multiplier array, for a total of 22 columns for the entire multiplier array. It should be recognized that the resulting 22 columns of the multiplier array does not correspond to (or “match”) the 16-bit input of an operand. This leads to a different layout pitch for the CSA than that for the input circuitry, and results in very complex routing in the layout for input operand signals.
The dynamic multiplier circuitry of the prior art utilizing Booth encoding is problematic for several reasons. First, because the resulting multiplier array results in a greater number of columns than the number of bits in the operands (i.e., because additional to columns are required for sign extension), massive routing complexity is required in the multiplier array. Furthermore, the dynamic circuitry solution of such prior art multipliers consumes an undesirably large amount of power (due to the dynamic circuit and clock) and requires an undesirably rigorous circuit check to ensure that the circuitry functions properly. Also, due to the relatively large number of components required in prior art dynamic multiplier circuitry, such multiplier circuitry consumes an undesirably large amount of surface area and requires an undesirably high cost to be implemented.
Also, another algorithm known as the “Baugh-Wooley” algorithm is well known in the prior art and is commonly implemented in multipliers for performing signed multiplication. The Baugh-Wooley algorithm implementation typically utilizes a linear summation array that results in fewer components and less complexity than multipliers using the Booth encoding algorithm. However, such prior art multipliers implementing a linear summation array utilizing the Baugh-Wooley algorithm only allow for signed multiplication to be performed. Accordingly, such multiplier implementations are severely limited in that they are unable to perform unsigned multiplication.
SUMMARY OF THE INVENTION
In view of the above, a desire exists for a high-speed multiplier that includes a linear summation array for performing both signed and unsigned multiplication. A further desire exists for a multiplier having a static design. Still a further desire exists for a multiplier that reduces the amount of circuitry and routing complexity of prior art multipliers.
These and other objects, features and technical advantages are achieved by a system and method which provide a multiplier comprising a linear summation array that is implemented in a manner that enables both signed and unsigned mul
Do Chat C.
Ngo Chuong Dinh
LandOfFree
Linear summation multiplier array implementation for both... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linear summation multiplier array implementation for both..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear summation multiplier array implementation for both... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266015