Digital Design / Module 8: Arithmetic and datapaths
45. Multipliers and Booth encoding
Understand the block behind every AI chip.
See it move
The idea
Binary multiplication is shift and add, just as with long multiplication on paper. Each bit of B decides whether a shifted copy of A is added to the total. The product of N-bit and M-bit numbers needs N + M bits.
A sequential multiplier
With one adder and N cycles, area is small and is low.
always_ff @(posedge clk)
if (start) begin
acc <= '0;
a_s <= a;
b_s <= b;
cnt <= N;
end else if (cnt != 0) begin
if (b_s[0]) acc <= acc + a_s;
a_s <= a_s << 1;
b_s <= b_s >> 1;
cnt <= cnt - 1'b1;
endParallel multipliers
To produce a result quickly, generate all partial products at once, then add them in a tree. Wallace and Dadda trees use carry-save adders, which reduce three numbers to two without waiting for carries. A fast adder then finishes the job. Depth grows roughly with log(N), rather than with N.
Booth recoding
Fewer partial products mean less hardware. Radix-4 Booth recoding looks at overlapping groups of three bits of B, and turns them into digits from -2 to +2. Each digit is easy to produce from A by shifting or inverting, so an N-bit multiplication needs only about N/2 partial products. It also handles signed numbers directly. Try several B values in the animation above to see the digits.
Why it matters
Multipliers are the most-repeated block in AI accelerators, DSPs and GPUs. A matrix engine can contain thousands, so small savings add up.
Common mistake
Writing a * b casually, as if it were cheap. It is a single line of RTL, and a large block of logic. Also mind the width: wire [7:0] p = a * b with 8-bit inputs silently discards the top half of the product.
Key ideas
- Multiplication adds shifted partial products.
- Booth recoding reduces the number of partial products.
- Tree structures reduce depth.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
wire [15:0] t = a * b;
Why it failed
The product needs 16 bits, but the intermediate wire has only 8, so the top half is silently thrown away. The output port being wide doesn't help, because the value was already cut. Verilog gives no error for this, though a lint tool would warn you.
Interview questions
coreProduct width of N x M bits?
N + M bits.
basicMultiply 1011 by 1101 using shift-and-add, showing the partial products.
A = 1011 (11) and B = 1101 (13). Going through B from bit 0: bit 0 is 1, add A = 11; bit 1 is 0, add nothing; bit 2 is 1, add A shifted by 2 = 44; bit 3 is 1, add A shifted by 3 = 88. The sum is 11 + 44 + 88 = 143, which is 11 x 13, and it fits in 4 + 4 = 8 bits (10001111).
basicWith 8-bit a and b both equal to 20, what does p hold, and why?
input [7:0] a, b; wire [7:0] p = a * b;
p holds 144, not 400. The product needs 16 bits, but the expression is evaluated at the width of the largest operand or the target, which here is 8 bits, so the top half is discarded: 400 - 256 = 144. Simulation gives 144. Declare p as 16 bits, which is N + M for an N-bit by M-bit product.
coreCompare a sequential shift-add multiplier with a fully parallel one.
The sequential version uses one adder and a few registers, and it takes about N cycles per N-bit product, so it is small but has low throughput. The parallel version generates all N partial products at once and adds them with a tree, producing a result every cycle, or every cycle once pipelined, at a much larger area. The choice depends on how many products per second you need and how much area you can spend.
coreGive the radix-4 Booth digits for the 8-bit value B = 00111100 (60). How many non-zero partial products result?
Take overlapping 3-bit groups (b1 b0 b-1), (b3 b2 b1), (b5 b4 b3), (b7 b6 b5), with b-1 = 0. They are 000, 110, 111 and 001, which give the digits 0, -1, 0 and +1, lowest first. Check: -1 x 4 + 1 x 64 = 60. Only 2 partial products are non-zero, compared with 4 for plain shift-add, since B has four 1 bits.
corea and b are 8-bit unsigned, both equal to 20. Why does p hold 144 here, even though p is 16 bits wide?
input [7:0] a, b;
wire [15:0] p;
assign p = {a * b};A concatenation's operands are self-determined, so inside the braces a * b is evaluated at 8 bits, the width of its operands, before the result is zero-extended to 16. The top half is lost before the assignment widens anything: 400 becomes 144. Simulation confirms 144, while wire [15:0] p = a * b gives 400. Widen the operands inside, or drop the braces.
coresa is declared signed and holds -3, ub is unsigned and holds 5. Why does p show 1265 instead of -15?
reg signed [7:0] sa; reg [7:0] ub; wire signed [15:0] p = sa * ub;
If any operand is unsigned, Verilog evaluates the whole expression as unsigned. So sa is treated as the bit pattern 11111101, which is 253, zero-extended, and 253 x 5 = 1265. Simulation shows 1265. If ub really is an unsigned magnitude, write sa * $signed({1'b0, ub}), which gives -15. If both are meant to be signed, declare both signed.
advancedWhy does radix-4 Booth recoding handle signed (two's complement) multipliers directly, and how is a negative digit applied?
The recoding rewrites B as a sum of digits from -2 to +2 times powers of 4. The top group carries the sign bit with a negative weight, exactly as in two's complement, so a negative B needs no special handling. A digit of -1 or -2 means adding -A or -2A: invert A, or A shifted by one, and add 1. The +1 is usually folded into the tree as an extra bit, so no separate adder is needed.
advancedA carry-save tree reduces partial products 3 rows to 2 at each level. How many levels does it need to reduce 16 rows to 2?
Six levels. Each level turns every full group of 3 rows into 2, and passes the leftovers through. So 16 becomes 11 (5 groups give 10, plus 1), 11 becomes 8, 8 becomes 6, 6 becomes 4, 4 becomes 3, and 3 becomes 2. A fast carry-propagate adder then adds the last two rows. Depth grows with the logarithm of the row count, not linearly.