Computer Organization | Booth’s Algorithm

Booth’s Algorithm is a method for multiplying binary numbers, and it is particularly useful for signed binary numbers. The algorithm was developed by Andrew D. Booth in 1951, and it is an efficient way to perform binary multiplication in digital computers. Booth’s algorithm reduces the number of operations needed for multiplication, especially when there are long sequences of 1’s or 0’s in the multiplier.

Key Concepts of Booth’s Algorithm:

1. Signed Binary Numbers: Booth’s algorithm works with both positive and negative binary numbers (in two’s complement form).
2. Multiplicand and Multiplier: In binary multiplication, the multiplicand is the number to be multiplied, and the multiplier is the number by which the multiplicand is multiplied.
3. Registers: The algorithm uses three main registers:
   • Multiplicand (M): The number that will be multiplied.
   • Multiplier (Q): The number by which the multiplicand will be multiplied.
   • Accumulator (A): The intermediate product is stored here.
   • Q-1: An additional bit used to check the last bit of the multiplier and helps in determining the next step.

Booth’s Algorithm Steps:

1. Initialization:
   • The multiplicand MM and multiplier QQ are stored in registers.
   • The accumulator AA is initialized to 0.
   • The extra bit Q−1Q-1 is initialized to 0.
2. Examine the Last Two Bits (Q₀, Q₋₁):
   • Check the pair of bits formed by the least significant bit of the multiplier (Q₀) and the Q-1 bit:
     • If Q₀Q₋₁ = 01, add the multiplicand to the accumulator.
     • If Q₀Q₋₁ = 10, subtract the multiplicand from the accumulator.
     • If Q₀Q₋₁ = 00 or Q₀Q₋₁ = 11, do nothing.
3. Arithmetic Shift:
   • After performing the addition or subtraction, an arithmetic right shift is performed. This means:
     • Shift the bits of the accumulator and multiplier right by one position.
     • The sign bit of the accumulator is preserved.
     • The new Q-1 is copied from the previous Q₀.
4. Repeat:
   • The process is repeated for a total of n cycles, where n is the number of bits in the multiplier.
5. Result:
   • After the final cycle, the result is contained in the combination of the accumulator and the multiplier register.

Example:

Let’s walk through a simple example:

• Multiplicand M=3M = 3 (in binary: 0011)
• Multiplier Q=6Q = 6 (in binary: 0110)

Assuming both numbers are 4-bit binary numbers, Booth’s algorithm will follow these steps:

Initialization:

• M=0011M = 0011
• Q=0110Q = 0110
• A=0000A = 0000
• Q−1=0Q-1 = 0

First Cycle:

• The last two bits of QQ and Q−1Q-1 are 1010, so we subtract MM from AA:
  • A=A−M=0000−0011=−0011A = A – M = 0000 – 0011 = -0011
• Then, perform an arithmetic right shift:
  • Shift AA and QQ, and update Q−1Q-1:
  • A=−0001A = -0001, Q=0011Q = 0011, Q−1=0Q-1 = 0

Second Cycle:

• The last two bits of QQ and Q−1Q-1 are 1010, so we subtract MM from AA:
  • A=A−M=−0001−0011=−0100A = A – M = -0001 – 0011 = -0100
• Arithmetic right shift:
  • A=−0010A = -0010, Q=1001Q = 1001, Q−1=1Q-1 = 1

Third Cycle:

• The last two bits of QQ and Q−1Q-1 are 0101, so we add MM to AA:
  • A=A+M=−0010+0011=0001A = A + M = -0010 + 0011 = 0001
• Arithmetic right shift:
  • A=0000A = 0000, Q=1100Q = 1100, Q−1=1Q-1 = 1

Fourth Cycle:

• The last two bits of QQ and Q−1Q-1 are 0000, so no operation is performed.
• Arithmetic right shift:
  • A=0000A = 0000, Q=1110Q = 1110, Q−1=0Q-1 = 0

Now, the result of the multiplication is in AA and QQ, which gives us the product in binary: 0011×0110=180011 \times 0110 = 18.

In conclusion, Booth’s algorithm is an efficient way to handle binary multiplication, especially for signed numbers. It minimizes the number of additions and subtractions needed by checking pairs of bits in the multiplier and applying the appropriate arithmetic operations.