Booth's algorithm is a multiplication algorithm which worked for two's complement numbers. It is similar to our paper-pencil method, except that it looks for the current as well as previous bit in order to decided what to do. Here are steps
The reason that the above computation works is because
- If the current multiplier digit is 1 and earlier digit is 0 (i.e. a 10 pair) shift and sign extend the multiplicand, subtract with previous result.
- If it is a 01 pair, add to the previous result.
- If it is a 00 pair, or 11 pair, do nothing.
4 bits
0110 <- 6
x 0010 <- 2
-------------
00000000
- 0110
--------------
11110100
+ 0110
--------------
(1) 00001100 <- 12 (overflow bit ignored)
8 bits
In Booth's algorithm, if the multiplicand and multiplier are n-bit two's complement numbers, the result is considered as 2n-bit two's complement value. The overflow bit (outside 2n bits) is ignored.The reason that the above computation works is because
0110 x 0010 = 0110 x (-0010 + 0100) = -01100 + 011000 = 1100.
Example 2: 0010
x 0110
------------
00000000
- 0010
-------------
11111100
+ 0010
-------------
(1) 00001100
In this we have computed 0010 x 0110 = 0010 x ( -0010 + 1000) = - 00100 + 0010000 = 1100
Download With OUTPUT
EmoticonEmoticon