Multiplication ALU
In digital design, a multiplier or multiplication ALU is a hardware circuit dedicated to multiplying two binary values.
A variety of computer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve computing a set of partial products, and then summing the partial products together. This process is similar to the method taught to primary schoolchildren for conducting long multiplication on base-10 integers, but has been modified here for application to a base-2 (binary) number system.
An unsigned example
For example, suppose we want to multiply two unsigned eight bit integers together: a[7:0] and b[7:0]. We can product eight partial products by performing eight one-bit multiplications, one for each bit in multiplicand a:
p0[7:0] = a[0] * b[7:0] = {8{a[0]}} & b[7:0]
p1[7:0] = a[1] * b[7:0] = {8{a[1]}} & b[7:0]
p2[7:0] = a[2] * b[7:0] = {8{a[2]}} & b[7:0]
p3[7:0] = a[3] * b[7:0] = {8{a[3]}} & b[7:0]
p4[7:0] = a[4] * b[7:0] = {8{a[4]}} & b[7:0]
p5[7:0] = a[5] * b[7:0] = {8{a[5]}} & b[7:0]
p6[7:0] = a[6] * b[7:0] = {8{a[6]}} & b[7:0]
p7[7:0] = a[7] * b[7:0] = {8{a[7]}} & b[7:0]
To produce our product, we then need to add up all eight of our partial products, as shown here:
p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
+ p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
+ p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0
+ p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0
+ p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0
+ p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0
+ p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0
+ p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0
-------------------------------------------------------------------------------------------
P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]
In other words, P[15:0] is produced by summing p0, p1 << 1, p2 << 2, and so forth, to produce our final unsigned 16-bit product.
The impact of signed integers
If b had been a signed integer instead of an unsigned integer, then the partial products would need to have been sign-extended up to the width of the product before summing. If a had been a signed integer, then partial product p7 would need to be subtracted from the final sum, rather than added to it.
Implementations
Older multiplier architectures employed a shifter and accumulator to sum each partial product, often one partial product per cycle. Modern multiplier architectures use something similar to a Wallace tree to add the partial products together in a single cycle. The performance of the Wallace tree implementation is sometimes improved by FPGAs
