Describe Booth's algorithm for signed binary multiplication. Explain how it optimizes the multiplication process and discuss its advantages over traditional methods?

Booth's algorithm multiplies two signed numbers in 2's complement form. Its idea is that a run of 1s in the multiplier, such as $0111100$, equals a difference of two powers of 2:

$$2^{6} - 2^{2} = 64 - 4 = 60 = 0111100_2$$

So instead of adding $M$ for every 1 bit, we subtract $M$ at the start of the run and add $M$ after its end.

Procedure. The multiplicand is kept in $M$. The multiplier is kept in $Q$, with an extra bit $Q_{-1} = 0$ on its right. $A$ is cleared to 0. We repeat the following $n$ times, once for each bit of the multiplier. If $Q_0Q_{-1}$ is $10$, we do $A = A - M$. If it is $01$, we do $A = A + M$. If it is $00$ or $11$, we do nothing. Then we shift $A$, $Q$ and $Q_{-1}$ right by one place, keeping the sign of $A$ (arithmetic shift right, ASR). At the end, $AQ$ holds the $2n$-bit product.

Example. Multiply $(+7) \times (-3)$ with 4-bit registers. Here $M = 0111$, $-M = 1001$ and $Q = 1101$.

So $AQ = 11101011$. The leading bit is 1, so the product is negative. Its 2's complement is $00010101 = 21$. Therefore $(+7) \times (-3) = -21$.

How it optimises multiplication. Long runs of equal bits in the multiplier need no additions at all, only shifts. For example, a multiplier with eight 1s in a row needs only one subtraction and one addition, instead of eight additions.

Advantages over the traditional method.

• It handles positive and negative numbers with the same circuit, so no separate sign logic is needed.
• It works directly on 2's complement numbers, so no correction step is needed for a negative multiplier.
• It is faster when the multiplier has long runs of 1s.
• The control is simple, with one add or subtract and one shift per cycle.

The worst case is a multiplier with alternating bits, like $0101$, where every cycle needs an add or subtract. Then Booth's method is no faster than shift-and-add.