Booth’s algorithm is a powerful algorithm that is used for signed multiplication. It generates a 2n bit product for two n bit signed numbers.

The flowchart is as shown in Figure 1.

The steps in Booth’s algorithm are as follow:

1) Initialize A, $Q_{-1}$ to 0 and count to n

2) Based on the values of $Q_0$ and $Q_{-1}$ do the following:

• if $Q_0$ , $Q_{-1} = 0,0$ then Right shift A,Q,$Q_{-1}$ and finally decrement count by 1

• If $Q_0$, $Q_{-1} = 0,1$ then Add A and B store in A, Right shift A,Q,$Q_{-1}$ and finally decrement count by 1

• If $Q_0$, $Q_{-1} = 1,0$ then Subtract A and B store in A, Right shift A,Q,$Q_{-1}$ and finally decrement count by 1

• If $Q_0, Q_{-1} = 1,1$ then Right shift A,Q,$Q_{-1}$ and finally decrement count by 1

3) Repeat step 2 till count does not equal 0.