Booth multiplication algorithm and hardware

Booth's algorithm multiplies two signed numbers in 2's complement form. It treats a run of 1s in the multiplier as (2^(j+1) - 2^i), so a run of 1s needs only one subtraction at the beginning and one addition at the end. This makes the multiplication of negative and positive numbers uniform, and it is faster when the multiplier has long runs of 1s.

Hardware

              +-----------------+
              |  M (multiplicand)|
              +--------+--------+
                       v
        +-------[ n-bit Adder / Subtractor ]
        |                |
        v                v
   +---------+      +---------+    +----+
   |  A (acc)|----->|    Q    |----| Q-1|
   +---------+  ASR +---------+    +----+
     <-- Shift right (A, Q, Q-1) together -->
   Control logic looks at Q0 and Q-1, with a counter n

• M: multiplicand register. Q: multiplier register (Q0 is the least significant bit).
• A: accumulator, initially 0; A and Q together hold the 2n-bit product at the end.
• Q-1: one extra flip-flop to the right of Q0, initially 0.
• Counter: set to n, the number of bits.

Algorithm

1. Initialise A = 0, Q-1 = 0, M = multiplicand, Q = multiplier, count = n.
2. Look at the pair (Q0, Q-1):
   • 00 or 11: no arithmetic.
   • 10: A = A - M (start of a run of 1s).
   • 01: A = A + M (end of a run of 1s).
3. Arithmetic shift right the combined A, Q, Q-1 (the sign bit of A is kept).
4. Decrement the count. If the count is not 0, go to step 2; else stop. The product is in A:Q.

Example: 7 × (-3), n = 4 bits

M = 7 = 0111, -M = 1001, Q = -3 = 1101 (2's complement of 0011).

Product (A:Q) = 1110 1011 = -21 (in 8-bit 2's complement). Check: 7 × (-3) = -21.

ASR = arithmetic shift right of A, Q and Q-1 together.