Hardware - Is booth multiplication algorithm for multiplying 2 positive numbers

Questions

http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

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 number of bits in m

y = 3 number of bits in r

m = 5

-m = 2 s complement of m

r = 4

• After right shift of P by 1 bit 0 000 100
• After right shift of P by 1 bit 0 000 010
• P+S = 011 001 0
After right shift by 1 bit 0 011 001
• Discarding the LSB 001100
But that comes out to be the binary of 12 . It should have been 20(010100)

  UPDATE      after @ ruakh answer  

5 * 4 = 20

m = 0101 is 5

r = 0100 is 4

A = 0101 0000 0

S = 1010 0000 0

P = 0000 0100 0

• shift P right by 1 bit : 0 0000 0100
• shift P right by 1 bit : 0 0000 0010
• P+S = 10100010
Shifting rightby 1 bit : 1101 0001
• P+A = 1 0010 0001 here 1 is the carry generated
shifting right by 1 bit : 110010000

Leave the LSB : 11001000 (not equal to 20)

Answers

You re not giving enough room for your sign handling. 5 is not 101, but 0101: it has to start with a 0, because values starting with 1 are negative. 101 is actually -3: it s the two s complement of 011, which is 3. Similarly, 4 is not 100, but 0100; 100 is -4. So when you multiply 101 by 100, you re actually multiplying -3 by -4; that s why you get 12.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/8191824/is-booth-multiplication-algorithm-for-multiplying-2-positive-numbers

Related