Hi students, coming to our next topic that is Booth's algorithm. So let us discuss what is this Booth's algorithm. Let we take the multiplication of two sine binary numbers.
If you take any two sine binary numbers, let us see how does Multiplication will be done by using this Booth's algorithm. So this is a flow chart of this algorithm. So this is start and here A is accumulator you call it as 0. Q-1 is one of the binary number of code and this is 0. And M is implied as a multiplicand. q is multiplier and in n indicates the number of bits so if q 0 and q minus 1 is both our 0 0 and 1 1 we have to do direct arithmetic right shift operation and you have to decrement the number of bits if this n is 0 then you have to end the program and save the result in the accumulator if it is not 0 we again uh go back and you'll do the operation So if it is 0, 1, we have to do the add the accumulator plus one of the operand of the multiplicand.
M is multiplicand and you have to do the right shift. If it is 1, 0, then we have to do A minus M and store the result in accumulator. And that value will be arithmetic right shift. And you have to decrement the number of bits. If it is 0, we have to end the program.
So this is... the flowchart for the Booth's algorithm. So let us take one example how this algorithm will be implemented and it is doing the multiplication on binary numbers. So consider any 4 bit numbers that is it's a Q it ends with a bit Q naught.
So Q3, Q2, suppose Q1 and the Q naught. And you can take the Q minus 1, so which is the previous to Q naught. So here the Q minus 1 is considered and we have to take Q minus 1 is indicated declared with the 0. So this is any 4 bit binary number. So let us take the example.
So example is we have to do the calculation 7 into 3 is equal to 21. So the normal calculation is 7 into 3. 7 3 is a 21. It's a normal calculation. So we have to do these calculation in the binary number and we have to get the result as 21. Here the 7 is a multiplicand. So 0 1 1 1 and 3 is represented with q.
So which is this the 4 bit number. So the q is 3 that is 0 0 1 1 so m is multiplicand is represented with 7 and q is 3 now actually we if you multiply these binary numbers we will get the result as 21 suppose 10101 so this is 1 2 4 8 16 so this is a binary representation 16 plus 4 plus 1 you will get answer 21 so we have to get the answer this so means if you do this for 4 cycles then you will get the answer as 21 so let us see the operations how this will be calculated so let us take a is the accumulator and q is this binary number Q minus 1, so which is a previous to the Q naught. So, we have to consider this Q naught and Q minus 1. So, this is Q naught and Q minus 1. So, on these two binary numbers, we are doing the operation, whether we have to do multiplication, addition or subtraction or directly shift operation. So, A, Q, Q minus 1 and the operations. Okay, so let us take first step.
So starting the accumulator value will be it is a 4 bit number. So all zeros. What is the Q value? Q value is 3. 0 0 1 1 and the Q minus 1 is indicated with 0. So it is declared as 0. Okay.
So first what we have to do which we have to check. It is 1 and 0. 1 and 0 means we have to do the subtraction. A is equal to. a minus 1. So, we have to do the operation a minus m.
So, this can be done like a plus 2's complement of m. Either you can directly multiply the, sorry, subtract the a value from m value or else you just add the 2's complement of m with a. Both are the same. So, how you are going to be calculate 2's complement of m? m is 0, 1, 1, 1. So this is the M, 0, 1, 1, 1. So first make it as 1's complement, 1, 0, 0, 0 and you have to do the plus 1. So if you may, for 1's complement if you add 1 you will get the 2's complement, 1, 0, 0, 1. So this is the 2's complement of M.
So A value is, let's start A value is 0, 0, 0, 0 and 2's complement of M is 1, 0, 0, 1. Now add both. So this is 1 0 0 1 you will get the a value. This will be stored in accumulator.
Okay so after a minus m what we have to do you have to shift the arithmetic shift the right shift you have to done the right shift. So what is the value of a first 1 0 0 1 q is 0 0 1 1 and the q minus 1 is 0. So now we have to do the right shift. So you just shift this operands and place 1 1 0 0 1 0 0 1 1 how you will get if you shift this to and this bits were shifting to right okay so this bit is shifting to right so what is the new value now so second step accumulator value is 1 1 0 0 and the q value is 1 0 0 1 And q minus 1 is 1. So now check. What is this two values?
q naught and q minus 1 is both are 1. If q naught and q minus 1 is both are 1, what we have to do? We have directly arithmetic shift right. So we have to do the shift operation directly. So what we have to do?
Shift operation directly. Right shift operation we have to do. So now shift 1 1 1 0. So this is shifting here 0 1 0 0 and this is shifting to here.
Okay. So this is a value. So now write the third step.
So now the accumulator value is 1 1 1 0. 0 1 0 0 is a Q value. And q minus 1 is 1. So now check again. 0, 1. So what we have to do if it is 0, 1? So 0, 1 means. So this is 0, 1. We have to do addition.
So a plus m. a value is 1, 1, 1, 0. m value is 0, 1, 1, 1. So now add both value. 1 0 1 1 1 you will get the carry here and sorry 1 0 if a triple ones it is 1 1 1 1 0. So you will get the carry.
So the a value is 0 1 0 1 q is 0 1 0 0 and 1. So what we have to do we after doing a plus 1 you have to right shift and again decrement. So n is n minus 1 means we have to do n is the number of bits. So how many bits total? 4 bits.
So we have to do the 4 operations to get the result. So now shift right 0 0 1 0 1 0 1 0 0. Okay means we are shifting the bits. So now what is the value of new value? The fourth bit is. 4th step 0 0 1 0 this is the accumulator and 1 0 1 0 is the Q value and Q minus 1 is 0. Now check the values Q naught and Q minus 1. So both are 0. If both are 0 means what we have to do directly arithmetic shift.
So directly we have to do arithmetic shift operation. So here we have to do the shift. operation.
So 0 0 0 1 0 1 0 1 0. Okay. So this is the final output. So now the n becomes 0. Means the 4 bits n 3 2 1. 0 so whenever the n is 0 you have to end the operation so now we are done for Shift operate for shift operations though now then is 0 so the final output is 21 How will get so this is 7 by 3 is nothing but in the binary numbers it is 0 0 0 1 0 1 0 1 it is 21 ok so this is a 8 bit 8 bit bit values so here this is 16 8 sorry 16 8 4 2 1 so 16 plus 4 20 20 plus 1 21 so the final output answer is 21 so this is how to calculate the boots algorithm so you just take any two binary numbers whether it is assigned or unsigned binary numbers Just with the help of this application, you have to check the Q0 and Q-1 values. So this is Q3, Q2, Q1, Q0. So you have to check this value and this value.
Okay, so in each step you have to check these values. So if it is 1, 0, you are doing A-M operation. If it is both or 1, we have to directly do the shift operations.
If it is 0, 1, we are doing A-M operation. addition a plus m if both are zeros you are doing sorry doing direct shift operations okay so after four operations you will get the answer as 7 by 3 is 21 which is in the binary form okay so thank you