Booth's Algorithm for Multiplication

Booth's Algorithm for Multiplication

  1:00 AM    Dnyaneshwar Kudande

---

Booth's Algorithm

• Booth's algorithm mainly developed to do signed as well as unsigned binary multiplication. 
• Following flowchart shows the working or Booth's Algorithm:

• From above flowchart we got mainly four conditions to perform operation on Q₀ and Q _-1

Sr. No.	Conditions		Operation
	Q 0	Q -1
1	0	0	Shift Right A, Q, Q-1
2	0	1	A = A + M & Shift Right A, Q, Q-1
3	1	0	A = A - M & Shift Right A, Q, Q-1
4	1	1	Shift Right A, Q, Q-1

Let us solve the example of signed multiplication using Booth's Algorithm.

Example-1 : 6 * -3

Here, M = 0110, Q = +3 = 0011, 

-3 = 1101 (Take 2's complement of +3 for this first take 1's complement of +3 which is 1100 and add 1 to get 2's complement i. e. 1101 ), 

- M = 1010 (Take 2's complement of M).

In this number of bits used in Q are 4 bits, hence total 4 cycles i. e. value of n = 4.

Cycle No.	A	Q                  Q0	Q -1	M	Operation
1	0000	1101	0	0110	Initial Value
	1010	1101	0	0110	A = A - M
	1101	0110	1	0110	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.
2	0011	0110	1	0110	A = A + M
	0001	1011	0	0110	Shift Right A, Q, Q -1 (MSB of A is replaced with 0 because of addition operation.
3	1011	1011	0	0110	A = A - M
	1101	1101	1	0110	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.
4	1110 MSB	1110 LSB	1	0110	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.

  

Hence 6 * - 3 = - 18

   18 = 1 0 0 1 0

  -18 = 0 1 1 0 1

         +          1

= 1 1 1 0 1 1 1 0  ( Result in A & Q. Result is negative so that MSB bits are 111 indicate sign bit)

Example-2 : Example of unsigned multiplication using Booth's Algorithm. 11 * 5

Here, M = 1011, Q = 5 = 0101, 

-M = 0101 (Take 2's complement of M for this first take 1's complement of M which is 0100 and add 1 to get 2's complement i. e. 0101 ), 

In this number of bits used in Q are 4 bits, hence total 4 cycles i. e. value of n = 4.

Cycle No.	A	Q                  Q0	Q -1	M	Operation
1	0000	0101	0	1011	Initial Value
	0101	0101	0	1011	A = A - M
	1010	1010	1	1011	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.
2	0101	1010	1	1011	A = A + M
	0010	1101	0	1011	Shift Right A, Q, Q -1 (MSB of A is replaced with 0 because of addition operation.
3	0111	1101	0	1011	A = A - M
	1011	1110	1	1011	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.
4	0110 0011	1110       0111	1 0	1011 1011	Shift Right A, Q, Q -1 (MSB of A is replaced with 1 because of substraction operation.

  

Hence 11 * 5 = 55

  

55 = 0011 0111 ( Result in A & Q.)