Booth's Multiplication Algorithm

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. Booth's algorithm involves repeatedly adding one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let X and Y be the multiplicand and multiplier, respectively; and let X and Y represent the number of bits in X and Y.

1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
2. A: Fill the most significant (leftmost) bits with the value of x. Fill the remaining (y + 1) bits with zeros.
3. S: Fill the most significant bits with the value of (-x) in two's complement notation.
4. Fill the remaining (y + 1) bits with zeros.
5.  P: Fill the most significant x bits with zeros. To the right of this, append the value of y. Fill the least significant (rightmost) bit with a zero.
6. Determine the two least significant (rightmost) bits of P.
7. If they are 01, find the value of P + A. Ignore any overflow. Perform right shift
8. If they are 10, find the value of P + S. Ignore any overflow. Perform right shift
9. If they are 00 or 11, Only perform right shift. Use P directly in the next step.
10. Arithmetically shift the value obtained in the previous step by a single place to the right. Let P now equal this new value.
11. Repeat steps 2 and 3 until they have been done y times.
12. Drop the least significant (rightmost) bit from P. This is the product of x and y.

Example :Find the product of -9 * -12

A	(-9)10		9=1001 and 1's Complement  = 0110		2's Complement 0110 +1 = 0111		10111 (1 is sign bit)
S  (A * -1)	(9)10		(1001)2
P	(-12)10		12=1100 and 1's Complement  = 0011		2's Complement 0011 +1 = 0100		10100 (1 is  sign bit)

Y = 00000 = 5 bits, so repeat the process five times.

		X	Y	+1			New Value
	A	10111	00000	0
	S	01001	00000	0
101	P	00000	10100	0	Last two bits is 00	Right Shift >>1	00000  01010  0
100	P	00000	01010	0	Last two bits is 00	Right Shift >>1	00000  00101  0
011	P	00000	00101	0	Last two bits is 10	P + S	00000  00101  + 01001 00000 = 01001 00101 0	Right Shift >>1	00100 10010 1
010	P	00100	10010	1	Last two bits is 01	P + A	00100 10010 + 10111 00000 =11011 10010 1	Right Shift >>1	11101 11001 0
001	P	11101	11001	0	Last two bits is 10	P + S	11101 11001 +01001 0000 0 = 00110 11001 0	Right Shift >>1	00011 01100 1
				-9 * -12	= 108	After dropping the LSB (Least Significant Bit)  we get = 00011 01100		= 1101100 =108

Example :Find the product of 15 * -8

A	(15)10		(15)10=(1111)2
S  (A * -1)	(-15)10		15=1111 and 1's Complement  = 0000		2's Complement 0000 +1 = 0001		10001(1 is  sign bit)
P	(-8)10		8=1000 and 1's Complement  = 0111		2's Complement 0111 +1 = 1000		11000(1 is  sign bit)

		X	Y	+1			New Value
	A	01111	00000	0
	S	10001	00000	0
101	P	00000	11000	0	Last two bits is 00	Right Shift >>1	00000  01100  0
100	P	00000	01100	0	Last two bits is 00	Right Shift >>1	00000  00110
011	P	00000	00110	0	Last two bits is 00	Right Shift >>1	00000  00110
010	P	00000	00011	0	Last two bits is 10	P + S	00000 00011 + 10001 00000 = 10001 00011	Right Shift >>1	11000 10001 1
001	P	11101	11001	0	Last two bits is 11	Right Shift >>1	11100 01000 1
				15 * -8	= -120	After dropping the LSB (Least Significant Bit)  we get = 11100 01000		10001000 = -120

Example :Find the product of 9 * -12

A	(9)10		(9)10=(1001)2
S  (A * -1)	(-9)10		9=1001 and 1's Complement  = 0110		2's Complement 0110 +1 = 0111		10111(1 is  sign bit)
P	(-12)10		12=1100 and 1's Complement  = 0011		2's Complement 0011 +1 = 0100		10100(1 is  sign bit)

		X	Y	+1			New Value
	A	01001	00000	0
	S	10111	00000	0
101	P	00000	10100	0	Last two bits is 00	Right Shift >>1	00000  01010
100	P	00000	01010	0	Last two bits is 00	Right Shift >>1	00000  00101
011	P	00000	00101	0	Last two bits is 10	P + S	00000 00101 + 10111 00000 = 10111 00101	Right Shift >>1	11011 10010 1
010	P	11011	10010	1	Last two bits is 01	P + A	11011 + 10010 + 01001 00000 = 00100 10010	Right Shift >>1	00010 01001 0
001	P	00010	01001	0	Last two bits is 10	P + S	00010 01001 + 10111 000 = 11001 01001	Right Shift >>1	11100 10100 1
				9 * -12	= -108	After dropping the LSB (Least Significant Bit)  we get = 11100 10100		10010100 = -108

Example : Find the product of 3 x 4

A	(3)10		(3)10=(0011)2
S  (A * -1)	(-3)10		-3=011 and 1's Complement  = 100		2's Complement 100 +1 = 101		1101(1 is  sign bit)
P	(4)10		4=100

4 bits Repeat it for four times

		X	Y	+1			New Value
	A	0011	00000	0
	S	1101	00000	0
100	P	00000	0100	0	Last two bits is 00	Right Shift >>1	0000  0010
011	P	00000	0010	0	Last two bits is 00	Right Shift >>1	0000  0001
010	P	00000	0001	0	Last two bits is 10	P + S	0000 0001 + 1101 0000 = 1101 0001	Right Shift >>1	1110 1000 1
001	P	1110	1000	1	Last two bits is 01	P + A	1110 1000 + 0011 0000 = 0001 10001	Right Shift >>1	0000 1100 1
				3 * 4	= 12	After dropping the LSB (Least Significant Bit)  we get = 0000 1100		1100= 12

!!!Once again sorry for delay but I wanted it more descript so student can understand it. Next it will be Digital Electronics. Bye!!!