Booth's Algorithm

• Booth’s Principle states that “The value of series of 1’s of binary can be given as the weight of the bit preceding the series minus the weight of the last bit in the series.”
• The booth’s multiplication algorithm multiplies the two signed binary integers.
• It is generally used to speed up the performance of the multiplication process.
• Booth’s Algorithm looks in the following manner in terms of flowchart representation:

Terms Used in Booth's Algorithm

• AC stands for Accumulator Counter set as 0 initially.
• M represents Multiplicand Bits.
• -M represents 2’s Complement of M.
• Q represents Multiplier Bits.
• $Q_n$ represents the Last Bit of Multiplier Q.
• $Q_{n+1}$ represents the Incremented value of $Q_n$ by 1. But at the initial state, it is set as 0.
• SC stands for Sequential Counter. It represents a number of bits that is nothing but a total number of bits in the multiplier Q.

Working of Booth's Algorithm

• Set the Multiplicand and Multiplier values in binary bits formats as M and Q, respectively.
• At a starting, set the AC and $Q_{n + 1}$ registers values to 0.
• As an SC represent the number of bits in the multiplier (Q). According to that set the value of SC. The value of SC goes on decreasing with each repetition of the computation loop until its value reaches 0.
• The $Q_n$ represents the last bit of the Q, and the $Q_{n+1}$ shows the incremented bit of $Q_n$ by 1.

• At each iteration Booth’s algorithm checks the condition of $Q_n Q_{n+1}$ bits.

  A] If the bits of $Q_n Q_{n+1}$ represent 01

  • Then Multiplicand Bits (M) is added to the Accumulator Counter (AC = AC + M).
  • Then Arithmetic Right Shift operation performs on AC $Q_n Q_{n+1}$ bits by 1.
  • Then decrease the value of Sequence Counter by 1.

  B] If the bits of $Q_n Q_{n+1}$ represent 10,

  • Then Multiplicand Bits (-M) is subtracted from the Accumulator Counter (AC = AC - M).
  • Then Arithmetic Right Shift operation performs on AC $Q_n Q_{n+1}$bits by 1.
  • Then decrease the value of Sequence Counter by 1.

  C] If the bits of $Q_n Q_{n+1}$ represent 00 or 11

  • Then directly Arithmetic Right Shift operation performs on AC $Q_n Q_{n+1}$ bits by 1.
  • Then decrease the value of Sequence Counter by 1.

• These checking iterations of bits value of $Q_n Q_{n+1}$continues until the value of Sequence Counter (SC) reaches 0.

• Finally when SC =0, the result of the multiplication is stored in AC and Q.

Multiplication of (-7) and 3 by using Booth's Algorithm

M = -7 = (1001) and –M = M’ + 1 = 0111

Q = 3 = (0011)

Value of SC = 4, because the number of bits in Q is 4.

$Q_n = 1$ according to last bit of Q and $Q_{n+1}$ set as 0 at initially.

As, (-7) * 3 = -21

Value stored in AC & Q registers = 11101011

(-7) * 3 = 2’s complement of 11101011= $- (00010100 +1)_2 = - (00010101)_2$

= - (16 + 4 + 1) = -21