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.
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 xe2x80x9cBoothxe2x80x9d 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 xe2x80x9cBoothxe2x80x9d 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 (xe2x80x9cMUXxe2x80x9d) structure to be implemented to encode input operands before the partial products of the operands form a multiplier array. The xe2x80x9cBoothxe2x80x9d 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 X0*Y0, to produce a partial product (e.g., the product of X0*Y0). 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 X2 and Y0 as input to produce the partial product for element X2*Y0 of multiplier array 40 as its output. Similarly, AND gate 34 may receive X1 and Y1 as input to produce the partial product for element X1*Y1 of multiplier array 40 as its output. Likewise, AND gate 32 may receive X0 and Y2 as input to produce the partial product for element X0*Y2 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. 2C. 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 xe2x80x9cmatchxe2x80x9d) 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 xe2x80x9cBaugh-Wooleyxe2x80x9d 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.
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 multiplication to be performed. A preferred embodiment utilizes a modified Baugh-Wooley algorithm to enable an optimum even-and-odd linear summation array for performing both signed and unsigned high speed multiplication. That is, a preferred embodiment enables a linear summation array that is smaller in size and simpler in design than the multiplier arrays typically implemented for signed multiplication in the prior art. For example, suppose 16-bit by 16-bit multiplication is being performed, a preferred embodiment utilizes a linear summation array that is 16 by 14, rather than the prior art multiplier arrays that are typically 22 by 14 because of the additional sign extension columns utilized in prior art designs.
Therefore, the resulting columns of the multiplier array of a preferred embodiment exactly fit into the input pitch of the operands, which dramatically reduces the number of circuitry components required to be implemented for the multiplier array, as well as the complexity of routing within the multiplier array. Additionally, a preferred embodiment implements a static design for performing signed and unsigned multiplication, which further reduces the number of components, complexity, cost, and power consumption of the multiplier. The modified Baugh-Wooley algorithm of a preferred embodiment translates a signed operand to an unsigned operand to greatly simplify the sign extension for multiplication, and to enable a relatively small multiplier array that does not include sign extension columns to be utilized for performing signed multiplication. The modified Baugh-Wooley algorithm of a preferred embodiment also enables the multiplier to perform unsigned multiplication.
It should be appreciated that a technical advantage of one aspect of the present invention is that a multiplier is provided which includes a linear summation array for performing both signed and unsigned multiplication. More specifically, a preferred embodiment utilizes the Baugh-Wooley algorithm to perform both signed and unsigned multiplication. Furthermore, a preferred embodiment provides a static design for performing both signed and unsigned multiplication. A further advantage of one aspect of the present invention is that an even-and-odd structured linear summation is utilized for both signed and unsigned multiplication, which allows for a static structure that is much simpler than the prior art Booth encoding structures for performing signed multiplication. The even-and-odd structured linear summation enables high-speed static multiplier design that is similar to dynamic Booth encoding multiplier speed. Therefore, one advantage of one aspect of the present invention is that it enables a much simpler multiplier design with less area, less cost and less power than is commonly required for prior art multipliers that perform signed and unsigned multiplication. Thus, one advantage of one aspect of the present invention is that a multiplier is disclosed that has a multiplication array that requires less circuitry and less routing complexity than is required for signed multiplication in prior art multipliers. Furthermore, an advantage of one aspect of the present invention is that a static design for a multiplier is disclosed that may reduce the power of the circuitry. For example, the current capacitive load of a preferred embodiment may be reduced by 60 percent or more below that typically required in prior art multipliers due to a smaller and simpler design. Additionally, a further advantage of one aspect of the present invention is that a multiplier is disclosed that may perform high-speed multiplication while providing a multiplier that is smaller, less complex, and more reliable than prior art multipliers. For instance, the multiplier of a most preferred embodiment is operable at a frequency 1 gigahertz or higher.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.