Booths Multiplication Algorithm
Unsigned and Signed Multiplication is covered using booths algorithm is explained in this article. The technique of adding a number to itself a specific number of times is know as multiplication. Unsigned numbers are always the positive numbers. Click here to access whole serie of computer organizartion and architecture.
Booths unsigned multiplication algorithm flowchart
Let us consider an example of multiplying 5 with 3
Ex: 5(multiplicant) x 3(multiplier) = 15
In binary format: 5(multiplicand) 0 1 0 1 x 3(multiplier) 0 0 1 1
Result = 0 0 0 1 1 1 1
This process is fast and it works.
Booths Unsigned multiplication Algorithm
1)Number of steps is equal to the number of bits in the multiplier.
2)At every step examine the multiplier bits.
3)If the multiplier bit is 1 then the partial product is a multiplier.
4)If the multiplier bit is 0 then the partial product is 0.
5)Add all the partial bits.
To take 4 separate registers to store each partial product when that is not even the actual answer,we tend to waste a lot of memory.Hence we accumulate these products into one register known as Accumulator register. These are the steps involved in booths unsigned multiplication algorithm.
Accumulator
- The size of multiplier and multiplicand combined is the size of the accumulator.
- Initially the accumulator will have all zeros.
- Then add the first partial product to higher bits in accumulator.
- Do the right shift(after every step right shift is done)
Accumulator(A) Multiplier(Q) Multiplicand(m)
As Accumulator is growing it occupies a multiplier and the multiplier will release the bits. Accumulator plays an important role in Booths unsigned multiplication algorithm.
For 5 x 3:
Accumulator
0 0 0 0 0 0 0 0
+0 1 0 1
0 1 0 1 0 0 0 0 →multiplier bit is 1
0 0 1 0 1 0 0 0
0 1 0 1 →multiplier bit is 1
0 1 1 1 1 0 0 0
0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 0 →multiplier bit is 0
0 0 0 0 1 1 1 1 →multiplier bit is 0
Booths unsigned multiplication algorithm
1)From the multiplier the bit moves to the control unit.Control unit checks if the bit is 0 or 1.
2)If the bit is 1,add multiplicand to the accumulator.
3)Right shift happens from accumulator to the multiplier bit.
4)If the bit is 0 then add zeros(0) to the accumulator and right shift.
- This method only works for unsigned numbers,That is when Booth’s Algorithm is used.Booth’s algorithm is called signed multiplication.
Signed Multiplication
Booths Multiplication Algorithm
Booth’s algorithm for multiplication, It is possible to multiply the two signed binary numbers in 2’s complement using the booth algorithm. The following are the steps that are involved in booths algorithm.
1)Number of steps is equal to number of multiplier
2)At each step examine two consecutive bits of multiplier from LSB
3)Observe the transition of bits from imaginary 0(zero) to LSB
- If transition is from 0 to 1 subtract
- If transition is from 1 to 0 addition is done.
4)Otherwise no arithmetic operation is performed.
5)In every step do right shift.
Here is the booths multiplication algorithm with example
Ex: 5 x 7
5 = 0 1 0 1 – 5 = 1 0 1 1
7 = 0 1 1 1 -7 = 1 0 0 1
1)first step:
| A | Q(7) | Imaginary 0Q-1 | m(5) | |
| 0 0 0 0 | 0 1 1 1 | 0 | 0 1 0 1 | |
| 0 to 1 Sub m Right shift | 1 0 1 1 1 0 1 1 1 1 0 1 | 0 1 1 1 1 0 1 1 | 0 1 |
2)second step:
| 1 to 1 Right shift | 1 1 1 0 | 1 1 0 1 | 1 |
3)third step:
| 1 to 1 Right shift | 1 1 1 1 | 0 1 1 0 | 1 |
4)Fourth step:
| 1 to 0 Add m Right shift | +0 1 0 1 0 1 0 0 | 0 1 1 0 | 1 |
Table for Booths multiplication Algorithm:
| A | Q(7) | Imaginary 0Q-1 | m(5) | |
| 0 0 0 0 | 0 1 1 1 | 0 | 0 1 0 1 | |
| 0 to 1 Sub m Right shift | 1 0 1 1 1 0 1 1 1 1 0 1 | 0 1 1 1 1 0 1 1 | 0 1 | |
| 1 to 1 Right shift | 1 1 1 0 | 1 1 0 1 | 1 | |
| 1 to 1 Right shift | 1 1 1 1 | 0 1 1 0 | 1 | |
| 1 to 0 Add m Right shift | +0 1 0 1 0 0 1 0 | 0 1 1 0 0 0 1 0 | 1 0 |
Result: 0 0 1 0 0 0 1 0
Table for Booths multiplication Algorithm:
For 5 x -7
| A | Q(-7) | Imaginary 0Q-1 | m(5) | |
| 0 0 0 0 | 1 0 0 1 | 0 | 0 1 0 1 | |
| 0 to 1 Sub m Right shift | 1 0 1 1 1 0 1 1 1 1 0 1 | 1 0 1 1 1 1 0 0 | 0 1 | |
| 1 to 0 Add m Right shift | +0 1 0 1 0 0 1 0 0 0 0 1 | 1 1 0 0 0 1 1 0 | 1 0 | |
| 0 to 0 Right shift | 0 0 0 0 | 1 0 1 1 | 0 | |
| 0 to 1 sub m Right shift | +1 0 1 1 1 0 1 1 1 1 0 1 | 1 0 1 1 1 1 0 1 | 0 1 |
Result: 1 1 0 1 1 1 0 1 this is the 2’s complement hence the number will be 0 0 1 0 0 0 1 1 which is -35.
You can refer wikipedia page as well.