What is Booth's Algorithm?

Booth's Algorithm is a method for multiplying binary numbers in signed 2’s complement form. It was created by Andrew Booth in 1951 to make multiplication faster and more efficient, especially when dealing with negative numbers.

The algorithm works by examining the bits of the multiplier and deciding whether to add, subtract, or do nothing to the partial product. It reduces the number of operations needed by skipping over strings of 0’s and handling strings of 1’s more efficiently.

The advantages include faster multiplication, lower hardware requirements, and better performance with signed numbers. However, it can be more complex to understand, has higher latency, and is limited to signed numbers. Booth’s algorithm is widely used in digital signal processors (DSPs), microprocessors, cryptography, and other hardware applications where efficient multiplication is needed.

Example: Multiply -5 and -3

Step 1: Represent the numbers in binary (using 4 bits for simplicity).

• -5 in 4-bit 2's complement is 1011.
• -3 in 4-bit 2's complement is 1101.

Step 2: Set up the registers:

• Multiplicand (M) = -5 = 1011
• Multiplier (Q) = -3 = 1101
• We also add an extra bit (Q-1) which is 0, and an accumulator (A) initialized to 0:
  A = 0000, Q = 1101, Q-1 = 0

Step 3: Follow the Booth’s Algorithm rules.

1. Check the last two bits of Q and Q-1:

   • Q = 1101, Q-1 = 0 → the last two bits are "10", so we subtract the multiplicand (M) from A.
   • A = A - M = 0000 - 1011 = 0101.

2. Shift right the entire A and Q (including Q-1):

   • After shifting right: A = 0010, Q = 1110, Q-1 = 1.

3. Repeat the process for the next pair of bits:

   • Q = 1110, Q-1 = 1 → the last two bits are "11", so no change to A.
   • After shifting: A = 0001, Q = 1111, Q-1 = 0.

4. Continue the process until all bits are processed.

Final Result:

After completing the steps, the result of multiplying -5 and -3 is in A and Q:
A = 0001, Q = 0011, which is 15 in decimal (the product of -5 and -3).

So, Booth's Algorithm successfully multiplied -5 and -3 to give 15.