Patent ID: 7769797
Filing Date: 2010-08-03
Classification: G06F

Abstract:
1. A multiplication apparatus having a plurality of identical partial multiplication modules, for receiving a multiplicand having m bits, wherein m is a positive integer, and a multiplier having n bits, wherein n is a positive integer, and for performing multiplication according to an execution instruction to generate a multiplication output, the multiplication apparatus comprising: a multiplier and multiplicand extractor for dividing each multiplicand into k partial multiplicands, wherein k is a positive number, dividing each multiplier into l partial multipliers, wherein l is a positive number, and generating k partial input pairs by combining the partial multiplicands with the respective partial multipliers; a multiplication executor including k identical partial multiplication modules, each for receiving one of the k partial input pairs and outputting one partial carry and one partial product by multiplying the partial multiplicand by the partial multiplier in the received partial input pair; and an output generator configured to selectively execute a Carry Save Adder (CSA) algorithm and an addition operation for combining k partial carries with k partial products according to the execution instruction to generate a final output.