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) numeral system.
| Contents |
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[15] 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 Booth encoding one of the two multiplicands, which reduces the number of partial products that must be summed.
External links
- Multiplier Designs (http://www.andraka.com/multipli.htm) targeted at FPGAs