wire / wire-format / multiplier
A hardware multiplier computes the product of two n-bit integers. Methods: shift-and-add (O(n^2) gate delay), Booth's algorithm (handles signed, reduces partial products), Wallace tree (parallel reduction of partial products, O(log n) delay), Dadda tree (similar, fewer gates). Modern CPUs use modified Booth encoding + Wallace/Dadda tree + carry-propagate adder.
aka: Hardware multiplier (shift-and-add, Booth, Wallace tree)
spec: Digital arithmetic
A hardware multiplier computes the product of two n-bit integers. Methods: shift-and-add (O(n^2) gate delay), Booth's algorithm (handles signed, reduces partial products), Wallace tree (parallel reduction of partial products, O(log n) delay), Dadda tree (similar, fewer gates). Modern CPUs use modified Booth encoding + Wallace/Dadda tree + carry-propagate adder.
| field | size | meaning |
|---|---|---|
| Partial products | n x n | n partial products, each shifted by its position. E.g., for 4-bit: 4 partial products of 4 bits. |
| Shift-and-add | O(n) iterations | Iterative: if multiplier bit is 1, add multiplicand to accumulator; shift right. O(n) cycles. |
| Booth's algorithm | O(n) iterations | Encodes pairs of multiplier bits: 00/11 -> 0, 01 -> +multiplicand, 10 -> -multiplicand. Reduces partial products for signed multiplication. |
| Modified Booth (radix-4) | O(n/2) iterations | Encodes triples of multiplier bits. Fewer partial products (n/2 instead of n). Most common in modern CPUs. |
| Wallace tree | O(log n) delay | Parallel reduction: 3:2 compressors (full adders) reduce partial products in a tree structure. Fast but area-intensive. |
| Dadda tree | O(log n) delay | Similar to Wallace but minimizes the number of adders. Slightly slower but smaller. |
| Result | 2n bits | Product of two n-bit integers is 2n bits. |
example:
00 00 00 00
Multiplier (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/multiplier
or /wire-format/multiplier.json