Wallace Tree
Logarithmic reduction tree: fastest with a CLA final adder.
Problem
How do you minimize reduction delay from n partial products to a final sum?
How it works
Groups partial product bits in threes and compresses each group with a 3:2 counter (full adder): all groups in parallel. Each level reduces the row count by factor ~1.5. After ⌈log₁.₅(n)⌉ levels, only 2 rows remain. A final carry-propagate adder (RCA or CLA) produces the product.
Key insightO(log n) reduction levels instead of O(n): but the irregular wiring makes layout harder than an array.
Tradeoffs
- Area
- n² FA-eq (same as array)
- Delay
- 1 + 2L + CPA(2n) gate delays
- Best when: Speed is critical: fastest multiplier architecture when paired with CLA.