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.

## No comments:

## Post a Comment