Computer Architecture EE bivi © The division process for binary numbers is similar to tl Anthmetic Ope, TE, comer I numbers, 4, Fig. 2.4.1 shows binary division process. \ 10/0, 1/00) =~ | | Quotient Divisor — [tlt[ela} ajo = Dividena | -|1}1jo LI {of Partial remainder |_| =| |0|0|0|4/1|0 He [STE eslclealiaijic laa dee 0[0[0]1(4| [++ Remainder | CY Fig. 2.4.1 Division examples ¢ In the division process, first the bits of the dividend are examined from left right, until the set of bits examined represents a number greater than or equal jy the divisor. * Until this condition occurs, 0's are placed in the quotient from left to right. When the condition is satisfied, a 1 is placed in the quotient and the divisor js Divis subtracted from the partial dividend. The result is referred to as a pattie 1 remainder. 2 ° From this point onwards, the division process is required. In each repetition cycle, additional bits from the dividend are brought down to the partial remainder unti the result is greater than or equal to the divisor and the divisor is subtracted from the result to produce a new partial remainder. ° The process continues until all the bits of the dividend are brought down and result is still less than the divisor. Restoring Division Algorithm { * Fig: 242 shows the hardware for implementation of restoring division. * It consists of n+1-bit binary adder, shift, add and subtract control logic and registers A, B, and Q. * As shown in the Fig. 2.4.2 divisor and dividend are | Tegister Q, respectivel then carried out. loaded into register B and ly. Register A is initially set to zero. The division operation is ter the division is complete, the n-bit quotient is in register Q and the remainder in register A.Anthnotic Operations Divisor PEE nebit bus ‘Binary down counter sequence counter (sc) clock Shift, add and subtract | control logic Quotiont sotting Qo Dividend Fig. 2.4.2 Hardware to implement binary division Division operation steps : 1. Shift A and Q left one binary position. 2. Subtract divisor (Le. add 2's complement of divisor (B)) from A and place answer back in A (A — A-B). 3. If the sign bit of A is 1, set Qo to 0 and add divisor back to A (that is, restore A); Otherwise, set Qo to 1. 4. Repeat steps 1, 2, and 3. n times. A flowchart for division operation is as shown in Fig. 2.4.3. Refer Fig. 2.4.3 on next page. (EEERREZED Perform the division of following numbers using restoring division algorithm : Dividend =1 0 1 0 Divisor=0 011 Solution : Fig. 2.4.4 shows steps involved in the above binary division. 0 0/0, 1/1 Divisor 1/1/14. 0/0) 1'scomplement > [1 Addt [47111] 0) 1) 2's complement of divisorComputer Architecture Aso B = Divisor Q = Dividend sC—n Shift left AQ Yh 0 O41 A=AtB Fig. 2.4.computer Architecture Initiaty Shit lon. Subtract B Sot Qy Restore (A*B) Shift oR A, Q Subtract B Set Qy Restore (A+B) Shift le A, Subtract B Sot Qy Shit le A, Q Subtract B Set Qy Fig. 2.4.4 A restorin 9 division exampleComputer Architecture 2-38 Solution ; Divisor 1's complement Add 1 2's complement ARegister — Q Register Initially 90000 1000 LeftshifA,Q 00001 ooo SublractB 11101 SetQ, @ii10 Restore 00 ooo Left shitA,Q 0 1 Subtract B seta, @ Restore Left shit A, Q Subtract B Set Q, Left shit A, Q Subtract B Set Q, Restore (A + B) Remainder Quotient Fig. 2.4.5 Perform the following division using restoring division algorithm 1001 0101Computer Architecture Solution = Initianty Shite, q Subtract 8 Set Qy Restore Shieh A, a Subtract 8 Set Qy Restore, Shif left A, Q Subtract 8 Set Qo Restore. Shif left A, Subtract B Set Qo Arithmetic Operations ARogister —_ Q Register 10 0.1 Dividend oo1g First cycle Second cycle 90101 omg 0010 0100 «+ mED 14044 Ti44 Third eycle S0101 9B o0100 ©1001 op~g 44044 100 Fourth cycle C0100 §©6MDE Remainder Quotient Fig. 2.4.6 CEERRERED using restoring division algoritim solve the following : Dividend = 17 Divisor = 03.r Architecture Restore (A+B) Shift Subtract B Restore (A+B) Shift Subtract B Shift Subtract B Restore (A+B) Shift Subtract B A Register ooo0000 ooo0011 oooo0o01 000010 ooo0o010 1014 qe ee ed 000010 000104 4-11 180.4 a Remainder Q Register 10001 coord oo 100 o 1000 o100 190000 00100 oooo —~_— Quotient Anthnetis — Dividena Second cyclo Third cyclo Fourth cycle Fifth cycleComputer Architecture ee Operations solution : The restoring division algorithm assumes positive signs of D and V. A Register Q Register Initially e000 0 1 1 1 Dividend Shift oo00 q 1 1 wl SubtactB 1404 Set Qy @101 Restore (A+B) First cycle Shift Subtract B Set Qy Second cycle Restore (AxB) _0 0 1 1 0004 1100 Shift oo14 1000 SubractB 4104 @ooo Third cycle Shift ooo4 SubtractB 4104 Set Qy 7 Fourth cycle Restore (A+B) 0 0 1 14 7 — Remainder Quotient Reminder = (0001), = 1 and Quotient = (0010)) = 2 In the division operation, the magnitudes of quotient (Q) and remainder (R) are not affected by the input signs. The signs of Q and R are easily derived from the signs of D and V using expression : D = Qx V+R The signs of Q and R for all possible combinations of signs of D and V are as follows = => => => = i fer Krowleda® TECHNICAL PUBLICATIONS”. An up thrust forComputer Architecture Arithmetic Op ig restoring method ea Demonstrate the division of 1100 by 101; ust block diagram and explain the operation. 1. Explain the restoring division algorithm. ane ane exannp les 2. Discuss in detail about division algorithm in detail with diag EESEGLoE Non-Restoring © Consider the sequence of operations that takes place after the subtr operation in the restoring algorithm. negative If A is positive = Shift left ang subtract divisor > 2A - B_ Restore Shift left and subtract divi +2(A+B)-B © Looking at the above operations we can write following steps for non-rest algorithm. shift A and Q left one bit position and subtract di Step 1: If the sign of A is 0, s from A; otherwise, shift A and Q left and add divisor to A. If the sign of 0, set Qg to 1; otherwise, set Qo to 0. Step 2: Repeat steps 1 and 2 for n times. Step 3: If the sign of A is 1, add divisor to A. (REED step 3 is required t0 leave the proper positive remainder in A at the end of 1 cycles. © A flowchart for non-restoring division operation is as shown in Fig. 24) (See Flowchart on next page) nuinbers using non-restoring divi Perform the division of follow a2 I (© Diviten = 7 dio sie [Il 9 g (p) Divicor. 00.07 1 op Solution : Fig. 2.4.8 shows steps 4 Ta Ip tie non-restoring binary division In this example, after 4 cycles & is positive and hence step 3 is not required.tor architecture AO B — Divisor Q ~ Dividend sC =n Shift left A+A-B Quotient in Q Remainder in AComputer Architecture Arogistor Initially 0 0 0 0 0 cane) Shit lot A,Q 9 0 0 0 1 Subtract B 1101 SotQ Gi 110 Shift le A, Q Arithmetic Openy Dad Q rogistor sc 0 1 0 +— Dividend 100 o1o0[] Firstcycle 0 1 1 04 of 100 10 Second cycle 0 a wid (048) ade O00 yi 4 Sot Qy Shift left A, Q Add B Third cycle 0 0 1 1 Set Qy @e 10 oP M)L Fourth cycle 0 0 0 ShiftletA,Q 0 0 10 0 SubtractB 11 o1 o4 VSS Remainder 1 1 00 0} (0; [4 [4 : Subtract B means add B in 2's complement form Quotient Fig. 2.4.8 A non-restoring division example ERRLELLD Perform the division of following numbers using non-restoring dit algorithm Dividend =1 01 1 Divisor=0 101 Divisor Solution : ofofsfo]1 [ifsfolafo 1 tfofafa 1's complement Add 1 2's complementnon-restoring, Frstcyoe ond Second cycle 0 1 0 Third cycle oo14 Fourtheycle 0 0 0 Fig. 24.9 A non-restoring division example algorithm. There is no simple algorithm for signed division. In signed division, the Operands ‘transform them into positive values.Arithmetic: Op or Architecture Compu A Register Q Register Initially 0000 01001 1 <—Dwidend Shit 0000 700) 4) {imal Subtract 1 1 0.0 pr First cyclo Set @1 00 ne shit 1004 oo 1100) Add 0100 \ second cycle oad oo 11005 shin 1010 011000 aad 0100 Third cyclo he) o1 1000 shin 1100 1190000 Fourth cyclo poet 0nd0.0 eles 000 ; shih 0.001 ee 1% 00 Fifth cycle QO o1 ‘Boone Shit 10141 OOOH Add 0100 Sixth cycle 144 Noone a a Remainder Quotient (So eoiee aerate) imple 2.4.10 : Explain non-restoring division algorithm with the help of suitable exam He 2.4.11 : Perform the division on the following 5-bit unsigned inte non-restoring division - 10101/00101 Coree Anthmatic Operations S10 algorithny with the helps af suitable example DOM [EES compari Comparison between Restoring and Non-Restoring Division Algorithm 1. Explain nom-restoring at Restorin, 8 Non-restoring Feeds restoring of register A iv the res subtraction is negative, esull of Does not need restoring, In each cyele content of register \ is register A is first In cach eyele content of register A ts first shifted left and! then divisor is subtracted shifted lett aud then divisor ts adel OF subtracied with the depending on the sign of A. from it Does not need restoring of remainder, nder if remainder is 4. Slower algorithm, Na