|
|
Multiplication AluIn 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: a7:0 and b7: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: p07 p06 p05 p04 p03 p02 p01 p00 + p17 p16 p15 p14 p13 p12 p11 p10 0 + p27 p26 p25 p24 p23 p22 p21 p20 0 0 + p37 p36 p35 p34 p33 p32 p31 p30 0 0 0 + p47 p46 p45 p44 p43 p42 p41 p40 0 0 0 0 + p57 p56 p55 p54 p53 p52 p51 p50 0 0 0 0 0 + p67 p66 p65 p64 p63 p62 p61 p60 0 0 0 0 0 0 + p77 p76 p75 p74 p73 p72 p71 p70 0 0 0 0 0 0 0 ------------------------------------------------------------------------------------------- P14 P13 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1 P0 In other words, P15: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
|
 |