0
28kviews
Draw the flowchart of Booth's Algorithm and multiply (−7)∗(3) using Booth's algorithm
1 Answer
2
4.3kviews
written 3.2 years ago by |
Booth's Algorithm
- Booth’s Principle states that “The value of series of 1’s of binary can be given as the weight of the bit preceding the series minus the weight of the last bit in the series.”
- The booth’s multiplication algorithm multiplies the two signed binary integers.
- It is generally used to speed up the performance of the multiplication process.
- Booth’s Algorithm looks in the following manner in terms of flowchart representation:
Terms Used in Booth's Algorithm
- AC stands for Accumulator Counter set as 0 initially.
- M represents Multiplicand Bits.
- -M represents 2’s Complement of M.
- Q represents Multiplier Bits.
- Qn represents the Last Bit of Multiplier Q.
- Qn+1 represents the Incremented value of Qn by 1. But at the initial state, it is set as 0.
- SC stands for Sequential Counter. It represents a number of bits that is nothing but a total number of bits in the multiplier Q.
Working of Booth's Algorithm
- Set the Multiplicand and Multiplier values in binary bits formats as M and Q, respectively.
- At a starting, set the AC and Qn+1 registers values to 0.
- As an SC represent the number of bits in the multiplier (Q). According to that set the value of SC. The value of SC goes on decreasing with each repetition of the computation loop until its value reaches 0.
- The Qn represents the last bit of the Q, and the Qn+1 shows the incremented bit of Qn by 1.
At each iteration Booth’s algorithm checks the condition of QnQn+1 bits.
A] If the bits of QnQn+1 represent 01
- Then Multiplicand Bits (M) is added to the Accumulator Counter (AC = AC + M).
- Then Arithmetic Right Shift operation performs on AC QnQn+1 bits by 1.
- Then decrease the value of Sequence Counter by 1.
B] If the bits of QnQn+1 represent 10,
- Then Multiplicand Bits (-M) is subtracted from the Accumulator Counter (AC = AC - M).
- Then Arithmetic Right Shift operation performs on AC QnQn+1bits by 1.
- Then decrease the value of Sequence Counter by 1.
C] If the bits of QnQn+1 represent 00 or 11
- Then directly Arithmetic Right Shift operation performs on AC QnQn+1 bits by 1.
- Then decrease the value of Sequence Counter by 1.
These checking iterations of bits value of QnQn+1continues until the value of Sequence Counter (SC) reaches 0.
- Finally when SC =0, the result of the multiplication is stored in AC and Q.
Multiplication of (-7) and 3 by using Booth's Algorithm
M = -7 = (1001) and –M = M’ + 1 = 0111
Q = 3 = (0011)
Value of SC = 4, because the number of bits in Q is 4.
Qn=1 according to last bit of Q and Qn+1 set as 0 at initially.
As, (-7) * 3 = -21
Value stored in AC & Q registers = 11101011
(-7) * 3 = 2’s complement of 11101011= −(00010100+1)2=−(00010101)2
= - (16 + 4 + 1) = -21
ADD COMMENT
EDIT
Please log in to add an answer.