Booth multiplication with hardware

Booth algorithm

Booth's algorithm multiplies two signed numbers in 2's complement form. It looks at the multiplier bit pair (Q0, Q-1) and treats a run of 1s as (next higher power − lowest power), so a block of 1s needs only one subtraction and one addition.

1. Load M = multiplicand, Q = multiplier, A = 0, Q-1 = 0, SC = n (number of bits).
2. Look at (Q0, Q-1):
   • 00 or 11: no arithmetic.
   • 10 (start of a run of 1s): A = A − M.
   • 01 (end of a run of 1s): A = A + M.
3. Arithmetic shift right the combined A, Q, Q-1 by one bit (the sign bit of A is kept).
4. SC = SC − 1. If SC ≠ 0 go to step 2; otherwise stop.
5. The 2n-bit product is in A:Q.

Hardware implementation

   +--------+      +----------------+
   |   M    |      | Control / SC   |
   +---+----+      +----------------+
       | n bits        ^  Q0, Q-1 | add/sub, shift
       v               |         v
   +-----------------------------------+
   |  n-bit parallel adder / subtractor |
   +-----------------+-----------------+
                     | n bits
                     v
   +----------+   +---------+   +----+
   |    A     |-->|    Q    |-->|Q-1 |
   | (ASR -->)|   |         |   |    |
   +----------+   +---------+   +----+

• M holds the multiplicand; A (accumulator) starts at 0 and Q holds the multiplier; Q-1 is a one-bit flip-flop.
• The adder/subtractor adds M or its 2's complement to A, as decided by the control unit from Q0 Q-1.
• A, Q and Q-1 form one shift register that does an arithmetic shift right.
• The sequence counter SC counts n cycles.

Flowchart

        +-----------------------+
        | A=0, Q-1=0, SC=n      |
        | M=multiplicand Q=mult |
        +-----------+-----------+
                    v
        +-----------------------+<-----------+
        |   Q0 Q-1 = ?          |            |
        +--+---------+--------+-+            |
         10|       01|     00/11|            |
           v         v         |             |
       A = A - M  A = A + M    |             |
           |         |         |             |
           +----+----+---------+             |
                v                            |
        +-----------------------+            |
        | ASR (A, Q, Q-1)       |            |
        | SC = SC - 1           |            |
        +-----------+-----------+            |
                    v                        |
               SC = 0 ? --- No --------------+
                    | Yes
                    v
              Product in A,Q

Multiply −10 × 6

Five bits are needed (−10 = 10110, 6 = 00110).

Multiplicand M = -10 = 10110, multiplier Q = 6 = 00110, -M = 01010, n = 5 bits.

Step  Action               A      Q      Q-1
-     Initial              00000  00110  0
1     Q0Q-1=00: no change  00000  00110  0
      ASR                  00000  00011  0
2     Q0Q-1=10: A = A - M  01010  00011  0
      ASR                  00101  00001  1
3     Q0Q-1=11: no change  00101  00001  1
      ASR                  00010  10000  1
4     Q0Q-1=01: A = A + M  11000  10000  1
      ASR                  11100  01000  0
5     Q0Q-1=00: no change  11100  01000  0
      ASR                  11110  00100  0

Result in A,Q = 11110 00100 = -60.

Answer: -10 × 6 = -60