Algorithms Multiplication MULTIPLICATION ALGO. é 73 10111 Multiplicand FLOWCHART 19 _X 10011 Multiplier 10111 + Multiplication of two fixed-point 10111 binary numbers in signed 00000 «+ magnitude representation is done 00000 by a process of successive shift 10111 and adds operations. 437 110110101 Product If the multiplier bit is a 1 the multiplicand is copied down otherwise, zeros are copied down. The numbers copied down in successive lines are shifted one position to the left from the previous number. Finally, the numbers are added and their sum forms the product. The sign of the product is determined from the sign of the multiplicand and multiplier. If they are alike, the sign of the product is positive. If they are unlike, the sign of the product is negative.Algorithms Multiplication Hardware Implementation for Signed Magnitude Data + When multiplication is implemented in a digital computer, it is convenient to change the process slightly. — First, instead of providing registers to store and add simultaneously as many binary numbers as there are bits in the multiplier it is convenient to provide an adder for the summation of only two binary numbers and successively accumulate the partial products in a register. — Second, instead of shifting the multiplicand to the left, the partial product is shifted to the right, which results in leaving the partial product and the multiplicand in the required relative positions. — Third, when the corresponding bit of the multiplier is O, there is no need to add all zeros to the partial product since it will not alter its value.Algorithms Multiplication 3B, Bregister Sequence counter (SC) Complementer and parallel adder (rightmost bit) Ay Q Qn 0— EFS A register Qregister * The hardware for multiplication consists of four registers. Registers A and B along with SC & Q. * The multiplier is stored in the Q register and its sign in Qs. The sequence counter SC is initially set to a number equal to the number of bits in the multiplier.Algorithms Multiplication The counter is decremented by 1 after forming each partial product. When the content of the counter reaches zero, the product is formed and the process stops. Initially, the multiplicand is in register B and the multiplier in Q. The sum of A and B forms a partial product which is transferred to the EA register. Both partial product and multiplier are shifted to the right. This shift will be denoted by the statement shr EAQ to designate the right shift. The least significant bit LSB of A is shifted into the most significant position MSB of Q, the bit from E is shifted into the most significant position MSB of A, and O is shifted into E. After the shift, one bit of the partial product is shifted into Q pushing the multiplier bits one position to the right.Algorithms Multiplication The rightmost flip-flop in register Q, designated by Qn, will hold the bit of the multiplier, which must be inspected next. Hardware Algorithm Initially, the multiplicand is in B and the multiplier in Q. Their corresponding signs are in Bg and Q, respectively. The signs are compared, and both A and Q are set to correspond to the sign of Multiply operation (( Maltiplicand in BY \ Multiplier in Q_/ As — Qs® Bs Qs® Bs EO Co END \ (product is in AQ) //Algorithms Multiplication the product since a double length product will be stored in registers A and Q. Registers A and E are cleared and the sequence counter SC is set to a number equal to the number of bits of the multiplier. After the initialization, the low order bit of the multiplier in Q is tested. -—Ifitisal1the multiplicand in B is added to the present partial product in A. — Ifitis a O, nothing is done. Register EAQ is then shifted once to the right to from the new partial product. The sequence counter is decremented by 1 and its new value checked. If it is not equal to zero, the process is repeated till SC= 0. The final product is available in both A and Q, holding the most significant bits and the least significant bits.Algorithms Multiplication Multiplicand B= 10111 E A Q SC Multiplier in @ 0 60000 10011 101 Q,- add B Jou First partial product 0 10111 Shift right FAQ. 0 O11 11001 100 Q,=l,add B 101 Second partial product 1 ‘00010 Shift right FAQ. 0 10001 01100 au Q, = 0; shift right EAQ 0 01000 10110 O10 Q, = 0; shift right EAQ_ 0 00100 O1olL 001 Q.= ladd B 40U1 Fifth partial product 0 11011 Shift right EAQ 0 01101 10101 000 Final product in AQ = 0110110101Algorithms Multiplication Booth Multiplication Algorithm + Booth algorithm give a procedure for multiplying binary integers in signed 2's complement representation. It operates on the fact that * strings of O’s in the multiplier require no addition but just shifting and * string of I's in the multiplier from bit weight 2* to weight 2M can be treated as 2K*/-2M_ + For example the binary number 001110 (+14) has a string of 1's from 2° to 2!. K=3, m=1 . The number can be represented as 2K*I-QM = 24-21= 16-2 =14. + Therefore, the multiplication M x 14 where M is the multiplicand and 14 the multiplier, can be done as M x 24-Mx2!, + Thus the product can be obtained by shifting the binary multiplicand M four times to the left and subtracting M shifted left once.Algorithms Multiplication Booth algorithm requires examination of the multiplier bits and shifting of the partial product. Prior to the shifting, the multiplicand may be added, subtracted, or left unchanged from the partial product according to the following rules: 1. The multiplicand is subtracted from the partial product upon encountering the first least significant 1 in a string of l's in the multiplier. 2. The multiplicand is added to the partial product upon encountering the first O in a string of O's in the multiplier. 3. The partial product does not change when the multiplier bit is identical to the previous multiplier bit.Algorithms Multiplication + The algorithm works for positive or negative multipliers in 2's complement representation. This is because a negative multiplier ends with a string of I's and the last operation will be a subtraction of the appropriate weight. + For example, a multiplier equal to -14 is represented in 2's complement as 110010 and is treated as -2 4+ 2?-2!= - 14 BR register Sequence counter (SC) ‘Complementer and parallel adder AC register [———>| OR register —|Algorithms Multiplication The hardware implementation of Booth algorithm is similar to multiply then this except that the sign bits are not separated We rename registers A, B, and Q as AC, BR, and QR, respectively Q, designate the least significant bit of the multiplier in register QR. An extra flip flop Q,,, is appended to QR to facilitate a double bit inspection of the multiplier. The flowchart for Booth algorithm AC and the appended bit Q, , , are initially cleared to 0 and the sequence counter SC is set to a number n equal to the number of bits in the multiplier. The two bits of the multiplier in Q, and Q, ,, are inspected. — If the two bits are equal to 1 O, it means that the first 1 in a string of I's has been encountered and subtraction of the multiplicand from the partial product in AC is required.Algorithms Matuply Multiplicatior Cae") ACO Seon =10 =o ACK AC+ BR+1 =0 Wow ACe BR ashr(AC& QR) So— SG-1Algorithms Multiplication — If the two bits are equal to O 1 it means that the first O in a string of O's has been encountered and addition of the multiplicand to the partial product in AC is required. — When the two bits are equal (O 0, 1 1), the partial product does not change. + An overflow cannot occur because the addition and subtraction of the multiplicand follow each other. + The next step is to shift right the partial product and the multiplier (including bit Q,,,). This is an arithmetic shift right (ashr) operation which shifts AC and QR to the right and leaves the sign bit in AC unchanged. * The sequence counter is decremented and_ the computational loop is repeated n times.Algorithms Multiplication AR = 101ul 0.0.4) BR + 1-001 AC OR On, 8 Initial OCA LOL a 101 io Subtract BR OROOL O1OO] ashr OOD LIOOL 1 O00 bea ashr OOOLO CLD 1 OL o1. Add AR HOUEL LOU ashr Ln LO a OL oo ashr THILO OHOLL a OO 1 oO Subtract BR COOL OOLL ash OOOLL LOLOL 1 (HK)