High speed multiplier using carry-save/propagate pipeline with sparse carries
AssigneeInternational Business Machines Corporation
InventorsRobert C. Letteney, Samuel R. Levine, David T. Shen, Arnold Weinberger
Life of this patent
Estimating the term…
Abstract
A high speed multiply apparatus minimizes latch requirements and I/O pin requirement between chips by a new configuration which iteratively adds four multiples of a multiplicand in a stage of 4-2 carry save adders which then feed four-bit parallel adders each having four sum outputs and a carry output from the highest order bit position. Only the sum outputs are latched and then fed to a carry propagate adder on each iteration for addition to the previous partial products. Only the single carry output from each of the 4-bit parallel adders needs to be latched and then fed to another 4-bit parallel adder.
Claims7
In a multiplier apparatus wherein p bits of a q-bit (p<q) multiplier word are examined in one iteration to produce r multiples of a multiplicand word, said multiples being added together to produce a partial product for the selected p-bit multiplier portion, said partial product, after having been properly shifted, being added to a partial product to be generated in the next iteration for the next higher-order p-bit multiplier portion to be selected in said next iteration to produce a sum of the newly generated partial product and the previously generated and properly shifted partial products such that after the final iteration of the multiplication a final product of the multiplicand word and the multiplier word is produced;
- a carry-save/propagate adder apparatus for performing iterative addition of the partial products comprising;
- an n-to-2 (n.gtoreq.3) carry-save adder stage having a plurality of n-to-2 carry-save adders, one for each bit position of input operands, and receiving n plural-bit operands including the multiples of said multiplicand word generated in each iteration for reducing said n plural-bit operands to two other plural-bit operands representing a sum and a carry of said n plural-operands,
- at least one first m-bit parallel adder, m being no larger than the number of said n-to-2 carry save adders, one for each m bit positions of said operands, said first m-bit parallel adder receiving corresponding bits of said two other plural-bit operands for providing m output signals representing a sum of the input operands thereto, and a carry from the highest order position thereof,
- a second parallel adder receiving in each iteration said m output signals from said first m-bit parallel adder representing the sum of the input operands to said first m-bit parallel adder and generated in the current iteration, and m output signals generated in the previous iterations and representing high-order portions of the previous partial products;
- and
- means transmitting said carry from said first m-bit parallel adder to a lower order input of said first m-bit parallel adder.
An adder apparatus for performing iterative addition of partial products for multiplication operation comprising;
- a 4-2 carry-save adder stage having a plurality of 4-2 carry-save adders each having four operand inputs, a carry-in port, a sum output, a carry output and a carry-out port, each of said 4-2 carry-save adders receiving four bits from four operand words, one bit from each operand word, at said operand inputs, a carry-in from the next lower-order 4-2 carry-save adder at said carry-in port and producing a carry-out representing a carry from said four operand bits to be transmitted to the next higher-order 4-2 carry-save adder, and a sum and a carry at said sum output and said carry output representing a sum of said four operand bits and said carry-in,
- a plurality of 4-bit parallel adders, one for each 4 bit positions of the operand word, each receiving the sum outputs from the four 4-2 carry-save adders of the corresponding four bit positions and the carry outputs from the lower three orders of the four 4-2 carry-save adders of the corresponding four bit positions and from the next lower-order 4-2 carry-save adder, for providing four output signals representing a sum of said four sets of sum outputs and carry outputs, and a carry from the highest order position;
- a plurality of sum latches, one for each output signal from each of said plurality of 4-bit parallel adders, for receiving and latching said output signals from said 4-bit parallel adders,
- a plurality of carry latches, one for each 4-bit parallel adder, for receiving and latching said carries from the highest order positions of said 4-bit parallel adders;
- a plural-bit parallel adder receiving the latched sums from said sum latches for producing a partial product;
- means for transmitting said carry from each of said 4-bit parallel adders to the lowest order position of the next lower-order 4-bit parallel adder;
- and
- means for shifting by eight bit positions the content of said plural-bit parallel adder representing the sum of previous partial products and feeding back a high-order portion of the shifted content to said plural-bit parallel adder for addition with the newly applied latched sums from said sum latches.
Dependencies are inferred from the claim text.