Sunday, 6 April 2014

How to Multiply Using Booth’s Algorithm

In this tutorial, I will discuss how to multiply two numbers using Booth’s algorithm. We will use the 
following problem as our example: 

Calculate 5 x -3 using four bit numbers and Booth's algorithm. Show all steps neatly in a 
table. 

First, convert both numbers to binary. 

5 = 0101 
-3 = 1101 

We see that if we add 0 to the right of both binary conversions, there are four 0 to 1 or 1 to 0 
switches in 0101, and only three switches in 1101. Since three is the smaller of the two, we use 
1101 as our x value and use 0101 as out y value. The next step is to find the two's compliment of 
our y value so that we can do subtraction of y from x. We do this by keeping all 0's up until, and 
including, the first 1 the same. We then flip all the remaining bits. So two's compliment of 0101 
becomes 1011. 

The next step is to set two registers, which we name u and v, to be zero. These are going to be the 
registers where we store our product throughout the working of the problem. We then place these 
registers into a table along with two additional registers x and x-1. Register x is initially set to be the 
predetermined value of x, and x-1 is initially set to be zero. 

 u          v       x    x-1 

0000 0000 1101 0 

The next step is to look at the LSB of x and the number in the x-1 register. If the LSB of x is one, and 
x-1 is zero, we subtract y from u. If LSB of x is zero, and x-1 is 1, then we add y to u. If both LSB of 
x and x-1 are equal, you do nothing and skip to the shifting stage. In our case, the LSB of x is one, 
and x-1 is zero, so we subtract y from u. We then do an arithmetic right shift on u and v, and a 
circular right shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 
1011 
1011 

1101 1000 1110 1 

We then go through the process again using the same rules. This time we see that the LSB of x is 
0 and x-1 is 1. We must now add y to u. Once added, we then do an arithmetic right shift on u and 
v, with the last bit of v dropping off, and a circular right shift on x, also copying the LSB of x into x-1. 
This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 
1011 
1011  
1101 1000 1110 1 
0101 
0010 

0001 0100 0111 0 

Again, we repeat the process again. This time LSB of x is 1 and x-1 is zero. So like we did on the 
first pass, we subtract y from u. We then do an arithmetic right shift on u and v, and a circular right 
shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 
1011 
1011 

1101 1000 1110 1 
0101 
0010 

0001 0100 0111 0 
1011 
1100 

1110 0010 1011 1 

Now on the fourth and final pass, we see that the LSB of x is 1 and so is x-1. This makes it easier 
for us because now we don't have to add the numbers. We only have to do an arithmetic right shift 
on u and v, and a circular right shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 
1011 
1011 

1101 1000 1110 1 
0101 
0010 

0001 0100 0111 0 
1011 
1100 

1110 0010 1011 1 
1111 0001 1101 1 

And we are finished. The result is u followed by v, and we get 11110001. Now to easily check our 
calculations, we take the original question, 5 x -3. This becomes -15. -15 is the two's compliment of 
15. 15 in eight bit binary is 00001111. Taking the two's compliment by the method previously 
described, we get the result 11110001, which is exactly the same as our Booths algorithm answer.