Multipliers & Booth Encoding

Ground-up guide to CMOS circuit design — transistors, gates, delay, power, memory, datapath and test

What a Multiplier Has to Do

A multiplier is a block that takes two numbers and produces their product. In digital design, those numbers are binary (made of 0s and 1s). If you multiply two 8-bit numbers, the result can need up to 16 bits. So a multiplier is bigger and slower than an adder, and people spend a lot of effort making it fast and small. Multiplication by hand uses the "shift and add" idea. You look at each bit of one number (the multiplier), and for each 1-bit you copy the other number (the multiplicand), shifted left by the bit position. Then you add all those shifted copies together. Each shifted copy is called a partial product (one row of the multiplication that you still need to add up). Let us see this with small numbers. Suppose the multiplicand is 1101 (which is 13) and the multiplier is 1011 (which is 11). For each multiplier bit that is 1, we write a shifted copy of 1101.

Multiplicand A = 1101 (13)
Multiplier   B = 1011 (11)
bit0 = 1 ->  0000001101   (1101 shifted by 0)
bit1 = 1 ->  0000011010   (1101 shifted by 1)
bit2 = 0 ->  0000000000   (zero, no copy)
bit3 = 1 ->  0001101000   (1101 shifted by 3)
Sum  =       0010001111  = 143
Check: 13 x 11 = 143  (correct)

So an N-bit by N-bit multiply makes N partial products. The whole job is two parts: (1) generate the partial products, and (2) add them all up. Step 2 is where most of the delay lives, because adding many numbers takes time.

Generating a partial product bit is easy: it is just an AND gate. Partial product bit = (multiplicand bit) AND (multiplier bit). For an 8x8 multiplier that is 64 AND gates. The hard, slow part is summing the rows.

Array Multipliers

The simplest hardware version is the array multiplier (a regular grid of adder cells that adds partial products row by row). You build a square mesh of full adders. Each cell adds one partial-product bit plus the carry and sum coming from the cell above, and passes results down and sideways. The good thing about an array multiplier is that it is very regular. Regular layouts are easy to draw on silicon and easy to wire. The bad thing is speed. The carry and sum signals have to ripple down through every row and across, so the delay grows roughly with N (the number of bits). Here is a rough delay estimate. Say one full-adder cell has a delay of 90 picoseconds (ps, one trillionth of a second). For an 8x8 array, the worst path crosses about 2N cells.

Cell delay        = 90 ps
Worst path cells  = 2 x N - 1 = 2 x 8 - 1 = 15 cells
Array delay       = 15 x 90 ps = 1350 ps = 1.35 ns
If N doubles to 16:
Worst path cells  = 2 x 16 - 1 = 31 cells
Array delay       = 31 x 90 ps = 2790 ps = 2.79 ns

So delay grows about linearly with N. For wide multipliers this gets slow.

Tree (Wallace) Multipliers

To go faster, we change how we add the partial products. Instead of adding one row at a time, a tree multiplier (also called a Wallace tree, after the idea of compressing many rows in parallel) squeezes many rows together at once. The trick uses a carry-save adder, often called a 3:2 compressor (a cell that takes 3 input bits in one column and produces 2 output bits: a sum and a carry). With these, you can reduce 3 rows to 2 rows in a single layer of delay, no matter how wide the numbers are. You keep stacking layers until only 2 rows remain. Then one normal fast adder finishes the job. The number of reduction layers grows with the logarithm of N, not with N itself. That is the whole point: log growth is much slower than linear growth for big N.

Reducing 8 partial-product rows with 3:2 compressors:
Layer 1: 8 rows -> 6 rows
Layer 2: 6 rows -> 4 rows
Layer 3: 4 rows -> 3 rows
Layer 4: 3 rows -> 2 rows
=> 4 reduction layers
If each compressor layer = 95 ps and final adder = 400 ps:
Tree delay = 4 x 95 + 400 = 380 + 400 = 780 ps = 0.78 ns
Compare array (8x8) above = 1.35 ns. Tree is much faster.

The cost of the tree is irregularity. The wires cross each other in messy ways, so the layout is harder to draw and the wiring takes more space. But for high-speed designs the time saving is worth it.

Booth and Modified-Booth Encoding

The other way to speed up multiplication is to make fewer partial products in the first place. Booth encoding (a scheme that looks at groups of multiplier bits and replaces runs of 1s with add/subtract steps) does exactly that. The most common version is modified-Booth (also called radix-4 Booth). It looks at the multiplier 3 bits at a time, with one bit overlapping between groups. Each group of 3 bits is turned into a single action chosen from this set: 0, +1x, +2x, -1x, or -2x of the multiplicand. Because each group covers 2 new bits, an N-bit multiplier produces only about N/2 partial products instead of N. Half the rows means a smaller, faster tree. Here is the radix-4 Booth lookup table. The 3 bits are the current pair plus the bit to their right.

The "-2x" and "-1x" are easy in hardware: shifting gives the 2x, and inverting plus a carry-in gives the negative. So Booth turns a multiplier into half as many partial products at low extra cost.

A nice bonus: Booth handles signed numbers naturally, because the subtract steps deal with the sign bit cleanly. That is why most fast multipliers use modified-Booth to make the rows, then a tree to add them.

Pipelined Multipliers and the Speed/Area Trade

Even a tree multiplier has some total delay. If you want a new result every clock cycle at a very high clock rate, you can pipeline the multiplier (split it into stages with registers between them, so several multiplies are in flight at once). Each stage does part of the work in one cycle. Pipelining does not make a single multiply finish sooner. It raises throughput (how many results come out per second) while adding latency (how many cycles a single result takes from start to finish). You trade a bit of latency and some register area for a much higher clock rate.

Non-pipelined tree: total delay 780 ps
Max clock = 1 / 780 ps = about 1.28 GHz
One result per cycle, latency 1 cycle.
Split into 3 balanced stages of ~260 ps each (plus 40 ps register overhead):
Stage delay = 260 + 40 = 300 ps
Max clock = 1 / 300 ps = about 3.33 GHz
Latency = 3 cycles, but a new result every cycle.
Throughput rises from 1.28 to 3.33 billion multiplies/sec.

The big picture: you pick array for small and simple, tree plus Booth for fast, and pipelining when you need a steady stream of results at a high clock rate. Each step up the speed ladder costs more area and wiring.

Interview Q&A

product. For each multiplier bit equal to 1, you create a partial product shifted by that bit's position. An N-bit multiplier makes N partial products in the plain method.

so its delay grows roughly with N. A tree uses carry-save (3:2) compressors to reduce many rows in parallel, so its delay grows with log N. For wide operands the tree is much faster.

time and produces about N/2 partial products instead of N. Fewer rows mean a smaller, faster adder tree. It also handles signed numbers cleanly.

clock and several multiplies in flight, but it increases latency because a single result now passes through several clocked stages.

and outputs a sum bit and a carry bit. It reduces three rows to two in one layer of delay, which is the key building block of a Wallace tree.

to just two rows. Those two rows still must be added with real carry propagation, so a fast carrypropagate adder finishes the job.

Key Takeaways

• A multiplier has two jobs: generate partial products (simple AND gates) and add them up (the slow part).
• Array multipliers are regular and small but have delay that grows linearly with N.
• Tree (Wallace) multipliers use 3:2 compressors to cut delay to order log N, at the cost of messy wiring.
• Modified-Booth (radix-4) encoding roughly halves the number of partial products and handles signed numbers naturally.
• Pipelining trades latency and area for throughput, letting the multiplier run at a much higher clock rate.