High speed pipeline multiplier with virtual shift
AssigneeAgere Systems Inc.
InventorsHan Quang Nguyen, Manosha S. Karunatilaka
Life of this patent
Estimating the term…
Abstract
Disclosed is a method and apparatus for accomplishing 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 multistate logic configurations of the prior art. “Virtual shifts” are achieved by allocating one or more positions, within a register storing the partial products, as place holders, typically zeroes. These place holders can be inserted in a single clock cycle and do not require the multi-staged shift register configurations of the prior art.
Claims12
A method for properly aligning partial products of binary numbers stored in registers in a multiplier device, comprising the steps of:
- determining a quantity of place holders required to properly align the partial products;
- determining appropriate positions in said registers for each of said place holders;
- and
- assigning place holders to the appropriate place holder positions in said registers.
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 said multiplier Y by all of said bits of said multiplicand M to produce Y partial products;
- storing each of said partial products in a separate (X+1) bit register, wherein one of said bit positions of each of said (X+1) bit registers is permanently set at zero;
- adding said stored partial products in pairs by first grouping said (X+1) bit registers into adjacent pair groups, beginning with said (X+1) bit register corresponding to the least significant bit (LSB) of said 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 said bit positions of each of said (X*2) bit registers are permanently set at zero;
- adding the values stored in said (X*2) bit registers;
- and
- outputting the added values stored in said (X*2) bit registers as the product of M*N.
A multiplying apparatus for multiplying an X-bit binary multiplicand M by a Y-bit multiplier N, comprising:
- a multiplexing device separately multiplying said multiplicand M by each bit of said multiplier N and outputting a first group of partial products;
- a first storage device storing said first group of partial products;
- a pairing structure dividing said first group of partial products into pairs;
- a first adding device adding together the partial products comprising each of said pairs;
- a second storage device storing the added partial product pairs together as a second group of partial products;
- and
- a second adding device adding the second group of partial products together to produce the product of M*N.
Dependencies are inferred from the claim text.