Multipliers and Compressors

Part 5 · Datapath Synthesis · Intermediate

A multiplier works in three stages. It forms partial products, compresses them to two rows, then adds once.

The three stages of a multiplier.

Partial products feed a compressor tree, and one final addition produces the product.

Stage	Job	Design knob
Partial products	One row per multiplier bit, or one row per two bits with Booth recoding.	Row count: N, or N / 2 with radix-4 Booth.
Compressor tree	3:2 counters shrink many rows to two in a logarithmic number of stages.	Wallace or Dadda target heights per stage.
Final adder	One carry-propagate addition of the two remaining rows.	Ripple for narrow widths, faster families for wide ones.

Lesson	What it covers
Partial products and the array multiplier	AND-gate rows, column heights, and the 4 by 4 array.
Booth radix-4 recoding	Recoding triplets, halved row counts, and an exhaustive Python check.
Compressor trees	3:2 counters, Wallace reduction, and Dadda stage counts.
Signed multiplication	Sign extension and the negated sign-bit row, worked by hand.
Truncation, the final adder, and equivalence	Low-bit truncation, final-adder choice, and a Yosys equivalence proof.

Check yourself What does Booth recoding buy, and what does it cost?

It halves the partial-product count, roughly halving the tree. It costs recoding logic and sign-extension care on every product.

Navigate