Booth Multiplier
Booth's algorithm encodes the multiplier so runs of ones become a single add and subtract, cutting the number of partial products.
The Insight
A run of consecutive ones in a binary number, say bits from position j to k, equals 2^(k+1) minus 2^j. So instead of adding a partial product for every one bit, you can add once at the high end and subtract once at the low end. Booth's algorithm turns this identity into a systematic recoding of the multiplier.
The classic radix-2 form scans the multiplier from least to most significant bit, examining each bit together with the bit to its right (an implicit zero starts the process). A 0-to-1 transition triggers a subtraction of the multiplicand, a 1-to-0 transition triggers an addition, and unchanged pairs do nothing but shift.
| cur | prev | action | x |
|---|---|---|---|
| 0 | 0 | shift | 0 |
| 0 | 1 | add M | 0 |
| 1 | 0 | sub M | 0 |
| 1 | 1 | shift | 0 |
Radix-4 Modified Booth
In hardware the modified (radix-4) Booth encoding is standard. It inspects three bits at a time with one bit of overlap, and each group selects one of {-2, -1, 0, +1, +2} times the multiplicand. This halves the number of partial products relative to a plain array, because each step consumes two multiplier bits.
- Fewer partial-product rows to reduce (about n/2 for radix-4)
- -2M and +2M are just shifts; -M and -2M use two's-complement negation
- Sign extension handled with a compact encoding trick
In a Full Multiplier
Modified Booth encoding is usually paired with a Wallace or Dadda reduction tree. Booth cuts the row count going in; the tree reduces those rows in logarithmic depth; a final carry-propagate adder produces the result. Together they form the multiply units in most high-performance datapaths.
The cost is added encoding logic and multiplexers to select the multiplicand multiple per group. For narrow operands the overhead can outweigh the savings, so small multipliers sometimes use a plain array. For wide operands, Booth encoding is a clear win.