High speed pipeline multiplier with virtual shift

Details High speed pipeline multiplier with virtual shift High speed pipeline multiplier with virtual shift

2000-07-18

2003-11-18

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06651079

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to binary multipliers; and more particularly, to an improved pipeline multiplier and multiplying method.
BACKGROUND OF THE INVENTION
The multiplication of binary numbers is an inherent part of the operation of any digital system. The multiplication of two binary numbers is performed in essentially the same manner as the multiplication of decimal numbers, by taking the product of a multiplicand and a multiplier. With binary numbers, this process consists of examining the successive bits of a multiplier, beginning with the least significant bit (“LSB”) of the multiplier. If the multiplier bit is a “1”, the multiplicand is recorded as a first partial product (assuming that the multiplier is more than a single digit binary number); if the multiplier bit is a “0”, zeroes are recorded as the first partial product. Moving from the LSB to the most significant bit (MSB) of the multiplier, each multiplier bit is examined in this manner. In a well known manner, each of the partial products recorded in successive lines are shifted one bit position to the left relative to the previous line.
When all of the multiplier bits have been examined and the partial products placed in appropriate alignment by the shifting process, the partial products in the successive lines are added to produce a final product. The purpose of the shifting step described above is to take into account the decimal position of the multiplier bit being examined, to properly align each of the successive partial products. Each partial product is shifted to the left by the number of bits corresponding to the bit position of the multiplier bit in question.
The following calculation llustrates: the above-described multiplication process using a multiplier of 1001 and a multiplicand of 1011:
1001 
multiplicand
× 1011 
multiplier
1001 
1001 
partial
0000 
products
1001  
1100011
final product
Devices for performing multiplication, called “multipliers,” are well known. Typically, multipliers are either “synchronous” (performing each of the operations which result in the final product in a synchronized manner according to a timing sequence controlled by the operation of a clock) or “asynchronous” (performing the operations which result in the final product without synchronization and thus without the need for control by a clock).
In a typical synchronous multiplier, each bit of the multiplicand is individually multiplied by each bit of the multiplier, with the result of the multiplication being stored in a register. This arrangement is known in the art as a “synchronous shifter and adder.” Shift registers are employed so that, with each successive multiplier bit, the partial product corresponding to the bit position of the multiplier bit is physically shifted and place holders (typically zeroes) are inserted (i.e., clocked in) in the positions vacated by the shifting process. Once each multiplier bit has been utilized to obtain all of the partial products, the now properly aligned partial products are added to result in the final product.
Because of the numerous shift steps required to perform multiplication using a to synchronous shifter and adder, many clock cycles are consumed during the shifting and adding operations, thereby slowing down the overall multiplication process. In addition, the shift registers increase the physical size of the multiplier, which is undesirable in an age where miniaturization is the focus of most circuit designers.
Asynchronous multipliers utilize multistage logic circuits (e.g., AND OR gates) to perform the multiplication processes. The use of multistage logic circuits eliminates the need to obtain partial products and thus alignment is not an issue. Further, since there are no synchronous elements such as flip flops, there is no clocking control required. However, asynchronous multipliers require large numbers of ASIC gates. For example, for an asynchronous 4×4 multiplier (i.e., one capable of obtaining the product of two 4-bit numbers) approximately 44 ASIC cells are needed. This increases the size of the multiplier and significantly slows down its operation.
Accordingly, it would be desirable to have a synchronous binary multiplier in which all of the required place holders are assigned or inserted via a single “virtual shift” clock cycle without the need to employ shift registers.
SUMMARY OF THE INVENTION
It is an object of the present invention to accomplish high speed multiplication of binary numbers using a single clock cycle to achieve the same computational power provided by the multiple clock cycle shift register configurations or the asynchronous no multistate logic configurations of the prior art.
In accordance with the present invention, instead of serially multiplying each bit of the multiplicand individually by each bit of the multiplier, and shifting each successive product to properly align the partial products prior to the final adding step, “virtual shifts” are achieved by allocating one or more positions, within a register storing the partial products, as place holders, typically zeroes.
In one embodiment, the present invention comprises a method for properly aligning partial products stored in registers in connection with the multiplication of binary numbers, comprising the steps of: determining a quantity of place holders required to properly align the partial products; determining the appropriate position in the registers for each of the place holders; and assigning place holders to the appropriate place holder positions.
In another embodiment, the present invention is a method for multiplying an X-bit binary multiplicand M by a Y-bit multiplier N, comprising the steps of: separately multiplying each bit of the multiplicand M by all of the bits of the multiplier N to produce Y partial products; storing each of the partial products in a separate (X+1) bit register, wherein one of the bit positions of each of the (X+1) bit registers is permanently set at zero; adding the stored partial products in pairs by first grouping the (X+1) bit registers into adjacent pair groups, beginning with the (X+1) bit register corresponding to the least significant bit (LSB) of the multiplier N, and then adding the two partial products stored in each adjacent pair group; storing the results of each added partial product pairs in a separate (X*2) bit register, wherein (Y−2) of the bit positions of each of the (X*2) bit registers are permanently set at zero; adding the values stored in the (X*2) bit registers; and outputting the added values stored in the (X*2) bit registers as the product of M*N.
In a further embodiment, the present invention comprises a multiplier for multiplying an X-bit binary multiplicand M by a Y-bit multiplier N, comprising: a first one-bit multiplier separately multiplying the multiplicand M by each bit of the multiplier N and outputting a first group of partial products; storage means for storing the first group of partial product; dividing means for dividing the first group of partial products into pairs; adding means for adding the partial products comprising each of the pairs together; storage means for storing the added partial product pairs together as a second group of partial products; and adding the second group of partial products together to produce the product of M*N.
The present invention will now be described with reference to the following drawings, in which like reference numbers denote the same element throughout.


REFERENCES:
patent: 4970676 (1990-11-01), Fling
patent: 5528531 (1996-06-01), Toyama et al.
patent: 6144980 (2000-11-01), Oberman
patent: 6263357 (2001-07-01), Choe

Affiliated with

Also associated with

Rating

High speed pipeline multiplier with virtual shift does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High speed pipeline multiplier with virtual shift, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed pipeline multiplier with virtual shift will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3129856