Booth's Multiplication Algorithm
Booth's algorithm is an efficient method for multiplying two signed binary numbers in two's complement notation.
Steps:
- Initialize: Set A = 0, Q = Multiplier, Q-1 = 0, M = Multiplicand, Count = n (number of bits).
- Check Q0 and Q-1:
Q₀Q₋₁ = 10 → A = A − M (Subtract)Q₀Q₋₁ = 01 → A = A + M (Add)Q₀Q₋₁ = 00 or 11 → No operation
- Arithmetic Right Shift: Shift [A, Q, Q-1] right by 1 bit (preserving sign of A).
- Decrement Count. If Count ≠ 0, go to step 2.
- Result: The product is in [A, Q] (8 bits for 4-bit inputs).
Truth Table (Q₀ Q₋₁)
| Q₀ |
Q₋₁ |
Operation |
| 0 | 0 | No Operation |
| 0 | 1 | A = A + M |
| 1 | 0 | A = A − M |
| 1 | 1 | No Operation |