Booth’s Algorithm for Multiplication

• The repeated addition algorithm works well multiplying unsigned
  inputs, but it is not able to multiply (negative) numbers in two's
  complement encoding.
• Booth's Multiplication Algorithm is an algorithm that works with
  signed two's complement numbers.

Unsigned binary numbers multiplication process:

• Before discussing Booth’s Algorithm, let us look at the unsigned binary numbers multiplication process. Consider a two 4-bit binary numbers as 1010 (i.e., 10 in decimal) and 1011 (11 in decimal), and its multiplication of these two is given as:

Signed binary numbers multiplication using Booth’s Algorithm:

Circuit Diagram for Signed Multiplication of 8-bit numbers using Booth’s Algorithm

Another Circuit Diagram for Signed Multiplication of 8-bit numbers using Booth’s Algorithm

Signed binary numbers multiplication using Booth’s Algorithm:

a) Booth’s Algorithm is used to multiply two SIGNED numbers.

b) When we multiply two “N-bit” numbers, the answer is “2 x N” bits.

c) Three registers A, Q and M, are used for this process, where Q contains the Multiplier and M contains the Multiplicand. d) A (Accumulator) is initialized with 0.

e) At the end of the operation, the Result will be stored in (A & Q) combined.

f) The process involves addition, subtraction and shifting.

Booth’s Algorithm steps:

• The number of steps required is equal to the number of bits in the multiplier.

1. At the beginning, consider an imaginary register Q-1 beyond LSB of Multiplier and initialize to “0”.

2. Every right-shift in the process will shift each bit of AQQ-1 by 1-bit such that LSB of Multiplier(i.e., Q0) will move into Imaginary Q-1. And the new MSB of Accumulator(A) after shifting will be same as previous MSB.

3. At each step, examine two adjacent Multiplier bits Q0Q-1.

4. If Q0Q-1 are same i.e., 00 or 11, then simply Right-Shift each bit in AQQ-1 by 1-bit.

5. If Q0Q-1 = 01, then ADD M to A (A<- A+M) and then Right-Shift each bit in AQQ-1 by 1-bit.

6. If Q0Q-1 = 10, then Subtract M from A (A<- A-M) and then Right-Shift each bit in AQQ-1 by 1-bit.

• Repeat steps 3 to 6 for all remaining bits of the multiplier . • The final answer will be in A & Q combined.