| Part of a series on | |||||||
| Arithmetic logic circuits | |||||||
|---|---|---|---|---|---|---|---|
| Quick navigation | |||||||
Components
| |||||||
See also | |||||||
Abinary multiplier is anelectronic circuit used indigital electronics, such as acomputer, tomultiply twobinary numbers.
A variety ofcomputer arithmetic techniques can be used to implement a digital multiplier. Most techniques involve computing the set ofpartial products, which are then summed together usingbinary adders. This process is similar tolong multiplication, except that it uses a base-2 (binary)numeral system.
Between 1947 and 1949 Arthur Alec Robinson worked forEnglish Electric, as a student apprentice, and then as a development engineer. Crucially during this period he studied for a PhD degree at the University of Manchester, where he worked on the design of the hardware multiplier for the earlyMark 1 computer.However, until the late 1970s, mostminicomputers did not have a multiply instruction, and so programmers used a "multiply routine"[1][2][3]which repeatedlyshifts and accumulates partial results,often written usingloop unwinding.Mainframe computers had multiply instructions, but they did the same sorts of shifts and adds as a "multiply routine".
Earlymicroprocessors also had no multiply instruction. Though the multiply instruction became common with the 16-bit generation,[4]at least two 8-bit processors have a multiply instruction: theMotorola 6809, introduced in 1978,[5] andIntel MCS-51 family, developed in 1980, and later the modernAtmel AVR 8-bit microprocessors present in the ATMega, ATTiny and ATXMega microcontrollers.
As moretransistors per chip became available due to larger-scale integration, it became possible to put enough adders on a single chip to sum all the partial products at once, rather than reuse a single adder to handle each partial product one at a time.
Because some commondigital signal processing algorithms spend most of their time multiplying,digital signal processor designers sacrifice considerable chip area in order to make the multiply as fast as possible; a single-cyclemultiply–accumulate unit often used up most of the chip area of early DSPs.
The method taught in school for multiplying decimal numbers is based on calculating partial products, shifting them to the left and then adding them together. The most difficult part is to obtain the partial products, as that involves multiplying a long number by one digit (from 0 to 9):
123 × 456 ===== 738 (this is 123 × 6) 615 (this is 123 × 5, shifted one position to the left) + 492 (this is 123 × 4, shifted two positions to the left) ===== 56088
A binary computer does exactly the same multiplication as decimal numbers do, but with binary numbers. In binary encoding each long number is multiplied by one digit (either 0 or 1), and that is much easier than in decimal, as the product by 0 or 1 is just 0 or the same number. Therefore, the multiplication of two binary numbers comes down to calculating partial products (which are 0 or the first number),shifting them left, and then adding them together (a binary addition, of course):
1011 (this is binary for decimal 11) × 1110 (this is binary for decimal 14) ====== 0000 (this is 1011 × 0) 1011 (this is 1011 × 1, shifted one position to the left) 1011 (this is 1011 × 1, shifted two positions to the left) + 1011 (this is 1011 × 1, shifted three positions to the left) ========= 10011010 (this is binary for decimal 154)
This is much simpler than in the decimal system, as there is no table of multiplication to remember: just shifts and adds.
This method is mathematically correct and has the advantage that a small CPU may perform the multiplication by using the shift and add features of its arithmetic logic unit rather than a specialized circuit. The method is slow, however, as it involves many intermediate additions. These additions are time-consuming. Faster multipliers may be engineered in order to do fewer additions; a modern processor might implement a dedicated parallel adder for partial products, letting the multiplication of two 64-bit numbers be done with only 6 rounds of additions, rather than 63.
Suppose we want to multiply twounsigned 8-bit integers together:a[7:0] andb[7:0]. We can produce eight partial products by performing eight 1-bit multiplications, one for each bit in multiplicanda:
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]where the followingVerilog notation is used:
& symbol stands for a bitwise AND.In order to obtain 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 summingp0,p1 << 1,p2 << 2, and so forth, to produce our final unsigned 16-bit product:
P[15:0] = p0[7:0] + (p1[7:0] << 1) + (p2[7:0] << 2) + (p3[7:0] << 3) + (p4[7:0] << 4) + (p5[7:0] << 5) + (p6[7:0] << 6) + (p7[7:0] << 7)
Suppose we now want to multiply twounsigned 16-bit integers together:u[15:0] andv[15:0] using the 8-by-8-bit multiplier from before. Using thepartial products method (justified by the associativity of multiplication) and running in 8-bit chunks, we have:
p0[15:0] = u[7:0] × v[7:0]p1[15:0] = u[15:8] × v[7:0]p2[15:0] = u[7:0] × v[15:8]p3[15:0] = u[15:8] × v[15:8]
The final product would then be:
P[31:0] = p0 + p1 << 8 + p2 << 8 + p3 << 16
One notices that if only P[15:0] (the lower 16 bits of the result) is required, no computation of p3 is needed.
As described above, the process of multiplication can be split into 3 steps:[6][7]
Older multiplier architectures employed a shifter and accumulator to sum each partial product, often one partial product per cycle, trading off speed for die area. To achieve the ability to perform one accumulation per cycle, a fast adder (something faster than ripple-carry) is required.[8]
Modern multiplier architectures use the (modified)Baugh–Wooley algorithm,[9][10][11][12]Wallace trees, orDadda multipliers to add the partial products together in a single cycle.
In a fast multiplier,the partial-product reduction (i.e. computing partial sums) process usually contributes the most to the delay, power, and area of the multiplier.[6]For speed, the "reduce partial product" stages are typically implemented as acarry-save adder composed of compressors and the "compute final product" step is implemented as a fast adder.
A compressor is any device that takes more bits as input than it generates as output. In the context of multiplier engineering, it refers to an adder with carry-in and carry-out. The basic compressor is the full adder, a "3:2 compressor": many fast multipliers use such a compressor implemented in staticCMOS.
To achieve better performance in the same area or the same performance in a smaller area, multiplier designs may use higher order compressors such as 7:3 compressors;[7][6]implement the compressors in faster logic (such transmission gate logic, pass transistor logic,domino logic);[8]connect the compressors in a different pattern; or some combination.
The performance of theWallace tree implementation is sometimes improved bymodifiedBooth encoding one of the two multiplicands, which reduces the number of partial products that must be summed.
A "single cycle" multiplier (or "fast multiplier") is purecombinational logic.
Ifb had been asigned integer instead of anunsigned integer, then the partial products would need to have been sign-extended up to the width of the product before summing. Ifa had been a signed integer, then partial productp7 would need to be subtracted from the final sum, rather than added to it.
The above array multiplier can be modified to supporttwo's complement notation signed numbers by inverting several of the product terms and inserting a one to the left of the first and last partial product term:
1 ~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+ 1 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]
Where ~p represents the complement (opposite value) of p.
 | This section mayrequirecleanup to meet Wikipedia'squality standards. The specific problem is:Should include proof here. Please helpimprove this section if you can.(December 2025) (Learn how and when to remove this message) |
There are many simplifications in the bit array above that are not shown and are not obvious.
For both types of sequences, the last bit is flipped and an implicit −1 should be added directly below the MSB. When the +1 from the two's complement negation for p7 in bit position 0 (LSB) and all the −1's in bit columns 7 through 14 (where each of the MSBs are located) are added together, they can be simplified to the single 1 that "magically" is floating out to the left. For an explanation and proof of why flipping the MSB saves us the sign extension, see a computer arithmetic book.[13]
Abinary floating-point number contains a sign bit, significant bits (known as the significand) and exponent bits (for simplicity, we don't consider base and combination field). The sign bits of each operand are XOR'd to get the sign of the answer. Then, the two exponents are added to get the exponent of the result. Finally, multiplication of each operand's significand will return the significand of the result. However, if the result of the binary multiplication is higher than the total number of bits for a specific precision (e.g. 32, 64, 128), rounding is required and the exponent is changed appropriately.