Booth's Algorithm (Radix-2)
Recodes the multiplier to skip runs of 1s and handle signed natively.
Problem
How do you reduce additions in sequential multiplication and handle signed operands natively?
How it works
Recodes multiplier B from binary {0,1} to signed digits {-1, 0, +1} using d[i] = b[i-1] - b[i] (where b[-1] = 0). Each d[i] means: add A (+1), subtract A (-1), or skip (0). Runs of consecutive 1s collapse: 0111 becomes +1000 -0001 (two operations instead of three).
Key insightSigned multiplication for free: two’s complement just works because the recoding naturally handles the sign bit.
Tradeoffs
- Area
- 2n FA-eq (same as S&A)
- Delay
- 2n² gate delays (same worst case)
- Best when: Signed multiplication, or multipliers with long runs of 1s.