Booth's Algorithm

Booth algorithm – step-by-step procedure

1. Choosing multiplicand (M) and multiplier (Q)

   • For the Booth algorithm, it is useful to choose the multiplicand and multiplier carefully
   • The number with fewer bit transitions (01/10-transitions) is chosen as the multiplier (Q)
   • This results in fewer arithmetic operations (add/subtract) during the algorithm
   • Multiplicand and multiplier can generally be swapped; this does not affect the result, only the sequence of operations

2. Initialization

   • The input values are converted into two’s complement binary numbers.
   • Registers are prepared:
   • A: initialize to 0
   • Q: initialize with the multiplier
   • Q-1: an additional bit, initialized with 0
   • M: initialize with the multiplicand

3. Loop over n bits (n = bit width of the multiplier)

   • In each loop iteration, the bit pattern Q₀ Q₋₁ is examined:
   • 10 → Subtract (A = A - M), then arithmetic right shift of the combined register (A, Q, Q₋₁)
   • 01 → Add (A = A + M), then arithmetic right shift of the combined register (A, Q, Q₋₁)
   • 00 or 11 → arithmetic right shift only
   • Overflows during addition/subtraction are discarded (register width remains constant).

4. Repetition

   Repeat step 3: n times.

5. Result

   • After n iterations, the final product of X*Y is obtained in the combination A | Q
   • This result is represented in two’s complement, Q₋₁ is no longer relevant