booth multiplication algorithm

Question

Is booth algorithm for multiplication only for multiplying 2 negative numbers (-3 * -4) or one positive and one negative number (-3 * 4) ? Whenever i multiply 2 positive numbers using booth algorithm i get a wrong result.

example : 5 * 4

A = 101 000 0 // binary of 5 is 101

S = 011 000 0 // 2's complement of 5 is 011

P = 000 100 0 // binary of 4 is 100

x = 3

y = 3

m = 5

-m = 2's complement of m

r = 4

1. After right shift of P by 1 bit 0 000 100

2. After right shift of P by 1 bit 0 000 010

3. P+S = 011 001 0

   After right shift by 1 bit 0 011 001

4. Discarding the LSB 001100

   But that comes out to be the binary of 12 . It should have been 20(010100)

Answer 1

The problem is you are using 3 bits for m and r, and they must be represented using 4 bits to get unsigned values. (Using just 3 bits, 101 = -3 and 100 = -4, and the result does = 12).

So redoing this with 4 bits, one gets:

example : 5 * 4
A = 0101 0000 0 // binary of 5 is 0101
S = 1011 0000 0 // 2's complement of 5 is 1011
P = 0000 0100 0 // binary of 4 is 0100
x = 4
y = 4
m = 5
-m = 2's complement of m
r = 4
1. After right shift of P by 1 bit 0000 0010 0
2. After right shift of P by 1 bit 0000 0001 0
3. P+S = 1011 0001 0
 After right shift by 1 bit 0101 1000 1
4. P+A = 0010 1001 0 (not 1010 1001 0, since overflow in MSB is ignored)
 After right shift by 1 bit 0001 0100 1
Discarding the LSB gives 00010100 which is 20

which gives the correct answer.